java - 确定一个球体是否被放置在它周围的其他球体完全包围

Question

问题:给定一个球体列表，找到所有被球体完全包围的空白空间。

详细信息:这是我正在研究的一个问题，我试图确定位于蛋白质中的空腔。我得到了构成蛋白质的原子列表((x，y，z)坐标和半径)。然后我运行我的算法，通过检查是否可以将探针(给定半径)放置在一个位置而不与其他球体发生碰撞，从而找到位于蛋白质边界内的所有空白空间。有两种类型的空隙，空隙和空腔。空隙空间是可以通向蛋白质或位于蛋白质外部的空间。空腔是完全被蛋白质原子包围的空隙。这是我们正在处理的样本“蛋白质”的图片。

可以三个维度查看here .

在蛋白质的中心附近有一个空腔，您看到的穿过蛋白质的隧道将被视为空隙空间，因为它没有被原子完全包围。

示例:给定一个包含 26 个原子的列表，这些原子在 3 维网格中从 (0,0,0) 到 (1,1,1) 均匀分布。每个原子的半径为 0.25，并且位于任意轴上的 0、0.5 或 1 上。在点 (0.5, 0.5, 0.5) 处没有原子。如果我们要绘制这些原子的 3D 图形，它将是一个中心缺失的立方体形状。空腔将指定为 (0.5,0.5,0.5)，半径为 0.25。可以假设这个空腔四周都被蛋白质包围。

示例图片:

请注意，以上只是立方体和蛋白质的二维表示。它实际上是 3D。

对于更大且形状不规则的原子组，如何确定空隙空间与空腔？

我正在考虑实现一个递归算法来检查每个方向以查看它是否可以达到图形的最大和最小边界，但我不确定这是否是正确的方法。

额外:是否有不同的算法会说示例中的空腔实际上是一个空隙空间，因为有非常小的“路径”可以到达蛋白质的外部？空腔必须完全被原子包围才能存在。任何具有通向蛋白质外部的路径(在任何方向上，不一定是笔直的)的空隙空间都不会被视为空腔。

Answer 1

很酷的问题。这是一个应该可以解决问题的算法:

符号:

• 让我们称我们的可移动球体为S .
• 写diam(X)对于球体的直径 X
• 写dist(X,Y)距离 X至 Y ;这与到 X 中心的距离相同到 Y 的中心减去半径之和。

算法:

1. 对于任意两个不可移动的球体 A和 B , 检查是否 S可以直接在A的中心之间通过和 B (即 diam(S) <= dist(A,B) ？)。
2. 如果是这样，对于彼此的球体C , 检查是否 S可以同时触摸所有三个球体A , B , 和 C ，如果不存在其他球体。如果S可以同时触摸所有 3 个，在 A 的中心之间画一个三角形, B , 和 C .
   • 这可以通过多种方式进行检查。一种相当简单的方法:S 中心的可能位置同时触摸 A和 B形成一个圆圈。你想知道这个圆上是否有一个小于 diam(S) + diam(C) 的点远离中心C .这是简单的几何学。
3. 问题现在归结为:三角形是否分隔了 S 中心的初始位置？从无限？您一次可以回答这个连接的组件。事实上，您甚至可以一次回答这个“边连接”组件，其中如果任何两个非顶点点可以通过不通过任何顶点的路径链接，则组件是边连接的。您可以通过简单的图形搜索来计算这些组件。
4. 对于给定的边连接组件，您需要确定该组件是否将 S 的中心分开从无限。有几种方法可以做到这一点:
   • 计算 2- homology选择有效的生成器，并针对每个生成器询问您的点和无穷大是否在循环的同一侧，这可以使用方向类进行检查。
   • 或者，开始绘制组件:
     • 从您可以从 S 到达的三角形开始，并绘制从那里可以到达的每一张脸。这有点微妙，但该算法只是“从任何地方开始，排队边缘，将每条边缘交叉到与该边缘形成最小角度的面上，并在没有剩余边缘时停止。”请记住，同一个三角形的另一边可能是形成最小角度的面。
     • 从无穷远处做同样的事情。你穿过任何彩绘的三角形吗？如果是，则您的球体可以逃脱。如果不是，则不能。

为什么有效

第 3 步是正确的，因为如果你没有击中任何球体 C同时“围绕”A 之间的边缘“滚动”和 B ，那么您可以到达该边缘的任何一侧。换句话说，任何阻止你走向无穷大的位置都必须涉及 S触摸至少 3 个球体。

请注意，“特殊”情况会产生一些微妙之处，例如 S 时一次接触 4 个球体。您可以在执行第 3 步和第 4 步之前重新对形状进行三角测量，从而避免这些细微差别。