如何找到到一个或多个给定 3D 坐标给定距离的所有可能的新位置？

Question

假设我们在立方体中有一组 3D 坐标 (x, y, z)，就像化学中的分子或晶格单元一样。现在我想在盒子里放置一个新的“原子”，我希望它像：

1. 给定固定距离 D
2. 在新原子周围至少发现一个已知原子，其距离恰好为D
3. D
内不允许有任何已知原子
4. 如果有多个已知原子与新原子的距离为D，记录它们的计数。

我已经为自己制定了解决方案，但不确定是否有更好的方法来解决。

我的解决方案简要如下（我的编码版本在这里：actual_code）：

1. 为所有已知坐标构建一个 kd 树。
2. 从所有已知的坐标中，构造一个以坐标为中心、半径为我想要的D的“球体”
3. 现在迭代树，对于每个节点，找到 2D 半径内的节点，然后进行数学计算以确定它们是否相交于点，或圆（不是实心圆，而是它，正如我想要的那样D）
4. 保存点和圆的结果。为圆构建一个数组，以 O(n^2) 的方式迭代它以检查每个圆是否与其他圆相交。我使用一个简单的轨道表来避免同时检查两个相同的圆，并使用一个计数器来计算圆与另一个圆相交的次数。如果计数器为零，则该圆是纯圆，表示仅连接距离为 D 的两个已知坐标的位置。如果圆相交，则与圆相关的所有原子满足 D 的允许位置会折叠成点。
5. 因为计算机在浮点数计算时不可避免地存在波动，所以我设置了一个epsilon为1e-6来“合并”之前计算得到的所有点。
6. 对于“纯圆”，我进一步检查了除了生成该圆的相关两个原子之外，是否存在比 D 更接近圆的原子。我再次使用 kd-tree 来做到这一点。我使用圆半径 + D 作为 find_within_radius 的最大公差。对于找到的原子，检查圆上是否有任何点的距离大于D，这样我们至少有一个距离圆不存在其他原子的位置。

还有一些更强力的努力，以确保结果不会错过任何比 D 更近的原子。到目前为止，我已经用几种化合物和晶格板模型测试了我的程序，结果正是我的预期。然而，对于一些只有大约 100 个原子但具有高对称性的特定情况，程序会挂起几秒钟才能输出结果。由于我是自学编码，没有扎实的数学和计算机科学背景，所以我一开始就想知道是否有更好的策略和算法。

Answer 1

这就是你要找的吗

球体与球体的交叉点。

有很多很棒的教程：

https://gamedev.stackexchange.com/a/75775/86883

（这是关于此事的著名书！）