简单的二维多边形三角剖分 [英] Simple 2d polygon triangulation

问题描述

试图对一组简单的二维多边形进行三角测量，我想出了这个算法:

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

我已经对其进行了测试，发现它甚至可以在非常大且复杂的简单二维多边形上工作(它不适用于带孔的多边形或自相交多边形).

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?

这个算法是已知的吗?

如果不是，我想确定这个算法是坚如磐石的，但我没有数学背景来证明它.

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:

您的算法将首先选择 A，并用两条相邻的边(用虚线连接)制作一个三角形.但是这个三角形包含另一个顶点 (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.

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