试图三角化一组简单的 2d 多边形，我想出了这个算法：
我已经对其进行了测试，发现它甚至可以在非常大且复杂的简单二维多边形上工作（它不适用于带有孔的多边形或自相交的多边形）。
是否存在会产生退化结果的极端情况？
这个算法是已知的吗？
如果不是，我想确定这个算法是坚如磐石的，但我没有数学背景来证明它。
非常感谢。
您正在对三角测量进行一种“剪耳”方法，请参阅： http ://en.wikipedia.org/wiki/Polygon_triangulation
如果另一个多边形顶点（例如从多边形的另一侧）最终位于您形成的三角形“耳朵”内，则您的算法将失败。考虑这个例子：
您的算法将首先选择 A，并用两个相邻边（用虚线连接）制作一个三角形。但是这个三角形包括另一个顶点（B），显然是不正确的。
广义的耳朵剪裁方法取决于找到可以剪掉的没有任何包含顶点的耳朵。
这是当您想要处理简单的多边形时，如矩形、五边形、六边形等。在这里，您只需取一个起点并将其连接到所有其他顶点。这个算法很简单，我真正想要的是一个更通用的解决方案，可以处理凹面和带孔的多边形。
为了处理更复杂的多边形，比如 Payne 提供的...
虽然有些算法运行得更快，但更快的算法变得非常复杂。柯克帕特里克等人。找到了一个在 O(n log log n) 中运行的算法，而Chazelle在 O(n) 中完成了它。然而，最容易实现的可能是运行时间为 O(n log n)的Seidel 算法。
该算法是一个 3 步过程
如果您对 C 源代码感兴趣，可以从北卡罗来纳大学教堂山分校获得。一般来说，代码质量很好，可以处理漏洞，但可能需要根据您的需要进行调整。
如果我对您的理解正确，那么您将从最小的内角开始切掉三角形。如果多边形不是凸的，这可能会失败。考虑一个多边形，其顶点（按顺序）位于：(0,0) (10,9) (9,9) (9,10)。最小的角度是原点的角度，但你不能安全地切断那个三角形。
（如果你的多边形是凸的，那么你可以选择任何顶点，在那里删除一个三角形，然后重复。所以我猜你希望你的算法即使对非凸多边形也能工作。）