# Seeking algorithm to place maximum number of points within constrained area at minimum spacing?

I have a polygon layer that describes a constraint; I wish to add points within this area. I want to add as many points as possible, but they must have a minimum spacing between them. Is it possible to do this with GIS?

To clarify, it would be best if an ordered grid could be generated, as this would guarantee the most points. However the constraint would rarely allow this, and it may be preferable to remove points to allow an offset to better fit within the constraint.

• 1. Yes. 2. Do you want random or ordered (grid)? Jan 4, 2011 at 15:57
• Seems to be two questions. Do you want an algorithm to do this outside of software? Or do you want to know what GIS system can do this? Jan 4, 2011 at 16:13
• Are the points constrained so that they must be >= the minimum distance from the polygon's boundary? If, so the question might be more clearly stated as: How can I pack the maximum number of circles into a polygon? Jan 5, 2011 at 18:13
• Somehow related: gis.stackexchange.com/q/4927/162 Jan 7, 2011 at 8:10
• @qva No there is not, because the exact solutions that can be found are asymmetrical and difficult to obtain even for simple shapes like rectangles. The best computing methods I have found are based on spatial simulated annealing (and they work very well, even though they require a lot of computation). Using them I have looked at solutions for many polygons of varying shapes. It is clear that the polygon boundaries control the solutions close to the boundaries; deep within the interior they tend to approximate hexagonal packings of disks. Sep 16, 2013 at 14:21

I do not know any GIS tool to do that, but I have an idea on the algorithm.

First, an approximation of the maximum point number can be obtained with this formula:

``````Nb = 4.A / Pi.d^2
``````

(where `A` is the polygon area and `d` the minimum spacing distance).

Then, to try to locate these points into the polygon, the best pattern is not the square grid but the hexagonal grid. See: Finally, some optimization techniques using force models could be used to refine the relative positioning of the points.

NB: It is a well known problem in crystallography.

• gis tool to do that... ian-ko.com geo-wizard random point in polygon. Jan 4, 2011 at 17:43
• Thanks! But the question is not exactly about random points in polygon, right? Jan 4, 2011 at 17:51
• As an initial quick-and-dirty approximation, hexagonal packing works ok. It is almost never optimal, though. I would expect the potential improvement to be proportional to the length of the perimeter of the polygon, so for non-tortuous polygons with many points this isn't a bad approach. Jan 4, 2011 at 21:00

See the thread at https://math.stackexchange.com/questions/15624/distribute-a-fixed-number-of-points-uniformly-inside-a-polygon . In particular, note the reference (in a comment) to "Poisson disk process" and do some Web searching. The connection with the current question is that when you can distribute a given number of points uniformly, then you can systematically increase that number until no more points can be put into the polygon and that solves the problem of maximizing the number of points subject to a minimum distance requirement. (Technically, the two problems are dual optimization problems where the objectives and constraints are interchanged.)

I think this could be thought of as a "packing" problem.

If so, you might want to try a Genetic Algorithm, perhaps one similar to that in On Genetic Algorithms for the Packing of Polygons.

• Interesting reference, thanks. A quick glance suggests that the paper's algorithm needs the polygons to be rectangles. Do you know whether it can be generalized to arbitrary polygons? Jan 6, 2011 at 17:51

The solution must be equilateral triangles, http://en.wikipedia.org/wiki/Equilateral_triangle. Only question is the length of the sides and the "x-y-offset" in relation to your polygon.

(same as the hexagonal grid mentioned below)

• This is true only within an infinite plane. The boundary of a finite polygon severely constrains the configuration. When there are many points, they approximately form equilateral triangles. Jan 4, 2011 at 20:59

Old but gold, there's a video on YouTube from 2020 showing how to do it interactively in QGIS. "QGIS how many circles contains a polygon"