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

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

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

有任何想法吗?

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

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

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

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

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

Steven Sudit还提出了一个有用的优化 ,如果你沿着这条路走下去,我建议你这样做。

我认为比尔凯瑞的方法是正确的,但我确实想建议一个可能的优化。

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

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

使用kd树。

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

文章提供了一个很好的解释。

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