How could I get the random point in the cross area between two circles?

I want to get the random position in the cross area between two circles.
I have the middle position and radius of two as the shadow area in the picture attached.
Anyone has an idea?
Thank.

 

http://math.stackexchange.com/quest...ind-the-points-at-which-two-circles-intersect

I would probably find the points where the two circles intersect as a starting point.

You can find the widest points by taking the direction between the two points, and translating along the direction by the radius for each circle.

My maths isn't the strongest, but that's gotta be a good start. You can at least get 4 solid reference points and get random points between those.

 

hmm I don't know what you're trying to do

you should know something about Integrals and surface that 2 functions are 'bounding'

but if you want to eg. spawn unit at random point in intersection of ranges between two points
you can do it on redneck way:
1) Randomly spawn unit at one circle
2) if OTHER circle doesn't contain spawned unit then move unit to random point inside of FIRST circle
3) loop this until unit is inside of
both circles

 

What majmun said.

If you are randomly and evenly distributing points in a circle,you are probably already doing a "pick a random point and discard if not in the circle" strategy. Just extend this method to keep going till you find a point in both circles.

Oh and do this for the smallest circle - it will find a valid point quicker.

 

Calculate the angle1, angle2 and r3.

- Step1: Get random angle between angle1 angle2
- Step2: Get random radius value between r3 radius1
- Step3: From random angle, radius --> new point
- Step3: Calculate distance d = newpoint Point2, if d > radius2, Go back to Step1, if not --> done :wink:

 

Also remember to check the circles do overlap so you don't end up in a loop you can't get out of!

 

Thanks all. But I think these solutions are a little expensive. I had this idea at first.
If there is a math solution like 'Frieza' said would be perfect.

 

Have you thought of creating a circle inside that intersection?

And then create a random point in that circle.

Good part: it is random + no loops required.
Bad part: it will never be a point in the extreme corners of that intersection.

 

I would do what Frieza said, use those 4 points to "create" an ellipse. Then figure out a point in that.

http://forums.xkcd.com/viewtopic.php?f=17&t=51871

 

I think I'd:

-- find the formula for the intersection points P1=(x1,y1), P2=(x2,y2) by the method outlined in Frieza's link
-- draw a line between P1, P2, separating the shape into two 'turtle shells'
-- find the turtle shells' areas
-- sample from the two turtle shells using polar coordinates, treating them like arcs cut out of circle: http://www.anderswallin.net/2009/05/uniform-random-points-in-a-circle-using-polar-coordinates/ (although, now that I think about it I'm not sure the 'turtle shells' can be handled in this way, since they're not of constant radius...)
-- weight the probability you use a point from each turtle shell by that shell's relative portion of the total area of the two turtle shells summed together

edit:

Alternatively, I doubt rejection sampling would be all that expensive computationally if you used the intersection points P1, P2 and a bound on the diameter of the intersection area to pull initial, random points from a rectangle or diamond made to bound the intersection area as closely as possible. Something like this with a rectangle could work like:

-- Find the intersection points P1, P2
-- In the two directions determined by the line connecting the circles' centers, find how wide the rectangle should be; if D (= r1 + r2 - length_of_overlap) is the distance between the circles' centers, this should be W1= r1/(r1+r2) * (r1+r2-D) and W2 = r2/(r1+r2) * (r1+r2-D), where r1+r2-D is the length of the overlapping segment in the intersection
-- Draw a rectangle of width W1+W2, with W1 and W2 being the sub-lengths extending out from P1,P2 in the appropriate directions; length of the rectangle is the distance between P1, P2 of course
-- Randomly sample from this rectangle, reject if the inequalities determined by the two circles' equations are not simultaneously satisfied

 

I think this is a pretty good idea, to take it further, stretch the circle along its local vertical axis.



It's not quite perfect, but works reasonably well
It's either using the chord length (s), or the approximation is a guess using (0.3 / (p1p2 / (2 * r2) ) ) + 0.7

https://dl.dropboxusercontent.com/u/157182894/Builds/test/Circles/Circles.html

 

Hmmm just had another idea, but havent tested any code, so I dont know how well it woould work, or how even the distribution is



choose a random y beween ymin and ymax, put the chosen y into the circles equations to get xmin and xmax, then choose a random x.... simple?

 

Well I came to a stop wen i realised that determining the xalues for xMin, yMax, etc, isn't so simple, but i came up with a third solution.
Get a random value (eg. 0.4), get a point on each arc 40% along, then a second random along the connecting line.
It now generates points only within the intersection, but there is a slight bias as shown in the second image, when one arc is significaly shorter than the other, poits more often come near the short side, but only slightly, and only really happens when one circle is significaly larger than the other.

https://dl.dropboxusercontent.com/u/157182894/Builds/test/Circles/Circles.html

 

Hmmm acutally i just noted that you get bias in the corners too. Again, probably fixable by not using a uniform RNG value

 

I came up with a pretty interesting idea for this. Here's what we got:
a: center of first circle
b: center of second circle
c: first intersection point of circles
d second intersection point of circles

Calculate the angle created by the vectors ab and ad. This is your max angle.
Calculate the angle created by the vectors ab and ac. This is your min angle.
Randomize an angle in between these two. Use this to determine a point on the acd arc.
Calculate the max angle at babd, as well as the min angle at babc
Randomize an angle between these to and determine a point on the bcd arc.
Randomize a point between these two

Not sure how effective this solution is, but it should work