Why do we need to triangulate a convex polygon in order to sample uniformly from it?

Question

Suppose I want to uniformly sample points inside a convex polygon.

One of the most common approaches described here and on the internet in general consists in triangulation of the polygon and generate uniformly random points inside each triangles using different schemes.

The one I find most practical is to generate exponential distributions from uniform ones taking -log(U) for instance and normalizing the sum to one.

Within Matlab, we would have this code to sample uniformly inside a triangle:

vertex=[0 0;1 0;0.5 0.5]; %vertex coordinates in the 2D plane

mix_coeff=rand(10000,size(vertex,1)); %uniform generation of random coefficients
x=-log(x); %make the uniform distribution exponential
x=bsxfun(@rdivide,x,sum(x,2)); %normalize such that sum is equal to one
unif_samples=x*vertex; %calculate the 2D coordinates of each sample inside the triangle

And this works just fine:

However, using the exact same scheme for anything other than a triangle just fails. For instance for a quadrilateral, we get the following result:

Clearly, sampling is not uniform anymore and the more vertices you add, the more difficult it is to "reach" the corners.

If I triangulate the polygon first then uniform sampling in each triangle is easy and obviously gets the job done.

But why? Why is it necessary to triangulate first?

Which specific property have triangle (and simplexes in general since this behaviour seems to extend to n-dimensional constructions) that makes it work for them and not for the other polygons?

I would be grateful if someone could give me an intuitive explanation of the phenomena or just point to some reference that could help me understand what is going on.

Answer 1

I should point out that it's not strictly necessary to triangulate a polygon in order to sample uniformly from it. Another way to sample a shape is rejection sampling and proceeds as follows.

1. Determine a bounding box that covers the entire shape. For a polygon, this is as simple as finding the highest and lowest x and y coordinates of the polygon.
2. Choose a point uniformly at random in the bounding box.
3. If the point lies inside the shape, return that point. (For a polygon, algorithms that determine this are collectively called point-in-polygon predicates.) Otherwise, go to step 2.

However, there are two things that affect the running time of this algorithm:

1. The time complexity depends greatly on the shape in question. In general, the acceptance rate of this algorithm is the volume of the shape divided by the volume of the bounding box. (In particular, the acceptance rate is typically very low for high-dimensional shapes, in part because of the curse of dimensionality: typical shapes cover a much smaller volume than their bounding boxes.)
2. Also, the algorithm's efficiency depends on how fast it is to determine whether a point lies in the shape in question. Because of this, it's often the case that complex shapes are made up of simpler shapes, such as triangles, circles, and rectangles, for which it's easy to determine whether a point lies in the complex shape or to determine that shape's bounding box.

Note that rejection sampling can be applied, in principle, to sample any shape of any dimension, not just convex 2-dimensional polygons. It thus works for circles, ellipses, and curved shapes, among others.

And indeed, a polygon could, in principle, be decomposed into a myriad of shapes other than triangles, one of those shapes sampled in proportion to its area, and a point in that shape sampled at random via rejection sampling.

---

Now, to explain a little about the phenomenon you give in your second image:

What you have there is not a 4-sided (2-dimensional) polygon, but rather a 3-dimensional simplex (namely a tetrahedron) that was projected to 2-dimensional space. (See also the previous answer.) This projection explains why points inside the "polygon" appear denser in the interior than in the corners. You can see why if you picture the "polygon" as a tetrahedron with its four corners at different depths. With higher dimensions of simplex, this phenomenon becomes more and more acute, again due partly to the curse of dimensionality.