确定一个点是否在CGAL的3D Alpha形状表面的内部或外部

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

来源

2014-07-15 Vahid

我不熟悉CGAL，所以我不知道在那里实现光线追踪和射线碰撞算法是多么容易。如果这很难，而且性能也不重要，那么如果一个点在一个alpha形状内，那么原始点集+查询点的alpha形状应该与原始alpha形状相同，并且您可能能够检查这个“平等”。 –

感谢您的回复。实际上，性能非常关键，因为我需要在每个时间步骤重复此过程，并且我的数据集中可能会有相当多的点（数十万甚至更多）。 – Vahid

您可以使用locate函数，并根据单纯形点和单纯形函数classify的输出结果，直接了解您是在内部，外部还是边界上。

无论单纯型，EXTERIOR是外部，INTERIOR是内部。
如果点落在边缘，定期是在边界上奇异取决于是否有什么隔离的优势应该在你的设置
如果这些点上的顶点回落，定期是在边界上和奇异是取决于是否一个孤立的输入点应该在你的设置

来源

2014-07-15 20:01:40 sloriot

感谢您的有用答案。目前，我只使用“Alpha_shapes_3”来构造凹面。这是否意味着我需要首先在整个体积（由凹面覆盖）内生成一个三角形网格，以便能够使用“Traiangulation_3”中的“定位”功能？我是一名具有基本C++经验的新CGAL用户，所以这让我有点困惑。 – Vahid

Alpha_shape_3继承Triangulation_3。 – sloriot

我试图通过将下面几行添加到代码中来使用locate函数，但是在编译时出现错误。 – Vahid

我不知道CGAL，但有几个启发式可以使用，因为你的多面体已知是凸的。基本上2D可以做很多工作。您可以使用任何轴，但假设我们正在XY平面中工作并暂时忽略Z分量。由于你的形状是凸的，通常只有两个三角形的XY坐标围绕着你的点的XY坐标。对于任何三角形，您可以快速确定是否x [min] < x [point] < x [max]，同样对于y。如果这些测试失败，继续前进。如果他们成功了，需要进一步测试来确定点是否实际在三角形内。找到2个可接受的三角形后，找到该点（X，Y）处每个三角形的Z值。如果点的Z位于面的Z值之间，则该点位于实体内部。

来源

2014-07-15 18:49:09 Logicrat

对于凸包，这似乎是一个有趣的方法，谢谢。但是，在我的情况下，我有一个凹包，其中可能包含多个体积（空间中未连接的部分）或两个以上的XY围绕查询点的三角形。我想这种算法在这种情况下不起作用。 – Vahid

我的不好，我在你原来的问题中误读为“凸”。然而，基本逻辑仍然适用，尽管它更复杂。你必须在2D中找到所有周围的三角形。然后，如果Z轴上方或下方的三角形的数量为奇数，则该点位于其中一个体积内，特别是包含其Z值在任一方向上与测试点最接近的三角形的体积。 – Logicrat

确定一个点是否在CGAL的3D Alpha形状表面的内部或外部

回答

相关问题