The red circle is the ''max total spread''. The yellow circle is the ''min delta spread'' and the green circle is the ''max delta spread''. I need to find a way to get a random point in the dark blue region with uniform distribution over the area. Also, because this is being implemented in a scripting language, fewer, simpler math operations are better (and just randomly generating points uniformly in between the spread circles until it falls inside the blue area isn''t an option).
I already know how to get the points where the spread circles intersect the total circle, but I''m not sure how to use that to help me.
Uniform Distribution in Circle Intersection
Author
I''m working on some aiming code for an FPS mod, and I need some help figuring out how to get it to be a uniform distribution.
The spread of bullets is calculated using 3 circles: one circle is the ''max total spread'' that is centered on the ''origin''. A second circle is the ''min delta spread'', which is centered on where your last bullet went, and the third circle is the ''max delta spread'' also centered on where your last bullet went.
I need to figure out how to get a random point between the delta spread circles such that there will be uniform distribution. This I think I can find on my own because I know its been discussed here before, so on to my real problem:
The red circle is the ''max total spread''. The yellow circle is the ''min delta spread'' and the green circle is the ''max delta spread''. I need to find a way to get a random point in the dark blue region with uniform distribution over the area. Also, because this is being implemented in a scripting language, fewer, simpler math operations are better (and just randomly generating points uniformly in between the spread circles until it falls inside the blue area isn''t an option).
I already know how to get the points where the spread circles intersect the total circle, but I''m not sure how to use that to help me.
The red circle is the ''max total spread''. The yellow circle is the ''min delta spread'' and the green circle is the ''max delta spread''. I need to find a way to get a random point in the dark blue region with uniform distribution over the area. Also, because this is being implemented in a scripting language, fewer, simpler math operations are better (and just randomly generating points uniformly in between the spread circles until it falls inside the blue area isn''t an option).
I already know how to get the points where the spread circles intersect the total circle, but I''m not sure how to use that to help me.
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]
[edited by - uber_n00b on May 29, 2004 1:54:51 AM]
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]
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]
Author
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 =-)
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.)
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
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
Author
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:
where random returns a real in [0, 1]
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
