c++ - 确定一个点是在 CGAL 中的 3D Alpha 形状表面的内部还是外部

Question

我正在使用 CGAL 使用ex_alpha_shapes_3 示例创建一组 3D 点的凹壳。接下来，我想知道空间中的点查询是否位于由三角形凹壳面（ex_alpha_shapes_3 代码的输出）创建的曲面内。“多边形中的点”技术应该对此有用。如果有人可以帮助我解决这个问题，我将不胜感激。

Answer 1

您可以使用定位函数，根据点所在的单纯形以及单纯形的分类函数的输出，您将直接知道您是在内部、外部还是在边界上。

• 无论哪种单纯形，EXTERIOR 是外部的，INTERIOR 是内部的。
• 如果该点落在一条边上，则 REGULAR 位于边界上，而 SINGULAR 取决于您的设置中的孤立边是否应该是什么
• 如果点落在顶点上，则 REGULAR 在边界上，而 SINGULAR 取决于您的设置中是否应该有一个隔离的输入点

Answer 2

我不了解 CGAL，但是鉴于您的多面体已知是凸的，您可以使用一些启发式方法。您可以在本质上是 2D 中完成很多工作。您可以使用任何轴，但假设我们在 XY 平面上工作并暂时忽略 Z 分量。由于您的形状是凸形的，因此通常只有两个三角形的 XY 坐标围绕您的点的 XY 坐标。对于任何三角形，您可以快速确定是否 x[min] < x[point] < x[max] 并且对于 y 也是如此。如果这些测试失败，请继续。如果他们成功了，则需要进一步测试以确定该点是否实际上在三角形内。找到 2 个可接受的三角形后，在点 (X,Y) 处找到每个三角形的 Z 值。如果点的 Z 在面的 Z 值之间，