java - Delaunay 对带孔的二维多边形进行三角剖分

Question

我想对带孔的复杂(但不是自相交)多边形进行三角剖分，以便生成的三角形都位于多边形内，完全覆盖该多边形，并遵守 Delaunay 三角形规则。

显然，我可以为所有点构建 Delaunay 三角剖分，但我担心多边形的某些边不会包含在生成的三角剖分中。

那么，这样的三角测量可能吗？如果是，我该怎么做？

以防万一 - 我需要它来构造多边形中轴的近似值(我希望它可以通过连接所得三角形的所有圆周点来完成)。

Answer 1

听起来你想要constrained Delaunay triangulation . “孔”可以通过限制输入边在三角剖分中保持不间断来实现。

参见 Triangle和 poly2tri实现项目。