找到3个球体之间的交叉点

Question

我正在寻找一种算法来找到3个球体之间的公共交叉点.

在完整算法的基础上,对数学的全面/详细描述将非常有帮助.

这是迄今为止我发现的唯一有用的资源:http: //mathforum.org/library/drmath/view/63138.html

但是这里描述的方法都不够详细,我可以写一个算法.

我更喜欢第二篇文章中描述的纯粹代数方法,但有什么用.

Answer 1

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

对于每对球体,通过减去球体方程(每个形式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-HC1 ^ 2,(C1,R1)是第一球的中心和半径.
• 解决方案是H + t U和Ht U.

Cabri 3D结构显示各种飞机和L线

Answer 2

考虑两个球体的交集.要使其可视化,请考虑连接球体两个中心的3D线段N. 考虑这个横截面

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

其中红线是具有法线N的平面的横截面.通过对称,您可以从任何角度旋转此横截面,并且红线段长度不能更改.这意味着两个球体的交点的最终曲线是圆形,并且必须位于具有正常N的平面中.

话虽这么说,让我们找到交集.首先,我们想要描述两个球体交叉的结果圆.您无法使用1个等式执行此操作,3D中的圆基本上是3D中的曲线,您无法通过1 eq描述3D中的曲线.

考虑图片 alt文本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沿着连接2个圆心的线N找到圆的中心点C.

然后你可以完全描述圆圈(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,以t表示圆的x,y,z的参数形式,并求解t.)

编辑---

你会得到的等式实际上非常难看,你会得到一大堆正弦和余弦相等的东西.要解决这个问题,您可以通过两种方式实现:

1. 使用相等性用指数来表示余弦和正弦

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

   然后对所有e ^(it)项进行分组,你应该得到e ^(it)的二次方程式,你可以用二次公式求解,然后求解t.这将为您提供准确的解决方案.这个方法实际上会告诉你一个解决方案是否存在,两个存在或一个存在,取决于二次方法中有多少点是真实的.

2. 使用牛顿的方法来解决t,这个方法并不精确,但计算上更容易理解,并且在这种情况下它会很好用.

Answer 3

基本上你需要分三步完成.假设你有三个球体,S1,S2和S3.

1. C12是由S1和S2的交点创建的圆.
2. C23是由S2和S3的交点创建的圆.
3. P1,P2是C12和C13的交点.

这里唯一真正困难的部分是球体交叉,幸好Mathworld已经很好地解决了.事实上,Mathworld也有圆形交叉点的解决方案.

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

Answer 4

这是我在维基百科文章中提到的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