我有一个平面点集 P。我已经知道 P 中的哪些点 p 属于边界 B(p)。所述边界可以是凸的或非凸的。现在,我想找到边界为 B(p) 的 P 的三角剖分。我的问题:
有没有直接实现这一点的算法?一个接近的候选者将是约束德劳内三角剖分(CDT)。但是,我认为 CDT 不适用于此处:我可以将 B(p) 中的所有边作为约束提供,这样所有边都将包含在三角剖分中。然而,这并不一定意味着这将是三角剖分的边界。如果我在这里错了,请纠正我。
如果你现在有这样的算法,你能给我指出一个提供实现的(轻量级)C 库吗?
或者:我当然可以使用 GTS 的标准 Delaunay 三角剖分对 P 进行三角剖分。然后我需要用 B(p) 之外的顶点修剪所有面。GTS 有可能吗?