implicit - 未网格化点云的 Delaunay 点检验

Question

给定一个任意点 P，并假设我可以查找按距离排序的附近（未划分网格）点，是否有可能有效地确定形成包含 P 的德劳内三角形的三个附近点？如果是这样，怎么做？

Answer 1

我假设你是二维的，没有共线点。我的建议也适用于 3D。构建一个包含所有点的 Kd 树。然后寻找 P 的 2 个最近邻。构造外接圆。

考虑那个圆的中心并寻找它最近的邻居。如果您找到的第一个点（忽略三角形点）比圆半径更远，那么您就有了三角形。否则，违反了空圆属性，在这种情况下，您知道该点在三角形之外。您现在可以定义两个三角形并检查是否像以前一样验证了空圆圈属性（但如果您在圆圈中找到一个点，我认为您需要检查该点是否在三角形内）。然后就像用所有四点和你在外接圆内找到的所有其他点进行 Delaunay 三角剖分。

对于实现，您可以使用例如 CGAL，它提供了Orthogonal_incremental_nearest_neighbor、来自Triangle_2类的 has_on_bounded_side 函数和circumcenter函数。

您还可以直接使用使用前三个点初始化的Delaunay_triangulation_2类，并逐步插入点，从而使三角形面的空圆属性无效。