How can I choose a point from a uniform distribution within a regular polygon?
Suppose I have a regular polygon in the Cartesian plane, centered at the origin with circumradius $1$, aligned with one vertex at $(1, 0)$. Given a source of independent, uniformly distributed random variables on $[0..1)$, how can I choose a point within the polygon, randomly, with uniform distribution, using only finitely many inputs?
Is this possible for all regular polygons or only for certain numbers of sides? (Of course the square case is trivial.)
I cannot use rejection sampling within a bounding area (e.g. the unit square) as this requires an unbounded (heh) number of random selections.
I know that a random point can be chosen inside a circle by randomly choosing an angle (mapping one input to $[0..2\pi)$) and distance from the origin (taking the square root of the input variable to correct for the bias). However, this doesn't seem to work for polygons; if I scale the chosen "radius" to fit within the polygon, the result will then show a bias towards the perpendicular bisectors of the sides (and away from the lines connecting the centre to the edges - for the same reason that the square-root correction was necessary).
This question is inspired by a recent Stack Overflow question. I believe I have an answer, but I would prefer to let others offer an answer first.
2 answers
The following users marked this post as Works for me:
| User | Comment | Date |
|---|---|---|
| Karl Knechtel | (no comment) | Aug 28, 2023 at 16:07 |
Any convex polygon can be trivially tiled into triangles. Choose any point on the boundary or inside the polygon and draw lines from there to all the vertices. This point can be one of the vertices. It can also be the origin in your case. It doesn't matter what point is picked.
Find the area of each triangle. For each random point, choose a triangle biased by its area, then randomly find a point within that triangle.
One simple way to do the latter conceptually is to transform the triangle into a space where it extends between (0,0) (1,0) (0,1). Pick any point in the (0,0) to (1,1) square. If it happens to be outside the triangle, reflect it back inside. Either the original point or its reflection will be in or on the triangle.
A (regular, convex and some weaker condition would be sufficient) polygon is a finite union of triangles with one vertex at the origin, and which only meet at their edges. (I am being ambiguous whether I consider the triangles as closed or open, but this almost surely does not make a difference.)
In case of a regular polygon, the two sides that touch the origin are equally long, even, and in the case presented in the question this side length is one and all the triangles are congruent.
That is to say, the question reduces to finding a uniformly random point in a triangle, or maybe even a triangle with extra properties. For an isosceles triangle with height h, we can choose a random height from a linear distribution that has value zero at the origin and a known value (that is uniquely determined by linearity and the total probability being one) at the wide end, and then consider a uniform distribution at the selected height.
(Bedtime and this response is CC-zero licensed, so details can be added by anyone.)
0 comment threads
0 comment threads