基于耳切算法的带孔洞多边形三角化死循环问题排查

核心问题：顶点顺序与凸性判断逻辑不匹配 #

你的耳切算法陷入死循环的直接原因是cross(AB, AC)始终为负，导致从未进入耳的检测分支，循环无法推进。这本质是多边形顶点顺序和凸顶点判断逻辑不匹配，加上孔洞合并后顶点顺序混乱导致的。

1. 顶点顺序一致性问题 #

耳切算法要求输入是简单多边形（无自交）且顶点按统一的顺时针/逆时针顺序排列。合并内外轮廓（孔洞）时，很容易出现顶点方向混合（比如外轮廓逆时针、内轮廓顺时针），导致整个多边形的顶点顺序混乱，所有顶点处的叉乘符号一致为负，无法找到符合条件的凸顶点。

修复：统一顶点顺序为逆时针
先计算多边形的有向面积判断当前方向，反转顺序统一为逆时针：

const float EPS = 1e-6f;

float polygon_signed_area(polygon Poly) {
    float area = 0.0f;
    int n = Poly.Count;
    for(int i = 0; i < n; ++i) {
        int j = (i + 1) % n;
        area += Poly.Elements[i].x * Poly.Elements[j].y - Poly.Elements[j].x * Poly.Elements[i].y;
    }
    return area * 0.5f;
}

void reverse_polygon(polygon* Poly) {
    int n = Poly->Count;
    for(int i = 0; i < n/2; ++i) {
        vec2 temp = Poly->Elements[i];
        Poly->Elements[i] = Poly->Elements[n-1 - i];
        Poly->Elements[n-1 - i] = temp;
    }
}

在三角化函数开头添加：

float signed_area = polygon_signed_area(SimplePolygon);
if(signed_area < -EPS) { // 顺时针转为逆时针
    reverse_polygon(&SimplePolygon);
}

2. 凸顶点判断逻辑错误 #

代码中选取的三个连续顶点是B（前一个）→A（当前）→C（后一个），计算叉乘cross(AB, AC)（其中AB=B-A，AC=C-A）。对于逆时针顺序的多边形，凸顶点的该叉乘结果应为≤0，但你代码中判断条件是>=0，完全写反了，导致所有凸顶点都被跳过。

修复：修正凸顶点判断条件
把：

if(cross(AB, AC) >= 0.0f) {

改为：

if(cross(AB, AC) <= EPS) { // 用EPS处理浮点数精度问题

3. 浮点数精度问题 #

代码中直接用A != B判断点是否重合，浮点数运算存在精度误差，容易误判共线或接近重合的点，导致叉乘计算异常。

修复：用epsilon判断点是否相等
添加向量相等判断函数：

bool vec2_equal(vec2 a, vec2 b) {
    return fabs(a.x - b.x) < EPS && fabs(a.y - b.y) < EPS;
}

替换原有check：

check(!vec2_equal(A,B) && !vec2_equal(A,C) && !vec2_equal(B,C));

4. 死循环保护 #

如果多边形存在自交、严重的顺序问题或共线点，可能仍然找不到耳，陷入死循环。添加标记判断是否找到耳，触发错误检查：

while(IndexCount > 3) {
    bool found_ear = false;
    for(int Index = 0; Index < IndexCount; ++Index) {
        // ... 原有顶点获取、叉乘计算逻辑 ...
        if(cross(AB, AC) <= EPS) {
            // ... 耳检测逻辑 ...
            if(IsEar) {
                // ... 生成三角形、删除顶点逻辑 ...
                found_ear = true;
                break;
            }
        }
    }
    check(found_ear && "Failed to find ear: polygon may be self-intersecting or have invalid vertex order");
}

5. 点在三角形内的判断验证 #

is_point_in_triangle函数中，三角形顶点顺序是B→A→C（顺时针），判断三个叉乘都≤0是正确的。但如果后续调整了三角形顶点顺序，需要同步修改判断逻辑：确保三角形顶点顺序一致，且所有叉乘符号与第一个叉乘符号相同（允许零）。

额外检查项 #

• 确认合并孔洞后的多边形是简单多边形：没有自交边，所有边仅在顶点处相交。可以遍历所有边对，检查是否存在非顶点的交点。
• 检查点集是否存在重复顶点：合并孔洞时可能引入重复点，需要去重（用epsilon判断）。

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