Determine the points of intersection between N spheres

Just wanted to know what is the best approach (in terms of speed and accuracy) to determin开发者_运维百科e 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.

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.

If i get you right, you want all intersections of at least two spheres from a group of N spheres, right?

If so, this is acually not an easy problem for high performance computing, at least not if you need an accurate solution. This problem is also solved when calculating the "Reduced Surface" of molecules:

http://www.ncbi.nlm.nih.gov/pubmed/8906967

There are several publications on how to efficiently calculate these points and circles, but it is not an easy task. I believe there was a publication to calculating these values with CUDA, but I don't remember the details. Google (Scholar) should be able to help you in this direction.

However, depending on what you want to achieve, there can be easier solutions. So, perhaps you could detail your question?