我有一个平面点集P。我已经知道P中哪些点p属于边界B(p)。所述边界可以是凸的或非凸的。现在，我想找到边界为 B(p) 的 P 的三角剖分。我的问题:
是否有直接实现此目的的算法？一个接近的候选者是约束德劳内三角剖分 (CDT)。但是，我认为 CDT 不适用于此处:我可以将 B(p) 中的所有边作为约束提供，这样所有边都将包含在三角剖分中。然而，这并不一定意味着这将是三角测量的边界。如果我在这里错了，请纠正我。
如果您现在知道这样的算法，您能告诉我一个提供实现的(轻量级)C 库吗？
或者:我当然可以使用来自 GTS 的标准 Delaunay 三角剖分对 P 进行三角剖分。然后我需要修剪所有顶点在 B(p) 之外的面。 GTS 可以吗？
最佳答案
I could feed all the edges in B(p) as a constraint, such that all the edges would be contained in the triangulation. However, this does not necessarily entail that this will be the boundary of the triangulation.
您说得对，受约束的 Delaunay 三角剖分可以填充边界的凹陷。然而，每个三角形要么完全在边界内，要么完全在边界外，因此通过从无限面开始遍历平面直线图的对偶，将边界边视为不可通过，可以很容易地删除边界外的三角形。 Jonathan Shewchuk 的图书馆 Triangle ，例如，这样做。该许可证可能不符合您的喜好，但如果您已经有另一个库来计算受约束的 Delaunay 三角剖分，我们并不是在谈论大量额外的代码。
关于c - 对具有已知边界的平面点集进行三角测量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19055134/