For the past two weeks I have been pondering on and off how I would calculate the location of the intersection of two spherical circles. I really want Spheriosity to be as complete as possible and having the intersection tool only work on Spherical lines/line segments seems like a real lame idea. So I have finally devised an algorithm which can correctly determine the intersection points. I will give a brief overview of it here. I will leave out details about different parts of the algorithm which I feel are either trivial or would need their own blog post to explain ;).
So we start with two circles… What are the possibilities for their arrangements in terms of intersections:
- The most simple is if the circles are not anywhere near each other and don’t intersect.
- One circle could be “inside” the other. In this case the circles obviously do not intersect.
- The two circles could intersect only in one spot. This could happen in a number of ways:
- Case 1:
- Case 2:
- Then there is the case where the circles intersect twice. This is perhaps the most common case in terms of what users will see, but since the other cases are easy to construct we must also deal with them.
So that loosely describes my problem and the different scenarios that need to be considered. So… on to the solution! Much of this boils down to finding the intersection of two planes. Each circle on the sphere defines it’s own plane which basically slices the sphere, and the intersection of that plane and the sphere could also be used to form the circle. So the intersection of the planes formed by both circles forms a line which, if it goes through the sphere, can be used to find our points of intersection.
Defining that line of intersection turned out to be the largest problem. It was easy enough to get a vector going in the correct direction but I still needed a point to form the line and perform any sort of calculation on it. Here are the steps I take to find the intersection and make sure one actually exists:
- Consider two circles AB and CD (defined by center point and radius point).
- Find the normal vector to the planes formed by each circle. We will call these vectors a and c
- Take a x c if the magnitude squared of the resulting vector is 0 you can stop now because the planes are parallel, and the circles could not possibly intersect (or are coincident).
- Form an axis of rotation, r, between points A and C.
- For both circles form lines by rotating their respective center points forward and back by the angle formed between their center points, the center of the sphere, and their radius points. (call these lines l and m.
- Find the intersection of lines l and m and call this point I
- Find the intersection of the line formed by using point I and the cross product of a and c with the sphere.
- Consider the following cases:
- Case 1: Line does not intersect the sphere: no intersection points
- Case 2: Line intersects once with the sphere: one intersection point
- Case 3: Line intersects twice with the sphere: two intersection points
There you have it! I know I left some details out, but writing out every single step would make this a really long post ;).