If you have a triangle with vertices A, B, and C, how would you generate random points inside the triangle ABC?
Barycentric coordinates
One idea would be to use barycentric coordinates.
Generate random numbers α, β, and γ from the interval [0, 1]. Normalize the points to have sum 1 by dividing each by their sum. Return αA + βB + γC.
This generates points inside the triangle, but not uniformly.
Accept-reject
Another idea is to use an accept-reject method. Draw a rectangle around the triangle, generate points in the square, and throw them away if they land outside the triangle.
An advantage to this method is that it obviously works because it doesn’t rely on anything subtle. Three cheers for brute force!
The method is fairly efficient; on average only half the points will be rejected.
A disadvantage to all accept-reject methods is that they have variable runtime, though this only matters in some applications.
... continue reading