19

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.

Community
  • 1
  • 1
dsg
  • 12,924
  • 21
  • 67
  • 111
  • 2
    This is probably better suited for http://math.stackexchange.com/ – Null Set Jan 24 '11 at 02:54
  • http://math.stackexchange.com/questions/18686/uniform-random-point-in-triangle – dsg Jan 24 '11 at 04:02
  • 3
    I think its perfectly fitted for SO. Voting to reopen. Numerical methods fit here quite well, and if you're going to do something like Monte Carlo, better be sure you can justify your assumptions. – Dr. belisarius Jan 24 '11 at 04:03
  • @belisarius: The question was not about a numerical method, but about a mathematical proof. I don't think it's completely off-topic here, but I think it is even more on-topic where it is now. – Sven Marnach Jan 24 '11 at 11:48
  • 2
    @Sven You may be right, but I see the scope of SO narrowing on a daily basis. I am afraid in the near future the only valid topics will be some syntax issues and applications of well known algorithms. Thanks for your opinion. – Dr. belisarius Jan 24 '11 at 11:56
  • @belisarius: I see this problem as well. I will keep your words in mind when deciding whether I vote to close in the future :) – Sven Marnach Jan 24 '11 at 12:05
  • Common algorithm for computer programmers, vote to reopen – bobobobo Oct 02 '12 at 02:57

1 Answers1

12

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.

David
  • 236
  • 2
  • 2
  • 3
    How does the sqrt(r1) account for the variation in the lengths of the line segments? – dsg Jan 24 '11 at 04:14
  • 1
    @dsg, if we write `(1-x)A + x[(1-y)B + yC]`, from simple geometry it can be seen that a narrow strip of height `dx` parallel to BC has the area `dS ~ x dx ~ d(x^2)`. Hence, to obtain the uniform distribution of points, `x^2` should be uniformly distributed. To obtain `x` from `r1 = x^2`, you take `sqrt(r1)`. – Evg Mar 06 '20 at 21:53