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

Question

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

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

有任何想法吗？

Answer 1

如果计算了云的质心,并将其坐标转换为原点为质心的极坐系统,该怎么办？

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

假设表面可以通过Delaunay三角剖分表示,请确定与您正在检查的点之间的角度差异最小的三个点.

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

基本上,您正在构建凸包的三角形网格,但一次需要一个三角形.如果执行速度非常重要,您可以随时缓存生成的三角形.

Steven Sudit还建议了一个有用的优化,如果你走这条路,我建议你这样做.

Answer 2

我认为Bill Carey的方法是正确的,但我确实想建议一个可能的优化.

由于形状大致为球形,因此可以预先计算由其约束的球体的半径以及限制它的球体的半径.这样,如果点的距离在较小的球体内,那么它就是一个明确的命中,如果它在外球体之外,它就是一个明确的错过.

这应该让你很快解决容易的案件.对于更难的人,凯里的方法接管了.