用于完成部分三角测量的算法（约束三角测量）

Question

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

UPDATE“你给出了一组点R^2的凸包，它基本上是一个多边形，里面有一些点，我们想要对点集进行三角化，这本身就是一个直接的问题，但你也有一些边缘，你想出的任何三角形都应该使用这些边缘。“

Answer 1

也许这是一个天真的答案，但你不能只用一个约束Delaunay三角？将已知边添加为约束。

CGAL有nice implementation。工具triangle具有相似的功能，并且更容易入门，但具有（可能）更少的灵活性。

Answer 2

我发现这本书“计算几何：介绍”有主题的详细处理，虽然它不给一个准备执行伪代码。

最简单的算法是一个贪婪其中一个枚举所有可能的边缘，然后由一个避免与先前添加的年龄交点添加它们之一。关于如何将运行时间减少到O（n^2 log n），本书有很长的讨论。

然后有一个为O（n log n）的算法，该算法首先规则化与给定的边缘凸包，然后分别进行三角测量每个单调多边形。