Delaunay 对带孔的二维多边形进行三角剖分
我想对带有孔的复杂（但不是自相交）多边形进行三角剖分，以便生成的三角形全部位于多边形内部，完全覆盖该多边形，并遵守 Delaunay 三角形规则。
显然，我可以为所有点构建 Delaunay 三角剖分，但我担心多边形的某些边不会包含在生成的三角剖分中。
那么，这样的三角测量可能吗？如果是的话，我该怎么做？
以防万一 - 我需要它来构造多边形中轴的近似值（我希望它可以通过连接所得三角形的所有圆周点来完成）。
I want to triangulate the complex (but not self-intersecting) polygon with holes, so that resulting triangles all lay inside the polygon, cover that polygon completely, and obey the Delaunay triangle rules.
Obviously, I could just build the Delaunay triangulation for all points, but I fear that some edges of the polygon will not be included into resulting triangulation.
So, is such triangulation possible? And if yes, how can I do it?
Just in case - I need it to construct the approximation of polygon medial axis (I hope it can be done via connecting all circumference points of resulting triangles).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
听起来您想要约束 Delaunay 三角剖分。 “洞”可以通过约束输入边缘以在三角测量中保持完整来实现。
请参阅三角形和poly2tri 项目。
It sounds like you want constrained Delaunay triangulation. The "holes" can be implemented by constraining input edges to remain unbroken in the triangulation.
See the Triangle and poly2tri projects for implementations.
这是我在为 RTS 游戏制作导航网格时想到的方法之一。请注意，它是自制程序，没有使用第三方工具，我花了大约 3 周的时间来实现和错误修复：
结果（请忽略紫色轮廓）：
Here's one of the methods I came up with when doing navmesh for an RTS game. Note that it is homebrew, no third-party tools were used, it took me about 3 weeks to implement and bugfix:
Result (plz ignore purple outlines):