Search code examples
performancegeometryscientific-computingcomputation

Determine the points of intersection between N spheres


Just wanted to know what is the best approach (in terms of speed and accuracy) to determine the points of intersection on N spheres (it was asked for two spheres here); wanted to know what would be the best language to do this. More detailed explanation about what I want to do is here.


Solution

  • As near as I can tell, you are asking for the intersection loci of each pair of N 3D spheres. Counting symmetry, there are N * (N-1) / 2 pairs.

    So take each pair. If the distance between centers is greater than the sum of their radii, there is no intersection. (Edit: Or, as @Ben points out, if the distance is less than the difference of radii, there is also no intersection.)

    If it is equal, the intersection is a single point, easily found on the line segment between centers. If it is less, the locus is a circle, not a point.

    To find the center of that circle and its radius, you're going to need to take a plane slice through the two spheres. That reduces the problem to finding the intersection of two circles. For that you need the Law of Cosines.

    Elaborated: Look at that Wikipedia diagram. a and b are the radii of the two spheres, and c is the distance between centers. Use the second-to-last equation and solve for cos(alpha). From that you can easily get sin(alpha). Then b sin(alpha) is the radius of the circle, and b cos(alpha) is the distance to its center. (Note - this doesn't call any trig functions, only sqrt.)

    Once you know the center and radius of the circle of intersection, the circle itself is just in a plane normal to the line segment connecting the sphere centers.

    Beyond that, I'm not really sure what you want.