问三维凸多面体中的点定位

EN

对于(1)，如果你有一个有n个顶点的凸多面体，那么你还有O(n)个面。一个人可以对每个面进行三角剖分，但总体上仍然是O(n)个三角形。现在取查询点Q，检查三角形Q的哪一边。此检查对一个三角形采用O(1)，因此对所有三角形采用O(n)。编辑: O(n)面定义O(n)平面。只需检查Q是否在所有平面的同一侧。

对于(2)，(我没有找到这方面的来源，但它似乎是合理的)可以将多面体P作为P‘投影到平面上。P‘可以看作是两个独立的平面图，一个图U’表示多面体的上部，第二个图L‘表示下部。在L‘和U’中总共有O(n)个面。现在可以通过Kirkpatrick optimal planar subdivision算法对L‘和U’进行预处理。(其他来源：1和2)这将启用PSLG (平面直线图)检查中的O(log )点。

现在使用查询点Q并将其投影到具有相同投影的同一平面上，可以在O(log )时间内查找其所在的L‘和U’的面。在3D中，每个面恰好位于一个平面中。现在我们检查Q在3D中的哪一边，并知道Q是否在多面体内部。

(2)的另一种方法是将多面体在空间上细分为slubs -金字塔，以其在多面体质心和多面体面上的顶点为基础。这样的板数是O(n)。您可以构建一个二进制空间分区树(BSP)，由这些分块(可能分成子分块)组成-如果它是平衡的，那么点位置将在O(logn)时间内工作。

当然，如果您需要多次调用点位置函数，这将是有意义的-因为这里的预处理步骤将占用O(n)时间(或更多)。