查找3个球体之间的交点 [英] Finding intersection points between 3 spheres
问题描述
我正在寻找一种算法来查找3个球体之间的公共交点.
如果没有完整的算法，则对数学进行彻底/详细的描述将非常有帮助.
这是我到目前为止发现的唯一有用的资源: http://mathforum.org/library/drmath/view/63138.html
但是其中描述的两种方法都不足够详细，我无法在上面编写算法.
我更喜欢第二篇文章中描述的纯代数方法，但是仍然有效.
UPDATE
可以在此 github中找到此答案的python实现及其用法示例回购.
事实证明，使用这种方法，解析解决方案实际上是非常不错的，并且可以告诉您何时存在一个解决方案，何时不存在(也可能只有一个解决方案.)没有理由使用牛顿方法
恕我直言，这比下面给出的三边测量法更容易理解和简单.但是，这两种技术都可以在我的测试中给出正确的答案.
原始答案
考虑两个球的相交.为了使其可视化，请考虑连接球体两个中心的3D线段N.考虑这个横截面
(来源: googlepages.com )
其中红线是具有法线N的平面的横截面.通过对称，可以从任意角度旋转该横截面，并且红线段的长度不能改变.这意味着两个球体相交的结果曲线为圆，并且必须位于具有法向N的平面中.
话虽如此，让我们开始寻找交点.首先，我们要描述两个球的相交的结果圆. 您不能使用1个方程式执行此操作，3D中的圆本质上是3D中的曲线，并且不能以1 eq来描述3D中的曲线.考虑图片
(来源: googlepages.com )
令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，这是相交圆的半径.您可以沿着连接两个圆心的线N从x处找到圆的中心点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.)
编辑---
您将得到的等式实际上很难看，您将有一堆正弦和余弦等于某物.要解决此问题，您可以通过两种方式做到这一点:
-
使用等式以指数形式写余弦和正弦值
e ^(it)= cos t + i sin t
然后将所有e ^(it)项分组，您应该得到e ^(it)的二次方程 您可以使用二次方程式求解，然后求解t.这将为您提供确切的解决方案.实际上，此方法会确切地告诉您解决方案是存在的，两个存在的或一个存在的，这取决于二次方法中有多少点是真实的.
-
使用牛顿法求解t，该方法并不精确，但计算上更容易理解，在这种情况下将非常有效.
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.
UPDATE
An implementation of this answer in python complete with an example of usage can be found at this github repo.
It turns out the analytic solution is actually quite nice using this method and can tell you when a solution exists and when it doesn't (it is also possible to have exactly one solution.) There is no reason to use Newton's method.
IMHO, this is far easier to understand and simpler than trilateration given below. However, both techniques give correct answers in my testing.
ORIGINAL ANSWER
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
(source: googlepages.com)
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.
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.
Consider the picture
(source: googlepages.com)
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
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.
Then you can fully describe the circle as (X,C,U,V are all vector)
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.
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.)
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:
write the cosine's and sine's in terms of exponentials using the equality
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.
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.
这篇关于查找3个球体之间的交点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
