performance - 确定 N 个球体之间的交点

Question

只是想知道确定 N 个球体上交点的最佳方法（在速度和准确性方面）是什么（这里要求两个球体）；想知道什么是最好的语言来做到这一点。关于我想要做的更详细的解释是here。

Answer 1

据我所知，您正在询问每对 N 3D 球体的交叉点。算上对称性，有 N * (N-1) / 2 对。

所以拿每一对。如果中心之间的距离大于它们的半径之和，则不存在交集。（编辑：或者，正如@Ben 指出的那样，如果距离小于半径的差异，也没有交集。）

如果相等，则交点是一个点，很容易在中心之间的线段上找到。如果小于，则轨迹是一个圆，而不是一个点。

要找到该圆的中心及其半径，您需要对两个球体进行平面切片。这将问题减少到找到两个圆的交点。为此，您需要余弦定律。

详细说明：查看那个维基百科图表。a和b是两个球体的半径，c是中心之间的距离。使用倒数第二个方程求解cos(alpha)。从那里你可以很容易地得到sin(alpha)。那么b sin(alpha)是圆的半径，b cos(alpha)是到圆心的距离。（注意 - 这不调用任何三角函数，只调用sqrt。）

一旦你知道了相交圆的中心和半径，圆本身就在一个垂直于连接球心的线段的平面上。

除此之外，我不确定你想要什么。

Answer 2

如果我猜对了，你想要一组 N 个球体中至少两个球体的所有交点，对吧？

如果是这样，这对于高性能计算来说实际上不是一个容易的问题，至少如果您需要一个准确的解决方案则不是。在计算分子的“缩减表面”时也解决了这个问题：

http://www.ncbi.nlm.nih.gov/pubmed/8906967

有几篇关于如何有效计算这些点和圆的出版物，但这并不是一件容易的事。我相信有一个出版物用 CUDA 计算这些值，但我不记得细节了。谷歌（学者）应该能够在这个方向上帮助你。

但是，根据您想要实现的目标，可以有更简单的解决方案。那么，也许您可​​以详细说明您的问题？