我想用孔对复杂的（但不是自相交的）多边形进行三角剖分，以便生成的三角形都位于多边形内，完全覆盖该多边形，并遵守德劳内三角形规则。
显然，我可以为所有点构建 Delaunay 三角剖分，但我担心多边形的某些边缘不会包含在生成的三角剖分中。
那么，这样的三角测量可能吗？如果是，我该怎么做？
以防万一-我需要它来构造多边形中轴的近似值（我希望可以通过连接生成的三角形的所有圆周点来完成）。
问问题
9324 次
2 回答
11
听起来您想要受约束的 Delaunay triangulation。“洞”可以通过约束输入边在三角剖分中保持不间断来实现。
于 2011-04-26T19:46:08.393 回答
4
这是我在为 RTS 游戏做 navmesh 时想到的方法之一。请注意，它是自制的，没有使用第三方工具，我花了大约 3 周的时间来实现和修复错误：
- 将所有点输入 Delaunay 三角剖分（以获得最均匀的三角形）
- 沿孔轮廓检查并翻转由 Delaunay 生成的多边形对以匹配轮廓
- 夹孔内脏
结果（请忽略紫色轮廓）：
于 2013-12-04T13:33:48.093 回答