如何测试一个点是否在由点云定义表面的三维形状内部？

Question

我有一组描述一个近似球体形状表面的点集合，需要一种方法来确定其它给定的点是否在这个形状内部。之前我一直将该形状近似为精确的球体，但是这已经被证明不够准确，我需要更准确的方法。简单和速度比完全准确更可取，一个好的近似就足够了。

我找到了一些将点云转换为3d网格的技术，但大多数都非常复杂，我正在寻找尽可能简单的东西。

有什么想法吗？

- Ben

---

云是否固定？表面是否凸出？您需要多频繁地进行点测试？ - Aryabhatta

云计算并非“长期固定”，但对于这些计算来说，它是固定的，因为它们将在系统的“快照”上执行。它不需要像游戏或其他实时应用程序那样实时运行。 测试将大约每2秒钟执行一次。 - Ben

Answer 1

如果您计算云的质心，并将其坐标转换为以该质心为原点的极坐标系统。

然后，将要检查的点转换为相同的坐标系。

假设表面可以用Delaunay三角形表示，则确定与您正在检查的点的角度差最小的三个点。

将要检查的点投影到由这三个点确定的三角形上，并查看从质心到投影点的距离是否大于实际点的距离。

实质上，您正在一次需要一个三角形地构建凸包的三角形网格。如果执行速度真的很重要，您可以在执行过程中缓存生成的三角形。

Steven Sudit还提出了有用的优化建议，如果您选择这条路线，我建议你采纳。

- Bill Carey

---

这听起来是个好主意，非常感谢！我现在会尝试一下看看它是否有效。我已经为另一个算法的优化准备了每个点的相邻点列表，我或许可以回收利用以加快速度。 - Ben

我思考了一下，我怀疑三个点应该总是足够的。这基于表面可以用三角形来定义的想法。只要点在三角形平面的靠近重心的一侧，那么它就在范围内。当然，如果这个假设是错误的——如果有凹陷和悬挑——那么这些都不成立。再说一遍，我不知道什么是正确的；仅仅添加更多的点是不够的。 - Steven Sudit

或者用正确的术语来说，我认为它是可以用Delaunay三角形来定义的凸包。 - Steven Sudit

Answer 2

我认为Bill Carey的方法是正确的，但我想提出一种可能的优化方案。

由于该形状大致呈球形，因此可以预先计算包围它的球体的半径和包围它的球体的半径。这样，如果点的距离在较小的球体内，则它是一个明确的命中；如果在外部球体之外，则它是一个明确的未命中。

这应该能够让您非常快速地解决简单情况。对于更困难的情况，可以采用Carey的方法。

- Steven Sudit

---

这绝对是一个很好的优化。我可以在我的答案中添加一个属性引用吗？ - Bill Carey

@Bill，我想你刚刚做到了。 :) - Steven Sudit

@Bill：看到每个答案左下角的“链接”链接了吗？你可以使用它加上标记或HTML来在帖子中创建“查看Steven的不错优化。”这样的链接...这通常是我处理这些事情的方式。 - dmckee --- ex-moderator kitten

我突然想到，如果将点存储为极坐标，则内部和外部边界球只是点半径的最小值和最大值！ - Steven Sudit

Answer 3

使用kd树。

http://en.wikipedia.org/wiki/Kd-tree

文章提供了很好的解释。

我可以澄清任何进一步的误解。

- bearrito

---

kd-tree与寻找最近的三个点有关，尽管听起来Ben有其他实现方法。 - Steven Sudit

你能否在极坐标系中构建KD树？我没有足够的经验来了解这一点。如果可以的话，它可能会很有用。 - Bill Carey

据我所知，kd树是用于笛卡尔坐标系的。如果是这样，你总是可以进行转换。如果不是，那么我很想看看它们如何处理混合单位（角度与距离）的问题。@Bill - Steven Sudit

嗯，我想知道的另一个问题是他们如何处理角度在360°处环绕的邻近问题。笛卡尔坐标具有独特和连续的优点。 - Steven Sudit