Comments on How can I choose a point from a uniform distribution within a regular polygon?
Parent
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.
Post
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.
0 comment threads