2
$\begingroup$

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:

enter image description here

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

enter image description here

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.

$\endgroup$
  • 2
    $\begingroup$ This is a copy from a question I asked on Stack Overflow. After posting, I realized it was not the best place for this kind of question but found no way to move it here other than pasting. Sorry if this is not the proper way to proceed. $\endgroup$ – Xav59130 Sep 8 at 9:32
  • 1
    $\begingroup$ "found no way to move it here other than pasting" -- ideally, you'd flag it and ask for it to be migrated; that should usually work, $\endgroup$ – Glen_b Sep 8 at 9:42
  • $\begingroup$ Feels weird I must ask someone to move my own question but no problem, I will do this way next time it happens. Thanks for the tip ! $\endgroup$ – Xav59130 Sep 8 at 13:12
  • $\begingroup$ A triangle is a simplex; the other figure is not. That's the heart of the matter. $\endgroup$ – whuber Sep 8 at 15:17
  • $\begingroup$ I understand this but why such sampling does only work with simplexes ? $\endgroup$ – Xav59130 Sep 8 at 22:47

Your Answer

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

Browse other questions tagged or ask your own question.