9
$\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

$\endgroup$
9
$\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
$\endgroup$
  • $\begingroup$ Is this question not a duplicate of the older one you link? $\endgroup$ – Raphael Aug 29 '13 at 14:37
  • $\begingroup$ @Raphael: Related, but more general, I would say. $\endgroup$ – A.Schulz Aug 29 '13 at 14:40
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.

$\endgroup$
  • $\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 Aug 29 '13 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 Aug 30 '13 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 Aug 30 '13 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 Aug 30 '13 at 17:20
3
$\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)$.

$\endgroup$
  • $\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. Aug 29 '13 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 Aug 29 '13 at 12:23
  • $\begingroup$ What if the polygon is guaranteed to be convex? $\endgroup$ – Yuval Filmus Aug 29 '13 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 Aug 30 '13 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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