Delaunay对带有孔的二维多边形进行三角测量
Rog*_*ach 14 java algorithm geometry delaunay medial-axis
我想对带有孔的复杂(但不是自相交)多边形进行三角测量,以便生成的三角形全部位于多边形内部,完全覆盖该多边形,并遵守Delaunay三角形规则.
显然,我可以为所有点构建Delaunay三角剖分,但是我担心多边形的某些边缘不会被包含在生成的三角剖分中.
那么,这样的三角测量可能吗？如果是,我该怎么办？
以防万一 - 我需要它来构造多边形中轴的近似(我希望它可以通过连接所得三角形的所有圆周点来完成).
这是我在为 RTS 游戏制作导航网格时想到的方法之一。请注意，它是自制软件，没有使用第三方工具，我花了大约 3 周的时间来实现和修复错误：
- 将所有点输入 Delaunay 三角剖分（以获得最均匀的三角形）
- 沿孔轮廓检查并翻转 Delaunay 生成的多边形对以匹配轮廓
- 内部夹孔
结果（请忽略紫色轮廓）：
