我有一个平面点集 P。我已经知道 P 中的哪些点 p 属于边界 B(p)。所述边界可以是凸的或非凸的。现在，我想找到边界为 B(p) 的 P 的三角剖分。我的问题：
有没有直接实现这一点的算法？一个接近的候选者将是约束德劳内三角剖分（CDT）。但是，我认为 CDT 不适用于此处：我可以将 B(p) 中的所有边作为约束提供，这样所有边都将包含在三角剖分中。然而，这并不一定意味着这将是三角剖分的边界。如果我在这里错了，请纠正我。
如果你现在有这样的算法，你能给我指出一个提供实现的（轻量级）C 库吗？
或者：我当然可以使用 GTS 的标准 Delaunay 三角剖分对 P 进行三角剖分。然后我需要用 B(p) 之外的顶点修剪所有面。GTS 有可能吗？
我可以将 B(p) 中的所有边作为约束提供，这样所有边都将包含在三角剖分中。然而，这并不一定意味着这将是三角剖分的边界。
您是对的，受约束的 Delaunay 三角剖分可能会填充边界的凹面。然而，每个三角形要么完全在边界内，要么完全在边界外，因此很容易通过从无限面开始遍历平面直线图的对偶来删除边界外的三角形，将边界边缘视为不可通过。例如，Jonathan Shewchuk 的库Triangle就是这样做的。许可证可能不符合您的喜好，但如果您已经有另一个库来计算约束 Delaunay 三角剖分，我们不是在谈论很多额外的代码。
poly2tri在给定边界的情况下找到平面区域的 CDT。它易于构建和使用。
您需要首先使用边界点进行耳朵剪裁，然后将结果传输到 Delaunay 三角剖分并添加内部点。