在3个球体之间找到交点。

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

我在寻找一个算法来找出3个球体之间的公共交点。

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

这是我迄今为止发现的唯一有用的资源: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.

我更喜欢在第二篇文章中描述的纯代数方法，但这是可行的。

6 个解决方案

#1

Consider the intersection of two spheres. To visualize it, consider the 3D line segment N connecting the two centers of the spheres. Consider this cross section

考虑两个球体的交点。要使它形象化，可以考虑连接两个球体中心的三维线段N。考虑这个横截面

alt text http://gara.matt.googlepages.com/circles.PNG

alt文本http://gara.matt.googlepages.com/circles.PNG

where the red-line is the cross section of the plane with normal N. By symmetry, you can rotate this cross-section from any angle, and the red line segments length can not change. This means that the resulting curve of the intersection of two spheres is a circle, and must lie in a plane with normal N.

当红线是平面的横截面时，通过对称，你可以从任意角度旋转这个横截面，而红线段长度不能改变。这意味着两个球体的交点的结果曲线是一个圆，并且必须与正常的N平躺在一个平面上。

That being said, lets get onto finding the intersection. First, we want to describe the resulting circle of the intersection of two spheres. You can not do this with 1 equation, a circle in 3D is essentially a curve in 3D and you cannot describe curves in 3D by 1 eq.

话虽如此，我们还是去找那个交叉路口吧。首先，我们要描述两个球体相交的结果圆。你不能用一个方程来做这个，一个三维的圆本质上是一个三维的曲线你不能用一个eq来描述三维的曲线。

Consider the picture alt text http://gara.matt.googlepages.com/circlesa.PNG

请考虑图片alt文本http://gara.matt.googlepages.com/circlesa.PNG。

let P be the point of intersection of the blue and red line. Let h be the length of the line segment along the red line from point P upwards. Let the distance between the two centers be denoted by d. Let x be the distance from the small circle center to P. Then we must have

让P是蓝线和红线交叉点的点。让h是沿红线从点P向上的线段的长度。让两个中心之间的距离用d表示，让x等于小圆中心到p的距离，那么我们就必须有。

x^2 +h^2 = r1^2
(d-x)^2 +h^2 = r2^2
==> h = sqrt(r1^2 - 1/d^2*(r1^2-r2^2+d^2)^2)

i.e. you can solve for h, which is the radius of the circle of intersection. You can find the center point C of the circle from x, along the line N that joins the 2 circle centers.

即你可以解出h，也就是交点的圆的半径。你可以从x处找到圆的中心点C，沿着2圆中心的直线N。

Then you can fully describe the circle as (X,C,U,V are all vector)

然后你可以把圆完全描述成(X,C,U,V都是矢量)

X = C + (h * cos t) U + (h * sin t) V for t in [0,2*PI)

where U and V are perpendicular vectors that lie in a plane with normal N.

其中U和V是垂直于平面的垂直向量。

The last part is the easiest. It remains only to find the intersection of this circle with the final sphere. This is simply a plug and chug of the equations (plug in for x,y,z in the last equation the parametric forms of x,y,z for the circle in terms of t and solve for t.)

最后一部分是最简单的。它仍然只是找到这个圆与最终球体的交点。这是方程的一个简单的塞子(代入x,y,z在最后一个方程中x,y,z的参数形式，用t来表示圆，解出t。)

edit ---

编辑- - - - - -

The equation that you will get is actually quite ugly, you will have a whole bunch of sine's and cosine's equal to something. To solve this you can do it 2 ways:

你会得到的方程其实很丑，你会得到一大堆sin和cos等于什么。要解决这个问题，你可以用两种方法:

1. write the cosine's and sine's in terms of exponentials using the equality

   用等号来表示cos和sin。

   e^(it) = cos t + i sin t

   e (it) = cos t + i sin t。

   then group all the e^(it) terms and you should get a quadratic equations of e^(it)'s that you can solve for using the quadratic formula, then solve for t. This will give you the exact solution. This method will actually tell you exactly if a solution exists, two exist or one exist depending on how many of the points from the quadratic method are real.

   然后组e ^(it)方面,你应该得到一个二次方程的e ^(it)的年代,你可以使用二次公式求解,然后求解t。这会给你确切的解决方案。这个方法实际上会告诉你一个解是否存在，两个存在或者一个存在取决于二次方法的点有多少是实数。

