寻找3个球体之间的交点

考虑两个球体的交点。要可视化它,考虑连接球体两个中心的三维直线段n。考虑这个横截面

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

其中红线为正N平面的横截面,对称性可以任意角度旋转该横截面,红线段长度不变。这意味着两个球体相交的结果曲线是一个圆,并且必须位于一个具有法向n的平面上。

也就是说,让我们开始寻找十字路口。首先,我们要描述两个球体相交的结果圆。你 不能 用一个方程做这个,一个三维的圆基本上就是一个三维的曲线,你不能用一个方程来描述三维的曲线。

考虑一下图片 alt text http://gara.matt.googlepages.com/circlesa.PNG

设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)

也就是说,你可以解出h,它是相交圆的半径。您可以从x找到圆的中心点c,沿着连接两个圆心的线n。

然后你可以把圆完全描述为(x,c,u,v都是向量)

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

其中u和v是垂直向量,它们位于一个法向n的平面上。

最后一部分是最简单的。它只会找到这个圆与最终球体的交点。这只是方程的一个插接和插接(上一个方程中的x,y,z为插接形式,x,y,z为参数形式,t为求解形式)。

编辑---

你将得到的方程实际上是非常难看的,你会得到一整串正弦和余弦等于某个东西。要解决这个问题,您可以通过两种方式:

1. 用等号写出余弦和正弦的指数

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

   然后将所有e^(it)项分组,得到e^(it)的二次方程。 你可以用二次公式来解,然后用t来解,这会给你精确的解。这个方法实际上会告诉你一个解是否存在,两个存在或者一个存在,这取决于二次方方法中有多少个点是真实的。

2. 用牛顿法求解T,这种方法虽然不精确,但计算起来容易理解,在这种情况下也能很好地解决。

可能比构建三维圆更容易,因为主要在直线和平面上工作:

对于每对球体,通过减去球体方程(每种形式x^2+y^2+z^2+a),得到包含其交集圆的平面方程。 X+B Y+C*Z+D=0)。然后你将有三个平面,p12 p23 p31。

这些平面有一条公共线L,垂直于平面Q,由球体的三个中心构成。你要找的两点在这条线上。点的中间是l和q之间的交点h。

要实现这一点:

• 计算p12 p23 p32的方程(球方程差分)
• 计算q方程(求解线性系统或计算叉积)
• 计算这四个平面的H点交点的坐标。(求解线性系统)
• 从方程中得到法向量u到q(将向量归一化)
• 计算h与解x之间的距离t:t^2=r1^2-h c1^2,(c1,r1)是第一个球体的中心和半径。
• 解决方案是H+T U和H-T U

显示各种平面和线L的cabri三维结构

基本上你需要分三步来完成。假设你有三个球体,s1,s2和s3。

1. c12是由s1和s2的交点创建的圆。
2. c23是由s2和s3的交点创建的圆。
3. p1,p2是c12和c13的交点。

这里唯一真正困难的部分是球体交叉点,谢天谢地 Mathworld has that solved pretty well . 事实上,MathWorld也有 solution to the circle intersections .

根据这些信息,您应该能够创建一个算法。

这是我刚从维基百科文章中移植的一个关于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                       

在搜索了网页后,这是第一次点击,因此我在这里发布了几个小时的研究后发现的最干净、最简单的解决方案: Trilateration

这个wiki网站包含了一个快速且易于理解的矢量方法的完整描述,因此人们可以轻松地对其进行编码。

下面是埃里克在上面发布的图片的另一种解释:

设h为三个球体中心所横跨的平面。设c1,c2,c3为球体与h的交点,c1,c2,c3为圆。让lij是连接ci和cj两个交点的线,然后这三条线l12、l23、l13在一个点p相交。让m是与h到p正交的线,那么你的两个交点就在m线上,因此你只需要将m与任一球体相交。