德劳内三角二维多边形孔 [英] Delaunay triangulating the 2d polygon with holes

问题描述

我想三角复杂（但不自相交）多边形孔，这样产生的三角形都打好多边形内，涵盖多边形完全，并服从德劳内三角规则。

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.

很显然，我可以只建立Delaunay三角的所有点，但我担心，多边形的一些边缘将不会被纳入造成三角。

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).

推荐答案

这听起来像你想的约束Delaunay三角。的洞可以通过约束输入的边缘保持完整的三角测量来实现。

It sounds like you want constrained Delaunay triangulation. The "holes" can be implemented by constraining input edges to remain unbroken in the triangulation.

查看三角和的poly2tri 项目的实施。

这篇关于德劳内三角二维多边形孔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！