Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finding intersection points between 3 spheres

Tags:

math

I'm looking for an algorithm to find the common intersection points between 3 spheres.

Baring a complete algorithm, a thorough/detailed description of the math would be greatly helpful.

This is the only helpful resource I have found so far: http://mathforum.org/library/drmath/view/63138.html

But neither method described there is detailed enough for me to write an algorithm on.

I would prefer the purely algebraic method described in the second post, but what ever works.

like image 274
Adam Avatar asked Sep 10 '09 16:09

Adam


People also ask

How do you find the intersection of a sphere?

The intersection curve of two sphere always degenerates into the absolute conic and a circle. Therefore, the real intersection of two spheres is a circle. The plane determined by this circle is perpendicular to the line connecting the centers of the spheres and this line passes through the center of this circle.

How do you determine points of intersection?

When the graphs of y = f(x) and y = g(x) intersect , both graphs have exactly the same x and y values. So we can find the point or points of intersection by solving the equation f(x) = g(x). The solution of this equation will give us the x value(s) of the point(s) of intersection.


1 Answers

Here is an answer in Python I just ported from the Wikipedia article. There is no need for an algorithm; there is a closed form solution.

import numpy                                             
from numpy import sqrt, dot, cross                       
from numpy.linalg import norm                            

# Find the intersection of three spheres                 
# P1,P2,P3 are the centers, r1,r2,r3 are the radii       
# Implementaton based on Wikipedia Trilateration article.                              
def trilaterate(P1,P2,P3,r1,r2,r3):                      
    temp1 = P2-P1                                        
    e_x = temp1/norm(temp1)                              
    temp2 = P3-P1                                        
    i = dot(e_x,temp2)                                   
    temp3 = temp2 - i*e_x                                
    e_y = temp3/norm(temp3)                              
    e_z = cross(e_x,e_y)                                 
    d = norm(P2-P1)                                      
    j = dot(e_y,temp2)                                   
    x = (r1*r1 - r2*r2 + d*d) / (2*d)                    
    y = (r1*r1 - r3*r3 -2*i*x + i*i + j*j) / (2*j)       
    temp4 = r1*r1 - x*x - y*y                            
    if temp4<0:                                          
        raise Exception("The three spheres do not intersect!");
    z = sqrt(temp4)                                      
    p_12_a = P1 + x*e_x + y*e_y + z*e_z                  
    p_12_b = P1 + x*e_x + y*e_y - z*e_z                  
    return p_12_a,p_12_b                       
like image 167
Andrew Wagner Avatar answered Sep 24 '22 16:09

Andrew Wagner