德劳内三角测量带孔的 2d 多边形
2022-09-03 14:51:19
我想用孔对复杂（但不是自相交）多边形进行三角测量，以便生成的三角形全部位于多边形内部，完全覆盖该多边形，并遵守Delaunay三角形规则。
显然，我可以为所有点构建Delaunay三角测量，但我担心多边形的某些边不会包含在生成的三角测量中。
那么，这种三角测量可能吗？如果是，我该怎么做？
以防万一 - 我需要它来构造多边形内侧轴的近似值（我希望它可以通过连接所得到的三角形的所有圆周点来完成）。
答案 2
这是我在为RTS游戏做navmesh时想出的方法之一。请注意，它是自制的，没有使用第三方工具，我花了大约3周的时间来实现和修复错误：
- 将所有点馈送到德劳尼三角测量中（以获得最均匀的三角形）
- 检查孔轮廓并翻转Delaunay生成的多边形对以匹配轮廓
- 夹孔内脏
结果（请忽略紫色轮廓）：
推荐
