Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Have a look at mathworks.com/matlabcentral/newsreader/view_thread/170480 –  Shai Covo Dec 28 '10 at 14:54
add comment

3 Answers

up vote 9 down vote accepted

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

share|improve this answer
    
Here is the article referred to by whuber. –  J. M. Dec 28 '10 at 2:19
    
that's for convex polygon if I'm not mistaken. But what about general polygon, regardless of convex or concave? –  Graviton Dec 28 '10 at 6:02
1  
@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. –  whuber Dec 28 '10 at 15:22
add comment

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

share|improve this answer
    
Well, the rejection method could be made more efficient if the polygon has symmetries, but apparently Ngu is interested in arbitrary polygons, so... –  J. M. Dec 27 '10 at 11:03
2  
In any event, here is what you want to use if you're taking the triangulation approach. Here is the associated C code. –  J. M. Dec 27 '10 at 11:15
    
@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? –  Graviton Dec 28 '10 at 6:04
    
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. –  J. M. Dec 28 '10 at 6:08
    
Awesome... sadly I cannot upvote more than once. –  J. M. Dec 28 '10 at 14:39
show 1 more comment

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.

share|improve this answer
    
+1 For the reference to that Poisson disk process paper. –  whuber Dec 28 '10 at 17:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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