17

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.

Improve this question
9
  • 1. Yes. 2. Do you want random or ordered (grid)?
    – Brad Nesom
    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?
    – Brad Nesom
    Jan 4, 2011 at 16:13
  • 1
    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, 2011 at 18:13
  • Somehow related: gis.stackexchange.com/q/4927/162
    – julien
    Jan 7, 2011 at 8:10
  • 1
    @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, 2013 at 14:21

5 Answers 5

Reset to default
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.

Improve this answer
3
  • gis tool to do that... ian-ko.com geo-wizard random point in polygon.
    – Brad Nesom
    Jan 4, 2011 at 17:43
  • 1
    Thanks! But the question is not exactly about random points in polygon, right?
    – julien
    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.
    – whuber
    Jan 4, 2011 at 21:00
6

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

Improve this answer
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.

Improve this answer
1
  • 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, 2011 at 17:51
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)

Improve this answer
1
  • 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 4, 2011 at 20:59
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

Improve this answer
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 Bot
    Sep 25, 2022 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.