无排序Graham扫描求简单多边形凸包失败的问题排查求助

理论上，Graham扫描算法处理简单多边形的凸包时，可利用顶点已有的有序性实现线性时间求解，无需nlogn复杂度的排序步骤。我实现的带角度排序的Graham扫描算法运行正常：

function ccw(a: Vertex, b: Vertex, c: Vertex) {
    return (b.y - a.y)*(c.x - a.x) - (b.x - a.x)*(c.y - a.y);
}

// Graham Scan Convex Hull Algorithm
// This is destructive
export function convexHull(points: Vertex[]) {
    const n = points.length;
    if (n <= 3) return points;
    
    // Assume the first point is bottom-left-most
    const p0 = points[0];

    // Sort by angle
    points.sort((a, b) => {
        const c = ccw(p0, a, b);
        return c === 0 ? a.x - b.x : c;
    });

    // Keep points in the result if they "turn left"
    let len = 1;
    for (let i = 1; i < n; i++) {
        let b = points[len-1];
        let c = points[i];
        //if (b.x === c.x && b.y === c.y) { continue; } // identical points are already filtered out
        if (len >= 2) {
            let a = points[len-2];
            while (ccw(a, b, c) >= 0) {
                len--;
                if (len < 2) { break; }
                b = a;
                a = points[len-2];
            }
        }
        points[len++] = c;
    }
    points.length = len;
    return points;
}

注：多边形输入已预先旋转，确保points[0]为最左下角顶点

针对半径为1的简单六角星测试数据：

[
  { x: 0, y: -1 },
  { x: 0.2886751345948129, y: -0.5 },
  { x: 0.8660254037844387, y: -0.5 },
  { x: 0.5773502691896257, y: 0 },
  { x: 0.8660254037844387, y: 0.5 },
  { x: 0.28867513459481287, y: 0.5 },
  { x: 0, y: 1 },
  { x: -0.28867513459481287, y: 0.5 },
  { x: -0.8660254037844387, y: 0.5 },
  { x: -0.5773502691896257, y: 0 },
  { x: -0.8660254037844387, y: -0.5 },
  { x: -0.2886751345948129, y: -0.5 }
]

带排序的算法可得到正确的外接六边形结果：

[
  { x: 0, y: -1 },
  { x: 0.8660254037844387, y: -0.5 },
  { x: 0.8660254037844387, y: 0.5 },
  { x: 0, y: 1 },
  { x: -0.8660254037844387, y: 0.5 },
  { x: -0.8660254037844387, y: -0.5 }
]

但移除角度排序步骤后，即使输入是简单多边形，结果会额外添加一个内部顶点：

[
  { x: 0, y: -1 },
  { x: 0.8660254037844387, y: -0.5 },
  { x: 0.8660254037844387, y: 0.5 },
  { x: 0, y: 1 },
  { x: -0.8660254037844387, y: 0.5 },
  { x: -0.8660254037844387, y: -0.5 },
  { x: -0.2886751345948129, y: -0.5 }
]

现寻求以下帮助：

• 对移除排序后Graham扫描的错误问题进行调试指导
• 推荐合适的替代算法：
  • 希望找到Lee算法的完整参考实现或伪代码
  • 可考虑Melkman算法，但无需在线构建功能，且希望尽量避免使用双端队列，仅用栈实现

内容的提问来源于stack exchange，提问作者Logan R. Kearsley