10
$\begingroup$

I would like to sample a uniformly random point in a polygon...

If sample a large number they'd be equally likely to fall into two regions if they have the same area.

This would be quite simple if it were a square since I would take two random numbers in [0,1] as my coordinates.

The shape I have is a regular polygon, but I'd like it to work for any polygon.

https://stackoverflow.com/questions/3058150/how-to-find-a-random-point-in-a-quadrangle

Improve this question
$\endgroup$

3 Answers 3

Reset to default
10
$\begingroup$
  1. Triangulate the polygon
  2. Determine in which of the triangles the point should lie (weights triangle areas)
  3. Sample the point in the triangle as explained in this post
Improve this answer
$\endgroup$
3
  • $\begingroup$ Is this question not a duplicate of the older one you link? $\endgroup$
    – Raphael
    Commented Aug 29, 2013 at 14:37
  • $\begingroup$ @Raphael: Related, but more general, I would say. $\endgroup$
    – A.Schulz
    Commented Aug 29, 2013 at 14:40
  • $\begingroup$ I just googled this question after watching a robotics video on Rapidly-exploring random tree, and now I am puzzled. Because if I have a triangulation of my map, I don't see why I would do anything other than route on the triangulated graph. $\endgroup$
    – nraynaud
    Commented Dec 10, 2020 at 19:25
4
$\begingroup$

One easy way is to find the bounding box for your polygon and use rejection sampling: sample from the bounding box and accept if it falls within the polygon, which will happen with probability $1/2$ at least (I think).

Another possibility is to triangulate your polygon. First sample a triangle in a proportionate way, then sample a random point in the triangle. The latter is simple: up to affine transformations, all triangles are of the form $\{(x,y) : x,y \geq 0, x+y \leq 1\}$. To sample uniformly a point from that distribution, first sample $x \in [0,1]$ according to the density $2(1-x)$ (i.e. sample a uniform $r \in [0,1]$ and compute $x = 1-\sqrt{1-r}$) and then sample $y \in [0,1-x]$ uniformly (i.e. sample a uniform $s \in [0,1]$ and compute $y = (1-x)s$). An even simpler method is to sample $x,y \in [0,1]$, and if $x+y > 1$ replace $(x,y)$ with $(1-x,1-y)$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Rejection sampling will reject with probability at most 1/2 in 2 dimensions, but in higher dimensions the probability of rejection might be much worse. $\endgroup$
    – D.W. ♦
    Commented Aug 29, 2013 at 7:27
  • $\begingroup$ Rejection sampling might have a larger rejection rate than 1/2. Just think of a spiral, slightly extruded. $\endgroup$
    – A.Schulz
    Commented Aug 29, 2013 at 12:23
  • $\begingroup$ What if the polygon is guaranteed to be convex? $\endgroup$
    – Yuval Filmus
    Commented Aug 29, 2013 at 14:07
  • $\begingroup$ If your bounding-boxes are axis-aligned, then convexity is no help; as the answers to the previous question suggest, just consider a triangle with vertices at (0, 1), (1, 0) and (x, x) for very large x - this will take up a vanishingly small proportion of its bounding box as x goes to infinity. If you're talking about the smallest possible bounding box then you can probably derive bounds on the volume your convex shape takes up, but then you have to find the box... $\endgroup$
    – Steven Stadnicki
    Commented Aug 30, 2013 at 16:27
4
$\begingroup$

This is a little crazy, but should work well even if your polygon is very weird.

Use the Reimann mapping theorem to find a conformal map from the unit disc to your polygon, viewing it as a subset of $\mathbb{C}$. See, for example the references in:

http://siam.org/pdf/news/1297.pdf

Then use the pushforward of a uniform density on the disc as the proposal density in Metropolis-Hastings MCMC sampling.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Conformal maps aren't necessarily area-preserving, though; they're angle preserving, but this is almost guaranteed not to sample the polygon uniformly. $\endgroup$
    – Steven Stadnicki
    Commented Aug 29, 2013 at 22:49
  • $\begingroup$ Thus the need to use it as a proposal in MCMC, not as an actual sampler. With the Poincare inequality you can show the variation of a conformal map from uniform is bounded by a constant. $\endgroup$
    – Nick Alger
    Commented Aug 30, 2013 at 14:50
  • $\begingroup$ I'm perhaps still missing it; the discussion on the pointed-to Wikipedia page says that the 'trial distribution' still needs to be directly proportional to the desired distribution; i.e., not $aP(x)\lt f(x)\lt bP(x)$ for some constants $a$ and $b$, but $f(x) = cP(x) \forall x$. Local variance in the mapped density will still lead to local variance in the sampling. $\endgroup$
    – Steven Stadnicki
    Commented Aug 30, 2013 at 16:24
  • $\begingroup$ The whole point of Metropolis Hastings MCMC is that the proposal isn't the true distribution. Convergence speed of the MCMC chain depends on how well the proposal approximates the true distribution. The most common proposal is putting a gaussian at the current point, regardless of the distribution you are trying to sample... $\endgroup$
    – Nick Alger
    Commented Aug 30, 2013 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.