9
$\begingroup$

I have a polygon in 2D (defined by a series of Vertex $V$ with coordinates). The polygon can be convex or concave. I have $n$ number of fix points I can put inside the polygon.

The question is, how can I distribute the fix points as uniformly as possible inside the polygon?

The motivation for this question is I want to create a mesh generator and I want all the triangular elements $E$ ( which is defined by a list of vertices $V$) to look good with no too small or too large angles. In order to control the granularity of the mesh I am thinking about using the number of fix points $n$ as the controlling parameter. The fix points are used to control the vertex of the triangular elements.

Is there any algorithm for this?

$\endgroup$
12
$\begingroup$

Just dropping points into the polygon according to a uniform distribution will not, unfortunately, generate very uniform solutions: with extremely high probability there will be large gaps and tight clusters.

Obtaining a highly uniform pattern within an arbitrary (convex) polygon is a difficult problem to solve; exact solutions are known only for special polygons and very small numbers of points. As the number of points $n$ grows, they tend to fall into a hexagonal pattern. However, like real crystals, these patterns can exhibit faults and fractures imposed by the polygon's boundary. As a quick and dirty solution you might estimate the average spacing by dividing the polygon's area by $n$ and solving for the dimensions of a hexagon of that area, creating an hexagonal mesh of those dimensions, and performing some trial overlays of that mesh (translating it a bit in each trial) to find something that works well. You are likely to run into trouble at places just inside the polygon's boundary, though.

One practical way to find solutions that really work is with spatial simulated annealing. Although that's a computationally intensive and purely approximate approach, in practice you can get reasonable solutions for the intended application in an extremely short time (thousands of iterations rather than hundreds of thousands).

$\endgroup$
  • 1
    $\begingroup$ Here is the article referred to by whuber. $\endgroup$ – J. M. is a poor mathematician Dec 28 '10 at 2:19
  • $\begingroup$ that's for convex polygon if I'm not mistaken. But what about general polygon, regardless of convex or concave? $\endgroup$ – Graviton Dec 28 '10 at 6:02
  • 1
    $\begingroup$ @J.M. Thanks for finding that. Unfortunately you need subscription access to a somewhat obscure journal in order to read the article. @Ngu Soon Hui: I'm not sure what your question is. I can say (from experience) that SSA solves the problem beautifully for nonconvex polygons, but (a) the solutions often depart markedly from the idealized hexagonal patterns seen in the interiors of convex polygons and (b) it takes more computation to converge to a near-optimal solution. $\endgroup$ – whuber Dec 28 '10 at 15:22
7
$\begingroup$

The simplest idea is to generate a sequence of points $(X_i,Y_i)$, where $X_i,Y_i$ are independent uniform random variables, in a rectangle containing the polygon (the minimal rectangle bounding the polygon). Then, you simply drop the points which fall outside the polygon. You continue until you get $n$ unrejected points.

As we could expect, this problem has been considered before by many people. You might find this one very useful. The basic question is how fast/simple you want to generate the $n$ points. The method I described is most simple, but might be time consuming.

EDIT: To add some mathematics to this post, let us justify the rejection method and triangulation approaches (though they might seem intuitively clear).

Rejection method approach. Suppose that $(X,Y)$ is uniformly distributed in a rectangle $R$ bounding the polygon $M$, and that $S$ is an arbitrary square contained in $M$. Then, $$ {\rm P}((X,Y) \in S |(X,Y) \in M) = \frac{{{\rm P}((X,Y) \in S )}}{{{\rm P}((X,Y) \in M)}} = \frac{{{\rm area}(S) /{\rm area}(R)}}{{{\rm area}(M)/{\rm area}(R)}} = \frac{{\rm area}(S) }{{{\rm area}(M)}}. $$ Hence, given that $(X,Y) \in M$, $(X,Y)$ is uniformly distributed in $M$.

Triangulation approach. Suppose that the polygon $M$ is partitioned into triangles $T_1,\ldots,T_m$, and set $p_i = {\rm area} (T_i)/ {\rm area}(M)$. Suppose that ${\rm P}((X,Y) \in T_i)=p_i$ and that, given $(X,Y) \in T_i$, $(X,Y)$ is uniformly distributed in $T_i$. Now, for fixed $k$, let $S \subset M$ an arbitrary square contained in $T_k$ (think of arbitrarily small squares). Then, $$ {\rm P}((X,Y) \in S) = \sum\limits_{i = 1}^m {{\rm P}((X,Y) \in S|(X,Y) \in T_i )p_i } = {\rm P}((X,Y) \in S|(X,Y) \in T_k )p_k. $$ Since, given that $(X,Y) \in T_k$, $(X,Y)$ is uniformly distributed in $T_k$, we have $$ {\rm P}((X,Y) \in S|(X,Y) \in T_k ) = \frac{{{\rm area}(S)}}{{{\rm area}(T_k )}}. $$ Hence, $$ {\rm P}((X,Y) \in S) = \frac{{{\rm area}(S)}}{{{\rm area}(T_k )}}\frac{{{\rm area}(T_k )}}{{{\rm area}(M)}} = \frac{{{\rm area}(S)}}{{{\rm area}(M)}}. $$ We conclude that $(X,Y)$ is uniformly distributed in $M$.

$\endgroup$
  • $\begingroup$ Well, the rejection method could be made more efficient if the polygon has symmetries, but apparently Ngu is interested in arbitrary polygons, so... $\endgroup$ – J. M. is a poor mathematician Dec 27 '10 at 11:03
  • 2
    $\begingroup$ In any event, here is what you want to use if you're taking the triangulation approach. Here is the associated C code. $\endgroup$ – J. M. is a poor mathematician Dec 27 '10 at 11:15
  • $\begingroup$ @J.M, nice link! I just wonder whether if I can triangulate the polygon, and then generate the fix point according to the algorithm you outline; would it be equivalent to what I want to do in my original question? $\endgroup$ – Graviton Dec 28 '10 at 6:04
  • $\begingroup$ The recommendation boils down to "triangulate, pick a triangle using the areas of those triangles as weighted probabilities, and generate points within the selected triangle". I haven't done the requisite experiments so I can't really say if this is immune to clustering and other problems. $\endgroup$ – J. M. is a poor mathematician Dec 28 '10 at 6:08
6
$\begingroup$

As whuber mentions, using a uniform distribution for sampling will result in "clumpiness" of the points. One way of quantifying this "clumpiness" is through a measure called discrepancy. There are numerous low-discrepancy sequences out there. You may also want to look into the Poisson disk method.

$\endgroup$
  • $\begingroup$ +1 For the reference to that Poisson disk process paper. $\endgroup$ – whuber Dec 28 '10 at 17:00
2
$\begingroup$

I came across this problem as well and have solved it by using K-means clustering.

For a given polygon, I generate N random cluster centers in the polygon's shape. For each center, I find the cluster of pixels in the polygon that are closest to this center (this is a Voronoi fragmentation of your shape). Iteratively move the centers to their respective cluster's center of gravity.

Note that this is a heuristic that doesn't guarantee to find the optimum distribution; when the iterations stabilize, you have found a local minimum that serves as an approximation of ideally uniformly distributed points in your polygon shape.

Here's an example result of 100 points uniformly distributed over a cloud shape and their respective (Voronoi) areas of influence

$\endgroup$
  • $\begingroup$ +1: This is known as Lloyd's algorithm, and is indeed often used to compute well-distributed point sets. $\endgroup$ – Rahul Jun 6 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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