0
$\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 convex polygon.

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

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ There are many approaches; one simple one would be accept-reject (generate an enclosing rectangle, and then generate uniform points inside it, keeping any points inside the polygon). You could overlay it with a sequence of strips, and do accept reject in each strip, with each strip being selected in proportion to its area (in effect generalizing the ziggurat method). You could split it into triangles, find the area of each, and then at each iteration select between the triangles in proportion to their area and then place a point uniformly in the selected triangle. $\endgroup$
    – Glen_b
    Commented Aug 29, 2013 at 0:10
  • 2
    $\begingroup$ @Glen_b Those are all great suggestions. Another approach, which I have found practicable, simple to code, and of general application, is to use rejection sampling whenever the polygon occupies an acceptably large proportion of its bounding box and otherwise to split that BB in half along its longer dimension, select one half with probability proportional to the area of the polygon within that half, and proceed recursively. (This implicitly builds an adaptive quadtree representation of a tight envelope around the polygon.) The hardest part is to clip a polygon to a rectangle, which is easy. $\endgroup$
    – whuber ♦
    Commented Aug 29, 2013 at 3:16
  • $\begingroup$ @whuber +1 very nice. That sounds reminiscent of the unimodal adaptive rejection sampling Radford Neal has described (in turn probably based on Luc Devroye's idea for monotonic densities in his book); I came up with the same idea for unimodal densities some years ago but Neal seems to have had the idea well before me; such a unimodal sampler is still unpublished, I believe. That basically involves knowing (or finding) the mode and using step functions as both upper and lower bounds, which are updated on every (presumed costly) function evaluation (lower bounds avoid many evaluations). $\endgroup$
    – Glen_b
    Commented Aug 29, 2013 at 5:40
  • $\begingroup$ @Glen_b Have you seen this [beautiful] answer? stats.stackexchange.com/questions/13630/…. $\endgroup$
    – whuber ♦
    Commented Aug 29, 2013 at 14:32

1 Answer 1

Reset to default
2
$\begingroup$

The spsample function in the sp package for R will generate a random sample of points within a polygon (does not even need to be convex).

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ this is great to know... perhaps I was asking how sp works. $\endgroup$
    – john mangual
    Commented Aug 29, 2013 at 0:34
  • $\begingroup$ @johnmangual, The spsample function has many options to do the sampling in different ways. But I believe that the default method for random sampling in a polygon is rejection sampling as mentioned in the comments above. $\endgroup$
    – Greg Snow
    Commented Aug 29, 2013 at 15:10

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.