完成部分三角测量的算法(约束三角剖分)

Question

给定平面中的一组点和点的凸包的不完全三角剖分(仅给出一些边),我正在寻找一种算法来完成三角测量(初始给定边应该保持固定).您可以假设可以完成部分三角测量,但如果您也可以建议用于检查的算法,那就太棒了.

更新"你给出了一组点R ^ 2的凸包,它基本上是一个多边形,里面有一些点.我们想要对点集合进行三角测量,这对于它自身是一个简单的问题,但你也是给出一些边缘,你提出的任何三角测量都应该使用这些边缘."

Answer 1

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

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