多边形的三角剖分

Question

我正在尝试对在3d模型中使用的多边形进行三角剖分。当我尝试对点如下所示的多边形使用耳法时，会得到红线所在的三角形。由于这些三角形内没有其他点，因此这可能是正确的。但是我只希望它对黑线内的区域进行三角剖分。任何人都知道会执行此操作的算法吗？

Answer 1

有许多用于对多边形进行三角剖分的算法，不需要首先将其划分为单调多边形。我的教科书 C语言中的计算几何学 中对此进行了描述，该书中有代码可以从该链接免费下载（使用C或Java）的与之关联的文件。 首先必须具有与边界遍历相对应的点。我的代码假定为逆时针方向，但是当然很容易更改。另请参见维基百科文章。也许这是您的问题，因为您没有一致地组织边界点？

Answer 2

通常的方法是使用梯形分解将简单多边形拆分为单调多边形，然后对单调多边形进行三角剖分。 第一部分可以使用扫掠线算法来实现。正确的数据结构（例如双重连接的边列表）可以加快速度。我知道的最好的描述可以在计算几何中找到。此和这似乎也很有帮助。

Answer 3

Wikipedia建议将多边形分解为单调多边形。您只需检查所有小于180度的角度即可检查多边形是否为凹面-任何角度大于180度的角都是凹面，您需要在该角处将其折断。

Answer 4

如果可以使用C ++，则可以使用 CGAL ，尤其是给出此处，可以对一组非相交的多边形进行三角剖分。仅当您已经知道黑线段时，此示例才有效。

Answer 5

您需要使用EarClipping算法，而不是Delaunay。请参阅以下白皮书： http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf