Jarvis March凸包算法JavaScript实现部分用例触发死循环求解

死循环核心成因 #

• 隐式变量问题：代码中newhull没有提前声明，属于隐式全局变量，会引发变量污染，极端情况下会干扰循环终止条件判断。
• 共线点选择逻辑错误：当前逻辑只要点i在p和当前q的线段上就更新q为i，当存在大量共线点时，会出现p和q反复切换的情况，导致do-while永远无法回到起始点l，触发死循环。正确逻辑应该选择距离p最远的共线点作为q，避免循环跳转。
• 凸包闭合逻辑错误：最后收集边线上共线点的代码中，当i是hull最后一个元素时，hull[i+1]为undefined，最后一条凸包边（最后一个顶点到起始顶点的连线）没有被正确处理，会引发逻辑异常。
• 边界场景缺失兼容：所有输入点共线时，凸包退化为线段，现有逻辑无法回到起始点，也会陷入死循环。

修复步骤 #

1. 补充标准辅助函数实现，可先对照你现有实现核对逻辑：

// 返回值：0=共线，1=顺时针，2=逆时针
function orientation(p, q, r) {
    const val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    if (val === 0) return 0;
    return val > 0 ? 1 : 2;
}
// 判断r是否在p和q的线段上
function onSegment(p, q, r) {
    return r.x <= Math.max(p.x, q.x) && r.x >= Math.min(p.x, q.x) &&
           r.y <= Math.max(p.y, q.y) && r.y >= Math.min(p.y, q.y);
}
// 计算两点距离平方，避免开方开销
function distSq(p, q) {
    return (p.x - q.x) ** 2 + (p.y - q.y) ** 2;
}

2. 补充变量声明，修改do-while循环内的q更新逻辑：

function convexHull(points) {
    const n = points.length;
    if (n < 3) return;
    let l = 0;
    let hull = [];
    let newhull = []; // 提前声明变量
    // 原有找最左点逻辑不变
    for (let i = 1; i < n; i++) {
        if (points[i].x < points[l].x)
            l = i;
        else if (points[i].x == points[l].x && points[i].y < points[l].y)
            l = i;
    }
    let p = l, q;
    do {
        hull.push(points[p]);
        newhull.push(points[p]);
        q = (p + 1) % n;
        for (let i = 0; i < n; i++) {
            const o = orientation(points[p], points[i], points[q]);
            // 更逆时针则更新q
            if (o === 2) {
                q = i;
            }
            // 共线时选距离p更远的点，避免循环
            else if (o === 0) {
                if (distSq(points[p], points[i]) > distSq(points[p], points[q])) {
                    q = i;
                }
            }
        }
        p = q;
    } while (p != l);
    // 兼容全共线场景：hull长度为2说明所有点共线，直接返回即可
    if (hull.length === 2) return newhull;
    // 修复共线点收集逻辑的索引问题
    for(let i = 0; i < hull.length; i++) {
        // 用取余实现凸包闭合，避免索引越界
        const nextP = hull[(i+1)%hull.length];
        for (let j = 0; j < points.length; j++) {
            if(orientation(hull[i], points[j], nextP) == 0 && onSegment(hull[i], nextP, points[j])) {
                newhull.push(points[j]);
                points.splice(j, 1);
                j--; 
            }
        }
    }
    return newhull;
}

优化方向 #

• 可以提前对输入点做去重处理，避免重复点引发的逻辑异常。
• 收集共线点的逻辑可以和顶点选择逻辑合并，不需要二次遍历修改原数组，splice操作开销很高，还会产生修改原数组的副作用。
• 可以去掉参数n，直接用points.length获取长度，避免传参不一致的问题。

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