完成部分三角剖分(Constrained Triangulation)的算法

Question

给定平面中的一组点和一个不完整的 triangulation of the convex hull of the points (只给出了一些边)，我正在寻找一种算法来完成三角剖分(初始给定的边应该保持固定)。您可以假设可以完成部分三角剖分，但如果您也可以建议一种算法来检查它，那就太好了。

UPDATE"你得到了一组点 R^2 的凸包，它基本上是一个内部有一些点的多边形。我们想要对这组点进行三角剖分，这本身就是一件简单的事情，但是你还给出了一些边，您提出的任何三角剖分都应该使用这些边。”

Answer 1

也许这是一个幼稚的答案，但您不能只使用受约束的 delaunay 三角剖分吗？添加已知边作为约束。

CGAL 有一个 nice implementation .工具triangle具有相似的功能并且更容易上手，但(可能)灵 active 稍差。