10

I am looking for an algorithm to generate equally distributed points inside a polygon.

Here is the scenario:

I have a polygon specified by the coordinates of the points at the corners (x, y) for each point. And I have the number of points to generate inside the polygon.

For example lets say I have a polygon containing 5 points: (1, 1) ; (1, 2) ; (2, 3) ; (3, 2) ; and (3, 1)

And I need to generate 20 equally distanced points inside that polygon.

Note: Some polygons may not support equally distributed points, but I'm looking to distribute the points in a way to cover all the region of the polygon with as much consistency as possible. (what i mean is I don't want a part with a lot more points than another)

Is there an algorithm to do so? or maybe a library

I am working on a C# application, but any language is ok, since I only need the algorithm and I can translate it.

Thanks a lot for any help

Y2theZ
  • 10,162
  • 38
  • 131
  • 200
  • 4
    You might want to try http://math.stackexchange.com/ to get the algorithm, then post here if you need assistance translating the algorithm to C#. – Michael Liu Jun 24 '12 at 15:11

7 Answers7

15

The simple approach I use is:

  1. Triangulate the polygon. Ear clipping is entirely adequate, as all you need is a dissection of the polygon into a set of non-overlapping triangles.

  2. Compute the area of each triangle. Sample from each triangle proportionally to the area of that triangle relative to the whole. This costs only a single uniform random number per sample.

  3. Once a point is determined to have come from a given triangle, sample uniformly over the triangle. This is itself easier than you might think.

So really it all comes down to how do you sample within a triangle. This is easily enough done. A triangle is defined by 3 vertices. I'll call them P1, P2, P3.

  1. Pick ANY edge of the triangle. Generate a point (P4) that lies uniformly along that edge. Thus if P1 and P2 are the coordinates of the corresponding end points, then P will be a uniformly sampled point along that edge, if r has uniform distribution on the interval [0,1].

    P4 = (1-r)*P1 + r*P2

  2. Next, sample along the line segment between P3 and P4, but do so non-uniformly. If s is a uniform random number on the interval [0,1], then

    P5 = (1-sqrt(s))*P3 + sqrt(s)*P4

r and s are independent pseudo-random numbers of course. Then P5 will be randomly sampled, uniform over the triangle.

The nice thing is it needs no rejection scheme to implement, so long, thin polygons are not a problem. And for each sample, the cost is only in the need to generate three random numbers per event. Since ear clipping is rather simply done and an efficient task, the sampling will be efficient, even for nasty looking polygons or non-convex polygons.

  • +1 for triangulating the polygon and sampling the discrete distribution weighted by triangle area. For sampling within a triangle, I prefer to sample the right unit triangle [(0, 0), (0, 1), (1, 0)] and apply the affine transformation onto the target triangle; the transformation matrix can be precomputed and applied efficiently with only multiplication and addition. Note that sampling from the right unit triangle is easy: `x, y <- U; if x + y > 1, x, y := 1-y, 1-x`. – ecatmur Jun 25 '12 at 09:36
  • @ecatmur - Yes, there are several ways to sample within a simplex. I used the one I chose because the extension to higher dimensional simplexes is easy to see. –  Jun 25 '12 at 12:33
  • True, but sampling from the standard unit simplex is also easy and efficient - see e.g. http://stackoverflow.com/questions/3010837/sample-uniformly-at-random-from-an-n-dimensional-unit-simplex – ecatmur Jun 25 '12 at 12:48
  • I have designed a visual demo of pretty much this exact algorithm, if it's of any interest: http://cecchi.me/portfolio (The [source](http://cecchi.me/js/point-picking.js.src) is unnecessarily verbose because of the visual component) – Cecchi May 06 '13 at 01:18
4

An easy way to do this is this:

  1. Calculate the bounding box
  2. Generate points in that box
  3. Discard all points not in the polygon of interest

This approach generates a certain amount of wasted points. For a triangle, it is never more than 50%. For arbitrary polygons this can be arbitrarily high so you need to see if it works for you.

For arbitrary polys you can decompose the polygon into triangles first which allows you to get to a guaranteed upper bound of wasted points: 50%.

For equally distanced points, generate points from a space-filling curve (and discard all points that are not in the polygon).

