In the first post of this series, I discussed a method to generate a random (guaranteed) permutation. On another occasion, I presented a method to recycle expensive random bits. Today, I will discuss something I had to do recently: generate random points inside a triangle.
Let us start by a rectangle. If I want to generate cloud of random dots in a rectangle, you would be easily convinced that generating pairs of (pseudo) random numbers, one for each coordinate, is quite sufficient. Let be a (pseudo) random function that returns a (pseudo) random number such that . So for a rectangle of height and width , a cloud of points generated by would look quite (uniform) random.
But what if we have, say, a triangle? It’s not quite easy, but it shouldn’t be too hard. At first, we could think that it suffices to compute the triangle’s bounding box and use the rejection method: we draw random points inside the rectangle and if a random point falls outside the triangle (while being inside the rectangle) it is rejected and we try again. This method is good if the triangle to rectangle surface ratio is good, but disastrous if the triangle is very small compared to its bounding rectangle. Say, something like:
So this first solution is not very good. A much better solution asks for some linear algebra, but not much, be assured. Let us say we have a triangle like the following:
The two arrows, or vectors, can be determined easily: take any corner as the common base, and draw them to opposite corners (in fact any two vectors in any order will do, but for clarity here, let us consider that they form a corner as in the above picture). These two vectors form, if they are different, a vector space basis. The space here is in fact only a plane, the plane in which the triangle lies. Let and be those two vectors.
Now, let’s generate random points in the triangle. The two vectors and generate the parallelogram:
but only the darker gray region is our triangle; the pale region is to be ‘rejected’. Now: let and be the vectors and their components. Let also be a random point in a unit square. This point can be mapped in the parallelogram using the following transform:
The parallelogram is therefore a sheared and scaled version of the unit square and are the x,y coordinates of the random point within the parallelogram. But we want only inside the original triangle!
We can now use rejection in the original unit square to make sure we only yield points in the triangle: we can reject all pairs with , since they will be mapped in the second (pale gray) triangle. We then draw random pairs until we get , and then use the above transform to map it into the triangle.
It doesn’t take long to get a Mathematica implementation running. (I suppose you could do the same with C and Gnuplot, only it’s not as immediate.) My implementation for two random vector and yields the following cloud of points:
And we see that the points are uniformely distributed, showing (approximately) equal density everywhere in the triangle.