6

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

细节：这是我正在研究的一个问题，我试图确定蛋白质中的空洞。我得到了组成蛋白质的原子列表（（x，y，z）坐标和半径）。然后我运行我的算法，通过检查（给定半径的）探针是否可以放置在不与其他球体碰撞的位置来查找位于蛋白质边界内的所有空白空间。有两种类型的空间，空隙空间和空腔。空隙空间是可以通向蛋白质或位于蛋白质外部的空间。空腔是完全被蛋白质原子包围的空白空间。这是我们正在使用的样本“蛋白质”的图像。

蛋白质

在这里可以从三个维度来看。

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

示例：给定一个包含 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。

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

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

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

4

1 回答 1

4

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

符号：

  • 让我们称我们的可移动球体S。
  • 写出diam(X)球体的直径X
  • 写出从到dist(X,Y)的距离；这与从中心到中心的距离减去半径之和相同。XYXY

算法：

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

为什么有效

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

请注意，“异常”情况会产生一些微妙之处，例如S一次接触 4 个球体时。在执行第 3 步和第 4 步之前，您可以通过重新三角化您的形状来避免这些细微之处。

于 2012-05-01T03:55:50.503 回答