c - 如何测试一个点是否位于 3d 形状内，其表面由点云定义？

Question

我有一组点来描述应该大致为球形的形状的表面，我需要一种方法来确定是否有任何其他给定点位于该形状内。我之前一直将形状​​近似为一个精确的球体，但事实证明这太不准确了，我需要一种更准确的方法。简单性和速度优于完全准确度，一个好的近似值就足够了。

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

有任何想法吗？

Answer 1

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

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

假设曲面可以通过 Delaunay 三角剖分表示，请确定与您正在检查的点的角度差最小的三个点。

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

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

Steven Sudit 还提出了一个有用的优化建议，如果你走这条路，我会推荐它。

Answer 2

我认为 Bill Carey 的方法是正确的，但我确实想提出一个可能的优化建议。

由于形状大致为球形，因此您可以预先计算由它包围的球体的半径以及包围它的球体的半径。这样，如果该点的距离在较小的球体内，则确定命中，如果在外球体之外，则确定未命中。

这应该可以让您很快解决简单的问题。对于较难的，凯里的方法接管了。

Answer 3

使用 kd 树。

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

这篇文章提供了很好的解释。

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