algorithm - 动态简单多边形三角剖分

Question

如问题标题所示，如何对动态增长的简单多边形进行三角剖分，也就是说，每当用户或计算机动态添加新顶点时，多边形就应该再次进行三角剖分。因此，与其在添加每个新顶点后运行一些三角剖分算法，不如对每个新输入有任何聪明/高效(也可能易于实现)的方法，应该说 <= O(n) 时间来对多边形进行三角剖分。新添加的顶点将与当前多边形的第一个和最后一个顶点相邻。

Answer 1

当您插入一个新顶点并用两条边替换一条边时，它们形成的三角形可能会与三角剖分的多个三角形重叠。重叠的三角形形成一个子多边形。构建此多边形的轮廓并插入新顶点。然后重新三角化更新的子多边形。

我想可以通过递归地探索起始三角形的邻居并检查它们是否重叠来有效地找到重叠三角形。子多边形的轮廓由两个三角形不共享的边组成。