动态简单多边形三角剖分

Question

如题所述，如何三角剖分一个动态增长的简单多边形，即每当用户或计算机动态添加新顶点时，多边形应重新进行三角剖分。因此，不是在添加每个新顶点后运行一些三角剖分算法，而是是否有任何聪明/高效（可能也容易实现）的方法，使每个新输入需要花费≤O(n)时间来三角剖分多边形。 新添加的顶点将与当前多边形的第一个和最后一个顶点相邻。

- mcertitude

---

多边形是否保持凸性？如果在A和B之间添加了新的顶点C，则只需将ABC作为附加三角形即可。 - Henry

不一定，但它始终是一个简单多边形。 - mcertitude

嗯，当一个新的顶点添加一个三角形时，这是非常直接的，但如果它“减去”它（即当顶点在现有多边形内部时），它可能会非常显著地改变内部三角剖分，我怀疑是否有简化的方法。因此，也许你只处理添加作为一个特殊情况。 - Anton Knyazyev

Y单调性怎么样？假设多边形正在动态地被分割成Y单调多边形，那么添加一个新顶点是否需要超过O（n）的时间来改变结构？ - mcertitude

如果我没记错的话，有些情况下添加一个顶点会强制你重新进行整个三角剖分（如果新边穿过所有对角线）。 - user1196549

Answer 1

当您插入一个新顶点并用两个边替换一条边时，它们形成的三角形可能会与三角剖分中的许多三角形重叠。重叠的三角形组成一个子多边形。建立该多边形的轮廓，并插入新顶点。然后重新对更新后的子多边形进行三角剖分。

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

- user1196549

---

这个观察是正确的，但我想要更具体的东西，不过还是谢谢。 - mcertitude

@mcertitude：这非常具体。它向您展示，您无论如何都需要重新三角化（有时是整个多边形），使其更快只是虚幻的最坏情况。它还向您展示，增量解决方案的一个主要组成部分是标准三角剖分算法。最后的评论使其非常接近可行的实现，看起来并不那么复杂。 - user1196549

Answer 2

我假设在每个步骤中，多边形都会通过添加顶点C、删除线段AB并添加线段AC和CB来进行扩展。我还假设没有退化情况。

如果ABC是顺时针旋转的（也就是说，多边形向外扩展），只需将ABC添加到三角剖分中即可。

否则，在之前的三角剖分中考虑三角形ABD。如果C在该三角形中，则删除三角形ABD并添加三角形BDC和DAC。如果不是，则它在AD侧的子多边形或BD侧的子多边形中。删除ABD并递归进入相应的子多边形，在（例如）线段BD上添加C。完成递归后，像之前一样添加三角形BDC和DAC。

这种解决方案依赖于新旧多边形均为简单多边形（非自交）。否则，在递归步骤后添加三角形可能无效。

- Sneftel