#### Archived

This topic is now archived and is closed to further replies.

# Uniform Distribution in Circle Intersection

This topic is 5288 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

##### Share on other sites
The only way I can see doing it is dividing the circle up into pieces such that the function (or functions) describing each piece is/are continuous, and then randomly picking an x between the intersection of the green/red circle on the right and the leftmost point on the green circle, and then picking a y according to the piece corresponding to the x value. It all sounds so costly to me (speed-wise). Am I making any sense? I'll be more than happy to draw a picture. Sorry I can't be of more help though. This topic sure ain't easy.

[edited by - uber_n00b on May 29, 2004 1:54:51 AM]

##### Share on other sites
You say a uniform distribution in a square isn't an option, but I really don't see why. The expected value of the number of attempts will be around 2 or less if the square is around the medium sized circle. The tests are also very quick. Otherwise, you'll have to change coordinate systems. One coordinate will be the radial bit around the last bullet. The other will be substantially more complicated. Then you can work out the inverse Jacobian and use that function, or something like that. I can tell you now it will not be pretty and will be very costly as in time.

I'm pretty certain there are no other ways, maybe you could have a uniform distribution in a different shape, so it 'hugs' the intersection you want more. The obvious one for this would be the 'donut' shape. The majority of the time it will be within the big circle anyway, and only requires one(very quick) test.

Of course there's no reason the distribution has to be perfect. You maybe able to find a good approximation.

[edited by - Higherspeed on May 29, 2004 6:45:45 AM]

##### Share on other sites
Truely just generating a point in the square and testing it might be acceptably fast, but I''d really like to know if there is another way just for curiosity''s sake =-)

##### Share on other sites
Think of it topologically. Generating a uniform bivariate distribution in a unit circle, given access to a random number generator with only a univariate uniform distribution is roughly analagous to the squaring the circle problem. At least any method I can think of that involves not rejecting generated numbers based on a fitness criterea maps onto the squaring the circle problem. (Or actually generates a non-uniform bivariate distribution.)

##### Share on other sites
It''s the intersection with the red disk that is the killer.

More efficient than generating points inside the square would be to generate points inside the green circle (outside the yellow circle) and then reject any outside the red circle.

John Bolton
Page 44 Studios
Current project: NHL Faceoff 2005 PS2

##### Share on other sites
I think I''ve worked out how to get a point in the ''donut area'' properly and it looks uniform when I generate points. In case anybody finds this thread when searching for such an algorithm:
a = random_angle()v = (INNER_RADIUS / OUTER_RADIUS)2d = sqrt(random() * (1-v) + v) * OUTER_RADIUSx = d * cos(a);y = d * sin(a);

where random returns a real in [0, 1]

1. 1
Rutin
49
2. 2
3. 3
4. 4
5. 5

• 10
• 28
• 20
• 9
• 20
• ### Forum Statistics

• Total Topics
633409
• Total Posts
3011722
• ### Who's Online (See full list)

There are no registered users currently online

×