Obviously, the box method(mine :D ) has equal prob for each point...

Besides, it has very high resolution, since you guys are working with floats...Say we want a circle @ radius = 10000 or so...

And mine must be WAAAYYY faster than the other one, since my method only involves multiplication, addition and subtraction...

quote:

---

Original post by kmsixpence
I''m not up on all the mathmetics, but i got and idea and maybe it was already there but here''s what i thought of. find a random angle between 0-360. Find a random radius based on the total radius of the circle. Use that information to find the x/y pos.

---

That has allready been done...That´s number 1.

quote:

---

Original post by Tjoppen
Obviously, the box method(mine :D ) has equal prob for each point...

Besides, it has very high resolution, since you guys are working with floats...Say we want a circle @ radius = 10000 or so...

And mine must be WAAAYYY faster than the other one, since my method only involves multiplication, addition and subtraction...

---

Not true. Your method involves testing the random point to see if it is within the circle. Because the point is being randomly generated, there is no way that the processor can predict this branching. A square root takes far less cycles than a mispredicted branch on modern systems IIRC, so your method is probably not as fast as you think.

And for increasing radii, the area inside your box but outside the circle will become larger as well. So the probability of having to create a new random point gets larger as well.

I don''t think the increased resolution will really pay off here. Besides, doing the sqrt method on doubles will probably still be faster than your method.

I''m not trying to cast you down or anything, just setting the record straight.

Aw, shoot...

Well, it´s not like I didn´t see it coming

quote:

---

said Scarab0,
"And for increasing radii, the area inside your box but outside the circle will become larger as well. So the probability of having to create a new random point gets larger as well.

I don't think the increased resolution will really pay off here. Besides, doing the sqrt method on doubles will probably still be faster than your method."

---

I don't really want to bother with the math, but the odds are incredibly higher that you'll find a point in the circle than you will in the surrounding square sections that the points you're making are pretty much moot. Prove me wrong.

Later,
ZE.

P.S. (EDIT) As a clarification, as the size of the radius goes up, the sizes of the circle and the square stay in proportion, so your first point is particularly wrong.




Edited by - ZealousElixir on January 2, 2002 6:15:24 PM

Areas:
A_box = (2r)² = 4r²
A_circle = pi * r²

Probability of circle:
P_circle = A_circle / A_box =(pi * r²) / 4r² = pi/4

Probability of outside circle:
P_outside = 1 - P_circle = (approx) 0.214601836602551690384339154180124

In short, a little over one out of every five times you'll miss the circle and hit the box.



Edited by - TerranFury on January 2, 2002 6:33:31 PM

I always use the box (or cube) technique for generating 2D or 3D random coordinates. Nothing looks stupider than rectangular explosions.

For completeness, why don''t we go ahead and benchmark the various techniques. BH, you did a great job with the visual comparison. Why not crank it up to a few million samples to see which is fastest?

Okay... drawing 1,000,000 points in a circle of radius 80.

Angle / Magnitude method: 3.329 seconds
Null & Void''s method: 3.364 seconds
The box method: 2.913 seconds
My method: 3.355 seconds

But, if we use the FSINCOS instruction...

Angle / Magnitude method: 2.726 seconds
Null & Void''s method: 2.802 seconds
The box method: 2.913 seconds (no change)
My method: 2.843 seconds

Gasp! Out of the two methods that work, me = teh win!
HAAHAHHAHHAH!!!1211 I AM SO POWERFUL!!112
Now you must bow down and worship me.

I''m too lazy to work out a 3d equivalent right now, though...

And your user will praise you. This program is .04 seconds faster than that one. It use to take me three seconds before I switched and now it, um, takes three seconds

Stop it with the sarcasm and get back to worshipping me!