Picking a Random Uniformly Distributed Point in a Circle

Started by
1 comment, last by clb 8 years, 9 months ago

A short article tI wrote that attempts to give a little insight into how this is done mathematically.

http://xdpixel.com/random-points-in-a-circle/

RandomPointInCircleComparison1.png

xdpixel.com - Practical Computer Graphics

Advertisement
Seems very well written. Have you considered submitting it as an article to this site:

How to Publish on GameDev.net

For some random sampling problems, rejection sampling ends up being the fastest and most elegant solution in practice. Related to this, the article states

You can use a while loop if you prefer but there is no way to know how long this operation will take. This might be acceptable if you are using the box method during an initialization process but if you need to pick random points in a circle per frame or in an update loop, there are much better ways of doing it.

however I would have liked to see a proof of why using a square root is better than using a loop. The first intuition is most often, like presented in the article, that the loop must be slow, since there's no way to know how many iterations it will take, but in practice, the probability that one takes e.g. more than 20 iterations is A(box)/A(circle)^20 = 1/ ( pi * 0.25)^20 < 0.8%, and the rate diminishes here very fast. It is not immediately obvious that using a square root is faster than using a loop which most of the time takes very few iterations, so it would be nice to see a practical benchmark to prove the superiority of the square root.

There exists other distributions which can be analytically reshaped from the uniform distribution like shown here, but very often they end up too complicated at runtime that simpler iterative methods outrun them in performance.

One practical remark on using rejection sampling, not just to solve this problem but in general, is that it is a good idea to have a fail-safe max number of iterations, e.g. 1000 or similar, instead of blindly doing a for(;;), in the case if there is a chance that the program will later be worked to interoperate with unknown random number generators, that might have a bug and generate faulty rng streams under some conditions (e.g. generating the same number again and again, like a stream of zeroes or similar), or perhaps if (external) calling code has a bug that one passes in a circle radius of 0 or negative, or something alike.

This topic is closed to new replies.

Advertisement