如何测试点是否位于其表面由点云定义的 3D 形状内？
我有一个点的集合，这些点描述了一个大致呈球形的形状的表面，并且我需要一种方法来确定是否有任何其他给定点位于该形状内。我之前一直将形状近似为精确的球体，但事实证明这太不准确，我需要一种更准确的方法。简单性和速度比完全精确性更有利，一个好的近似值就足够了。
我遇到过将点云转换为 3D 网格的技术，但我发现的大多数东西都非常复杂，我正在寻找尽可能简单的东西。
有什么想法吗？
I have a collection of points which describe the surface of a shape that should be roughly spherical, and I need a method with which to determine if any other given point lies within this shape. I've previously been approximating the shape as an exact sphere, but this has proven too inaccurate and I need a more accurate method. Simplicity and speed is favourable over complete accuracy, a good approximation will suffice.
I've come across techniques for converting a point cloud to a 3d mesh, but most things I have found have been very complicated, and I am looking for something as simple as possible.
Any ideas?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果计算云的质心，并将其坐标转换为原点为该质心的极坐标系，会怎样？
然后，将要检查的点转换到相同的坐标系。
假设曲面可由 Delaunay 三角剖分表示，请确定与您正在检查的点之间角度差异最小的三个点。
将您要检查的点投影到由这三个点确定的三角形上，然后查看投影点到质心的距离是否大于实际点的距离。
本质上，您正在构建凸包的三角形网格，但根据需要一次构建一个三角形。如果执行速度确实很重要，您可以随时缓存生成的三角形。
Steven Sudit 还建议 一个有用的优化，如果您沿着这条路走下去，我会推荐它。
What if you computed the centroid of the cloud, and converted its coordinates to a polar system whose origin is that centroid.
Then, convert the point you want to examine to the same coordinate system.
Assuming the surface is representable by a Delaunay triangulation, determine the three points with the smallest difference in angle from the point you're examining.
Project the point you're examining onto the triangle determined by those three points, and see if the distance of the projected point from the centroid is larger than the distance of the actual point.
Essentially, you're constructing a triangular mesh of the convex hull, but as-needed one triangle at a time. If execution speed really matters, you might cache the resulting triangles as you go.
Steven Sudit has also suggested a useful optimization that I'd recommend if you go down this path.
我认为比尔·凯里的方法是正确的，但我确实想提出一个可能的优化建议。
由于形状大致为球形，因此您可以预先计算它所包围的球体的半径以及包围它的球体的半径。这样，如果该点的距离在较小的球体之内，则确定是命中；如果该点的距离在外部球体之外，则确定是未击中。
这应该可以让您快速解决简单的情况。对于较难的问题，凯里的方法就起作用了。
I think Bill Carey's method is on the right track, but I do want to suggest a possible optimization.
Since the shape is roughly spherical, you can pre-calculate the radius of the sphere bound by it and of the sphere that bounds it. This way, if the distance of the point is within the smaller sphere, it's a definite hit and if it's outside the outer sphere, it's a definite miss.
This ought to let you resolve the easy cases very quickly. For the harder ones, Carey's method takes over.
使用 kd 树。
http://en.wikipedia.org/wiki/Kd-tree
文章提供一个很好的解释。
我可以消除任何进一步的误会。
Use a kd-tree.
http://en.wikipedia.org/wiki/Kd-tree
The article provides a good explanation.
I can clear up any further misunderstandings.