Timeline for random sampling in a polygon
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2017 at 12:39 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| Aug 29, 2013 at 14:32 | comment | added | whuber♦ | @Glen_b Have you seen this [beautiful] answer? stats.stackexchange.com/questions/13630/…. | |
| Aug 29, 2013 at 5:40 | comment | added | Glen_b | @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). | |
| Aug 29, 2013 at 3:16 | comment | added | whuber♦ | @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. | |
| Aug 29, 2013 at 0:18 | answer | added | Greg Snow | timeline score: 2 | |
| Aug 29, 2013 at 0:13 | review | First posts | |||
| Aug 29, 2013 at 0:36 | |||||
| Aug 29, 2013 at 0:10 | comment | added | Glen_b | 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. | |
| Aug 28, 2013 at 23:56 | history | asked | john mangual | CC BY-SA 3.0 |