凸多边形三角剖分：如何实现支持多顶点的简单分割方法

原代码的问题定位 #

你编写的代码仅能正常处理4顶点多边形的核心原因有两点：

• 操作顺序错位：拼接三角形时先执行poly.pop(1)修改了列表结构，之后再读取poly[-2]的元素，当顶点数超过4时，取到的顶点已经不是原本连续相邻的节点了
• 选取的三角形顶点不连续：以5顶点序列[A,B,C,D,E]为例，原代码第一轮循环会生成三角形[A,B,D]，三个节点中B和D间隔了顶点C，不属于多边形上连续相邻的节点，切下这个三角形会把剩余顶点（比如C）甩在剖分区域外，最终的三角形集合既会出现边界交叉，也无法完整覆盖整个多边形。
• 仅当顶点数为4时，原代码的索引刚好匹配连续相邻的要求（生成三角形[A,B,C]，剩余顶点组成[A,C,D]），因此可以正常输出结果，顶点数更多时逻辑就完全失效了。

拿5顶点输入跑原代码的实际输出为：[[A,B,D], [A,C,D], [A,D,E]]，存在明显的边界交叉和覆盖遗漏问题。

适配逻辑说明 #

你需要剖分的是无大于180°内角的凸多边形，不需要引入复杂的凹点判断、方向检测逻辑——凸多边形中所有连接不相邻顶点的对角线都在多边形内部，任意选取三个连续相邻的顶点，切下一个耳形三角形后，剩余的节点依然组成一个少1个顶点的凸多边形，重复这个切耳过程直到剩下3个顶点，就能得到合法的三角剖分结果。

凸多边形的三角剖分没有唯一标准答案，只要满足无交叉、无重叠、完整覆盖多边形区域的要求都是正确的，你示例中的[A,B,C]、[A,C,E]、[C,D,E]就是其中一种合法的剖分方案。

修正后的实现 #

只要把原代码中错位的顶点选取逻辑替换为“连续相邻三顶点切耳”，就能适配任意顶点数的凸多边形剖分：

def turnIntoTriangles(poly):
    triangles = []
    # 复制传入的顶点列表，避免修改原输入数据
    remaining = poly.copy()
    
    while len(remaining) > 3:
        # 选取列表前三个连续相邻的顶点组成耳三角形
        ear = [remaining[0], remaining[1], remaining[2]]
        triangles.append(ear)
        # 移除被切下的中间顶点，保持剩余顶点的相邻顺序
        remaining.pop(1)
    
    # 剩余的3个顶点组成最后一个收尾三角形
    triangles.append(remaining)
    return triangles

上述代码对5顶点输入的输出为[[A,B,C], [A,C,D], [A,D,E]]，这是符合剖分要求的合法结果，和你示例中的剖分只是方案差异；如果需要得到示例中特定顺序的剖分结果，只需要调整每次切耳时选取的相邻顶点位置即可——因为是凸多边形，不需要额外的几何校验，只要三个点保持邻接顺序，切耳的位置不会影响剖分的合法性。

对应剖分的示意图：

内容的提问来源于stack exchange，提问作者DinosaurMoritz