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

Question

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

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

​

​

它可以在三维这里中看到。

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

例子：给出了26个原子的列表，这些原子在一个三维网格中从(0,0,0)到(1,1,1)之间均匀地间隔。每个原子的半径为0.25，并放置在任意轴上的0、0.5或1上。这一点上没有原子(0.5，0.5，0.5)。如果我们要绘制这些原子的三维图形，它将是一个立方体状的形状，中心缺失。在(0.5,0.5,0.5)处指定一个腔，半径为0.25。可以假定这个腔被四面八方的蛋白质包围。

示例图像：

​

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

一个人将如何去确定一个更大和不规则形状的原子群的空腔和空腔？

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

Extern外：是否有一种不同的算法，在这个例子中，空腔实际上是一个空空间，因为有很小的“路径”可以到达蛋白质的外部？一个空腔必须被原子完全包围才能存在。任何空隙，如果有一条通向蛋白质外部的路径(在任何方向，不一定是直线的)，都不会被认为是空洞。

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可以同时触摸所有三个，在A、B和C的中心之间画一个三角形。
   • 这可以通过几种方式进行检查。一个相当简单的方法：S中心的可能位置，同时触摸A和B，形成一个圆圈。您想知道这个圆上是否有一个点，它小于diam(S) + diam(C)，远离C的中心。这是很简单的几何学。

​

1. 这个问题现在归结为这样一个问题:三角形是否将S中心的初始位置与无穷远分开？您可以一次回答这个连接的组件。事实上，您甚至可以一次回答这个“边缘连接”组件，其中一个组件是边缘连接的，如果任何两个非顶点点都可以通过不通过任何顶点的路径连接。您可以通过简单的图搜索来计算这些组件。
2. 对于给定的边缘连接组件，您需要确定该组件是否将S的中心与无穷远分开。有几种方法可以这样做：
   • 计算组件的2-同调，选择有效的生成器，并为每一个，询问您的点和无穷大是否在周期的同一边，这可以使用定位类进行检查。
   • 或者，只需开始绘制组件：
     • 从您可以从S到达的三角形开始，然后画出可以从那里到达的每一张脸。这有点微妙，但算法只是“从任何地方开始，排列边缘，将每条边缘交叉到脸上，形成带有该边缘的最小角，并在没有边缘时停止。”请记住，同一三角形的对面可能是构成最小角的脸。
     • 从无穷远处做同样的事情。你有没有穿过画过的三角形？如果是的话，你的球体就能逃脱。如果不是，那就不行。

​

​

为什么会起作用

第三步是对的，因为如果你在A和B之间“滚动”边缘的时候没有碰到任何球体，那么你就可以到达边缘的任何一边。换句话说，任何阻止你进入无穷远的位置都必须涉及到S接触至少3个球。

请注意，在“特殊”情况下出现了一些微妙之处，比如当S同时触及4个区域时。在执行步骤3和步骤4之前，您可以通过重新三角化您的形状来避免这些微妙之处。