2. use newton's method to solve for t, this method is not exact but its computationally much easier to understand, and it will work very well for this case.

   用牛顿法求解t，这个方法不精确，但它的计算更容易理解，对于这个例子来说，它会很好地工作。

#2

Probably easier than constructing 3D circles, because working mainly on lines and planes:

可能比构建3D圆圈更容易，因为主要是在线条和平面上工作:

For each pair of spheres, get the equation of the plane containing their intersection circle, by subtracting the spheres equations (each of the form X^2+Y^2+Z^2+aX+bY+c*Z+d=0). Then you will have three planes P12 P23 P31.

对于每一对球体，通过减去球面方程(每一种形式X 2+Y 2+Z 2+aX+ by +c*Z+d=0)，得到包含其交点圆的平面方程。然后你会有三架P12 P23 P31。

These planes have a common line L, perpendicular to the plane Q by the three centers of the spheres. The two points you are looking for are on this line. The middle of the points is the intersection H between L and Q.

这些平面有一个共同的直线L，垂直于平面Q由球体的三个中心组成。你要找的两点在这条线上。点的中间是L和Q之间的交点H。

To implement this:

实现:

• compute the equations of P12 P23 P32 (difference of sphere equations)
• 计算P12 p2p32的方程(球方程差分)
• compute the equation of Q (solve a linear system, or compute a cross product)
• 计算Q的方程(解线性系统，或计算叉积)
• compute the coordinates of point H intersection of these four planes. (solve a linear system)
• 计算这四个平面的点H的坐标。(解决线性系统)
• get the normal vector U to Q from its equation (normalize a vector)
• 从方程中得到法向量U到Q (normalize a vector)
• compute the distance t between H and a solution X: t^2=R1^2-HC1^2, (C1,R1) are center and radius of the first sphere.
• 计算t H和解决方案之间的距离X:t ^ 2 = R1 ^ 2-HC1 ^ 2,(C1,R1)中心和半径的球体。
• solutions are H+tU and H-tU
• 解是H+tU和H-tU。

A Cabri 3D construction showing the various planes and line L

一个展示各种平面和直线L的Cabri 3D结构。

#3

Basically you need to do this in 3 steps. Let's say you've got three spheres, S1, S2, and S3.

基本上你需要三步走。假设你有三个球，S1, S2和S3。

1. C12 is the circle created by the intersection of S1 and S2.
2. C12是由S1和S2的交集创建的圆。
3. C23 is the circle created by the intersection of S2 and S3.
4. C23是由S2和S3的交集创建的圆。
5. P1, P2, are the intersection points of C12 and C13.
6. P1 P2，是C12和C13的交点。

The only really hard part in here is the sphere intersection, and thankfully Mathworld has that solved pretty well. In fact, Mathworld also has the solution to the circle intersections.

这里唯一真正困难的部分是球体交叉，谢天谢地，Mathworld解决得很好。事实上，Mathworld也有解决循环交叉点的方法。

From this information you should be able to create an algorithm.

从这些信息中，您应该能够创建一个算法。

#4

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.

这里是我从*文章中移植的Python的一个答案。不需要算法;有一个闭合解。

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                       

#5

after searching the web this is one of the first hits, so i am posting the most clean and easy solution i found after some hours of research here: Trilateration

在搜索了web之后，这是第一个点击，所以我发布了最干净、最简单的解决方案，我在这里做了几个小时的研究:Trilateration。

This wiki site contains a full description of a fast and easy to understand vector approach, so one can code it with little effort.

这个wiki站点包含了一个快速且易于理解的向量方法的完整描述，因此您可以毫不费力地编写它。

#6

Here is another interpretation of the picture which Eric posted above:

这是Eric在上面的图片的另一个解释:

Let H be the plane spanned by the centers of the three spheres. Let C1,C2,C3 be the intersections of the spheres with H, then C1,C2,C3 are circles. Let Lij be the line connecting the two intersection points of Ci and Cj, then the three lines L12,L23,L13 intersect at one point P. Let M be the line orthogonal to H through P, then your two points of intersection lie on the line M; hence you just need to intersect M with either of the spheres.

让H是由三个球体的中心张成的平面。让C1 C2 C3是球体的交点H，然后C1 C2 C3是圆。让Lij是连接Ci和Cj的两个交点的直线，然后是L12,L23,L13相交于1点的三行，让M是与H通过P正交的直线，那么你的两个交点就在直线M上;因此，你只需要将M与两个球中的任意一个相交。