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

Question

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.

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 04 '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 05 '11 at 18:13
I have exactly the same problem. Did you finally find a solution? — , Feb 19 '13 at 13:48
@Simran I never actually went ahead with any solution. I was trying to optimize wind turbine locations within a footprint. On reflection I think it is better in my case to generate every possible configuration and then measure the quality of the solution. If you can generate every possible solution that is surely better than a genetic algorithm that only gives one solution (however optimal) that may not be the best. — Matthew Snape, Feb 22 '13 at 15:12
I have the same problem, and I don't know where to look. Somehow triangle looks right but is there any compact theory in geometry about this? — , Sep 16 '13 at 12:43
@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
What about constrained triangulation with a minimal area of triangle, and take their centroids? The Triangle library does this — mdsumner, Oct 07 '18 at 21:13

score 9 · Answer 1 · answered Jan 04 '11 at 16:53

9

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:

square vs hexagonal grid

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.

answered Jan 04 '11 at 16:53

julien

10,186
6
55
93

gis tool to do that... http://www.ian-ko.com/ geo-wizard random point in polygon. – Brad Nesom Jan 04 '11 at 17:43
1

Thanks! But the question is not exactly about random points in polygon, right? – julien Jan 04 '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 04 '11 at 21:00

score 6 · Answer 2 · edited Apr 13 '17 at 12:22

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.)

score 5 · Accepted Answer · answered Jan 05 '11 at 20:32

5

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.

answered Jan 05 '11 at 20:32

Kirk Kuykendall

25,787
8
65
153

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 06 '11 at 17:51

score 0 · Answer 4 · answered Sep 25 '22 at 13:43

0

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"

https://www.youtube.com/watch?v=zG-5TB5O9og

answered Sep 25 '22 at 13:43

Maxi Díaz

1

Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Community Sep 25 '22 at 17:19

score 0 · Answer 5 · answered Jan 04 '11 at 16:59

0

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)

answered Jan 04 '11 at 16:59

Uffe Kousgaard

2,543
15
24

1

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 04 '11 at 20:59

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

5 Answers5

Linked

Related