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

Question

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

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

有什么想法吗？

Answer 1

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

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

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

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

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

Steven Sudit 也建议 a useful optimization如果你走这条路，我会推荐它。