usr
  • 168,620
  • 35
  • 240
  • 369
  • Imagine a very thin rectangle positioned diagonally. That wastes tons of samples. Still, a reasonable approach. – Roman Starkov Jun 24 '12 at 15:28
  • @romkyns, I was mistakenly thinking of triangles only. I added a solution for arbitrary polygons. – usr Jun 24 '12 at 15:30
  • 1
    Imagine a thin _triangle_ positioned diagonally... :) – Roman Starkov Jun 24 '12 at 15:32
  • You can generate a random point in a triangle as follows. Every triangle has a base and a height. Pick two random numbers from 0 to the height. If the first is smaller, take the first number as the height to put the point at. If the second is smaller, take (height - first number) as the height to put the point at. Randomly pick a point from that height. This method requires picking 3 random numbers. Pick and discard until you are in the triangle requires an average of 4, and can take unbounded time. – btilly Jun 24 '12 at 15:47
2

You can use Lloyd’s algorithm:

https://en.m.wikipedia.org/wiki/Lloyd%27s_algorithm

John
  • 41
  • 2
1

You can try the {spatialEco} package (https://cran.r-project.org/web/packages/spatialEco/index.html) and apply the function sample.poly (https://www.rdocumentation.org/packages/spatialEco/versions/1.3-2/topics/sample.poly)

You can try this code:

library(rgeos)
library(spatialEco)

mypoly = readWKT("POLYGON((1 1,5 1,5 5,1 5,1 1))")
plot(mypoly)
points = sample.poly(mypoly, n= 20, type = "regular")
#points2 = sample.poly(mypoly, n= 20, type = "stratified")
#another type which may answer your problem
plot(points, col="red", add=T)
IndieGameDev
  • 2,905
  • 3
  • 16
  • 29
Jul
  • 11
  • 1
0

The easy answer comes from an easier question: How to generate a given number of randomly distributed points from the uniform distribution that will all fit inside a given polygon?

The easy answer is this: find the bounding box of your polygon (let's say it's [a,b] x [c,d]), then keep generating pairs of real numbers, one from U(a,b), the other from U(b,c), until you have n coordinate pairs that fit inside your polygon. This is simple to program, but, if your polygon is very jagged, or thin and skewed, very wasteful and slow.

For a better answer, find the smallest rotated rectangular bounding box, and do the above in transformed coordinates.

André P.
  • 1
-2

  1. Genettic algorithms can do it rather quickly
    Reffer to GENETIC ALGORITHMS FOR GRAPH LAYOUTS WITH GEOMETRIC CONSTRAINTS

  2. You can use Force-Directed Graph for that...
    Look at http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing)
    it defiantly can throw you a bone.

I didn't try it ever,
but i remmember there is a possiblity to set a Fix for some Vertices in the Graph

Your Algorithm will eventually be like

  1. Create a Graph G = Closed Path of the Vertices in V
  2. Fix the Vertecies in place
  3. Add N Verticies to the Graph and Fully connect them with Edges with equal tension value 1.0
  4. Run_force_graph(G)

Scale Graph to bounded Box of

Though it wont be absolute because some convex shapes may produce wiered results (take a Star)

LASTLY: didn't read , but it seems relevant by the title and abstract
take a look at Consistent Graph Layout for Weighted Graphs

Hope this helps...

Tomer W
  • 3,395
  • 2
  • 29
  • 44
  • Possibly because your providing sources of information which will help develop the answer not providing an actual answer – MikeT Nov 11 '16 at 14:37
-4

A better answer comes from a better question. Suppose you want to put a set of n watchtowers to cover a polygon. You could see this as an optimization problem: find the 2n coordinates of the n points that will minimize a cost function (or maximize a value function) that fits your goal. One possible cost function could calculate, for each point, the distance to its closest neighbor or the boundary of the polygon, whichever is less, and calculate the variance of this sequence as a measure of "non-uniformity". You could use a random set of n points, obtained as above, as your initial solution.

I've seen such a "watchtower problem" in some book. Algorithms, calculus, or optimization.

@Youssef: sorry about the delay; a friend came, and a network hiccuped.

@others: have some patience, don't be so trigger-happy.

André P.
  • 1
  • 1
    The question of placing watchtowers is not a better question than sampling a uniform distribution; it's a completely different question. – Roman Starkov Jun 25 '12 at 08:23