Quote:
Originally Posted by Greg Woelki
Can anyone think of another general way of generating a random point in an n-gon that is more efficient than mine for small values of n (without sacrificing significantly for larger values of n, of course)? When n=3, my program is discarding almost 60% of the points it generates.
|
1. Generate a random point (xrand,yrand) within a unit square.
2. If xrand+yrand is greater than 1, use the point (1-xrand, 1-yrand) instead. You will now have a point within a right triangle of unit width and height that I will call (x, y).
3. Determine the apothem a and the perimeter p of your regular n-gon.
4. Regular n-gons are made up of n isosceles triangles which have a base width of p/n and a height of a. Each of these isosceles triangles is made up of 2 right triangles of width p/(2n) and height a. Take your point (x, y) and scale it accordingly to a right triangle described above, to get a point (x*p/(2n),y*a).
5. Randomly decide if this point will be on the left or the right half of an isosceles triangle (you could even use the leftover data from part 2 if you don't want to generate another random number).
6. Randomly decide in which of the n isosceles triangles your point should go.
100% of these points will be within your regular n-gon, and the distribution will be uniform.
Given, you do need to generate at least 3 random numbers for this process, so if generating random numbers is resource intensive you may want to look for other methods.