The best algorithm to generate a point in a circle is to generate a point in a square with the same width as the circle diameter and then rerun the algorithm until this random point is inside the circle. This algorithm might need to run a couple of times before finding a suitable point but will be faster than a more algorithmic solutions.
Pseudo code:
- Randomize a point in the square
- If this point is outside the circle then jump to 1
- Done
I’m no CS expert, but what’s wrong with:
angle = rand(0, 360)
dist = rand(0, circle_radius)
random_pos = pos( sin(angle) * dist, cos(angle) * dist )
??
That would give you an uneven distribution. (more samples closer to the center) And sin and cos instructions are slow.
IMHO, the method you propose is a dangerous one!
I’ll try to explain in brief.
First of all, the probability to get a point outside the disk,
using this way, is about 0.21 (which is quite much).
Now, the problem is that there is no real “randomize” on our
computers. All we have is pseudo random functions (which depend
on the clock). Because modern CPU’s are so good at branch prediction
and caching instructions, one could end up in a very long loop (between step 1 and step 2), because of the patterns to appear when
sampling the clock (direct influence of branch prediction).
Of course this all depends on the quality of the RNG function,
which, unforutantely, in the stanrdad implementation are quite
lacking.
A more “correct” solution might be to generate these two:
angle=uniform(0,2*pi)
r=R*sqrt(uniform(0,1))
Where ‘R’ is the radius of the original disk.
Then:
x=r*cos(angle)
y=r*sin(angle)
It might be a bit slower (not too much though, as all the functions
can be computed very efficiently), but it’ll avoid the looping.
if we want to find the fastest solution and doing sin, cos, sqrt etc. needs to be as minimal as it can be.
Max’s solution isnt the best one here, as it uses all three of those costly functions – and it’s bad. If you dont want to use the loop, then go for the algorithm that SomeGuy told us here:
angle = random(0, 360);
dist = random(0, circle_radius);
x = cos(angle) * dist;
y = sin(angle) * dist;
Or even try my better(not the best) solution, where only one costly function is used:
(where R – given radius):
r = random(0, R);
x = r*random(-1, 1);
y = r-2*sqrt(r*r – x*x);
any better implementations?
mini, SomeGuy’s solution has non-uniform distribution (it’ll
produce more points near the center), as Robert already noted.
May I also remind you, that sin and cos can be computed
simultaneously up to a very good precision while using
only six multiplications.
As for your solution, I didn’t look much into it, but
I’m quite sure that it has non-uniform distribution.
It depends on what your random functions are, just use Mersenne twister pseudo-random number generator and you wont have any problems. The non-uniform things can be dealt with.
The best is asking a Mathematician
http://mathworld.wolfram.com/DiskPointPicking.html
Second, if you want to use that in a Montecarlo simulation (Ask an Engeneer) and he/she’ll probaby respond: use Mersenne Twister (periodicity of any sequence is about 2^19937 iterations, nice, VERY nice). Also (and obvious) won’t appear the unpleasant Marsaglia Effect.
And last, the method that the author has posted is the BASIS of the russian roulette that’s perfect when multidimensional analisis is required, i.e. BRDF of four, five or even six dimensions.