sample random point in triangle [closed]

Question

Suppose you have an arbitrary triangle with vertices A, B, and C. This paper (section 4.2) says that you can generate a random point, P, uniformly from within triangle ABC by the following convex combination of the vertices:

P = (1 - sqrt(r1)) * A + (sqrt(r1) * (1 - r2)) * B + (sqrt(r1) * r2) * C

where r1 and r2 are uniformly drawn from [0, 1], and sqrt is the square root function.

How do you justify that the sampled points that are uniformly distributed within triangle ABC?

EDIT

As pointed out in a comment on the mathoverflow question, Graphical Gems discusses this algorithm.

Answer 1

You have a map P(r1,r2) from the unit square to your triangle. Choosing r1 and r2 uniformly gives a random point in the unit square. The image in the triangle is distributed according to the Jacobian determinant of the map P, which turns out to be a constant. Therefore the image distribution is also uniform.

Actually, to verify this you only need to check it for one triple of non-collinear points A,B,C. Affine linear maps have constant Jacobian so you can apply one of these to move an arbitrary triple into this standard position without affecting the distribution.

Finally, a word about "why": Consider the triangle as filled out by line segments parallel to the BC side. In the formula for P, the variable r1 selects which segment the point will lie on, while r2 determines where along the segment it will be. For uniformity, all points on a given segment should be treated equally (hence linear in r2). But for r1, since some segments are shorter than others, we need to favor the long segments in order to attain a uniform distribution. The sqrt(r1) in the formula accounts for this.