简单的2D多边形三角 [英] Simple 2d polygon triangulation

问题描述

试图三角一套的简单的2D多边形，我想出这个算法：

Trying to triangulate a set of simple 2d polygons, I've come up with this algorithm:

• 1）为在该多边形的每个顶点，计算两个相连边缘间的角度
• 2）分类顶点通过减少相对角，以该多边形的内部
• 3）如果少于3个顶点的集合，我们就大功告成了
• 4）采取由它和它的两个邻国形成了集和输出三角形的最后一个顶点
• 5）从集合中删除顶点
• 6）更新两个邻国的角度
• 7）跳转到2

我测试过它，并发现它的工作即使在真正的大而复杂的简单的2D多边形（它没有为多边形孔或自相交的多边形工作）。

I've tested it, and found it to work even on really big and complicated simple 2d polygon (it don't work for polygon with a hole or self intersecting polygons).

有没有其他的情况会产生退化的结果呢？

Is there corner cases that will produce degenerate result?

请问这个算法是一个已知的？

Does this algorithm is a known one?

如果没有，我想，以确保该算法是坚如磐石，但我没有数学背景来证明这一点。

If not, I would like to be sure this algorithm is rock solid but I have not the mathematical background to prove it.

多谢了。

推荐答案

您正在做一个版的耳朵削波的方式进行三角测量，请参阅：的 http://en.wikipedia.org/wiki/Polygon_triangulation

You are doing a version of "ear clipping" approach to triangulation, see: http://en.wikipedia.org/wiki/Polygon_triangulation

如果另一多边形顶点（比如从多边形的另一侧）结束了三角形的耳朵你形成在你的算法失败。考虑这个例子：

Your algorithm fails if another polygon vertex (say from the other side of the polygon) ends up inside the triangle 'ear' you form. Consider this example:

您的算法将选择的第一，并与这两个相邻的边缘（用虚线连接的）一个三角形。但这个三角形包括另一个顶点（B）和显然是不正确。

Your algorithm will choose A first, and make a triangle with the two adjacent edges (connected with the dashed line). But this triangle includes another vertex (B) and is clearly incorrect.

广义耳裁剪方法取决于找到的耳朵，你可以剪掉不具有任何包括顶点。

The generalized ear clipping approach depends on finding ears you can clip off that do not have any included vertices.

这篇关于简单的2D多边形三角的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！