线性时间的多面体测试点

Question

假设我们有一个具有N个顶点的3D多面体。 你如何测试一个点是否在时间O（n）内。 应该有一个线性算法，但我的搜索不成功。

Answer 1

如果有限定凸多面体（3D版多边形的）N个点，这意味着得到的形状是拓扑等价球体。

如果你查找几个拓扑定理，这并不难证明。基本上，由于没有内部孔，所以缺少孔将您的多面体放置在与球体相同的几何对象的“属”中。然后，您只需将每个顶点（一组N个拉伸）转换为距给定内点的某个固定距离R.由于所有这些点现在位于球体的表面上，并且只使用拓扑合法的“拉伸”操作（通过移动它们的顶点来拉伸边界面），所以凸多面体在拓扑上等同于球体。我省略了正式的条款，因为它们不会增加太多混乱。

只要你空穴 - 并不等同于球体再添加任何排除内部区域 - 。在这种情况下，你可以使用相同的扩展版本。你测试你是否在多面体的“边界面”内，然后测试你是否在它的任何一个洞内（它们也是多面体）。你需要一些额外的标志或条款孔位于外多面体的一部分，等

Answer 2

可能您正在使用给定顶点的凸包。

计算凸包（O（N log n）的），并发现是在多面体点（O（N））具有复杂度O（N log n）的。

如果点不在凸多面体比有分隔点和多面体的平面。在2D中，很容易找到从点到多面体顶点的矢量之间的分离平面测试角度。对于3D我不知道如何做到这一点（在O（n））。

Answer 3

解决方案是： 由于多面体在拓扑上等价于一个球体，因此它的面（和边）数为O（n）（因为它相当于一个平面图，... - 需要一个简短的证明）。只需迭代所有面并进行类似于2D中的点中多边形测试的光线投射，实际上将在O（n）中运行，因为只有O（n）个面。