algorithm - 完成部分三角剖分的算法（约束三角剖分）

Question

给定平面中的一组点和点的凸包的不完整三角剖分（仅给出一些边），我正在寻找一种算法来完成三角剖分（初始给定的边应该保持固定）。您可以假设可以完成部分三角剖分，但如果您也可以建议一种算法来检查它，那就太好了。

更新“你得到了一组点 R^2 的凸包，它基本上是一个多边形，里面有一些点。我们想对这组点进行三角剖分，这本身就是一个简单的问题，但你也是给定一些边缘，您提出的任何三角测量都应该使用这些边缘。”

Answer 1

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

CGAL 有一个很好的实现。工具三角形具有相似的功能并且更容易上手，但（可能）灵活性稍差。

Answer 2

我发现“计算几何：简介”这本书对这个主题进行了详细的处理，尽管它没有提供准备好实现的伪代码。

最简单的算法是一种贪心算法，它枚举所有可能的边，然后将它们一一添加，避免与先前添加的年龄相交。书中关于如何将运行时间减少到 O(n^2 log n) 的讨论很长。

然后有一个 O(n log n) 算法，它首先用给定的边对凸包进行正则化，然后分别对每个单调多边形进行三角剖分。