# 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)? – Brad Nesom Jan 4 '11 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? – Brad Nesom Jan 4 '11 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? – Kirk Kuykendall Jan 5 '11 at 18:13
• Somehow related: gis.stackexchange.com/q/4927/162 – julien Jan 7 '11 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. – whuber Sep 16 '13 at 14:21

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? – whuber Jan 6 '11 at 17:51

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. – Brad Nesom Jan 4 '11 at 17:43
• Thanks! But the question is not exactly about random points in polygon, right? – julien Jan 4 '11 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. – whuber Jan 4 '11 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.)

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. – whuber Jan 4 '11 at 20:59