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.
Accept-flip
There is a clever variation on the accept-reject method. Create a parallelogram by attaching a flipped copy of the triangle. Now randomly sample from the parallelogram. Every sample point will either land inside the original triangle or in its flipped twin. If it landed in the original triangle, keep it. If it landed in the twin, flip it back over and use that point.
This is like an accept-reject method, except there’s no waste. Every point is kept, possibly after flipping.
You can find code for implementing this method on Stack Overflow.
Related posts
The post Randomly selecting points inside a triangle first appeared on John D. Cook.