C++实现Graham Scan凸包算法返回错误路径问题求助

1. 致命语法错误：Vector2D 加减运算符实现错误 #

你写的加减法运算符误用了逗号表达式，没有正确构造Vector2D对象：

// 错误写法
Vector2D Vector2D::operator+(const Vector2D& aRHS) const
{
    return (fX + aRHS.fX, fY + aRHS.fY);
}

逗号表达式会先计算左边的fX + aRHS.fX然后丢弃，最终返回仅传入y值的Vector2D对象，所有向量运算完全失效。
修正方案：

Vector2D Vector2D::operator+(const Vector2D& aRHS) const
{
    return Vector2D(fX + aRHS.fX, fY + aRHS.fY);
}
// 减法同理修正
Vector2D Vector2D::operator-(const Vector2D& aRHS) const
{
    return Vector2D(fX - aRHS.fX, fY - aRHS.fY);
}

2. 方向计算逻辑错误 #

Vector2D::direction()用atan(fY/fX)计算方向存在象限错误，atan的返回值范围只有[-π/2, π/2]，无法区分一/三象限、二/四象限的同斜率向量。
修正方案：改用atan2函数，覆盖全象限方向：

double Vector2D::direction() const
{
    return atan2(fY, fX);
}

3. 共线判断逻辑错误 #

Point2D::isCollinear当前计算的是两个点相对于全局坐标原点的叉乘，不是相对于凸包基准原点的叉乘，共线判断完全失效。
修正方案：基于两个点的相对向量计算叉乘，同时增加浮点精度判断：

bool Point2D::isCollinear(const Point2D& aOther) const
{
    Vector2D v1 = *this - getOrigin();
    Vector2D v2 = aOther - getOrigin();
    return fabs(v1.cross(v2)) < 1e-8;
}

4. 极角排序基准错误 #

你在buildConvexHull排序前，没有将所有点的Origin设置为找到的最低点（凸包基准点），导致极角排序是基于全局坐标原点而非凸包基准点，排序结果完全错误，这也是p12没有出现在凸包里的核心原因。
修正方案：排序前设置基准原点：

void Point2DSet::buildConvexHull(Point2DSet& aConvexHull)
{
    aConvexHull.clear();
    sort(orderByCoordinates);
    // 新增：将第一个点（y最小的基准点）设置为所有点的Origin
    for (auto& p : fPoints) {
        p.setOrigin(fPoints[0]);
    }
    sort(orderByPolarAngle);
    // 后续逻辑修改
}

5. Graham Scan遍历逻辑错误 #

当前遍历只弹出一次栈顶元素，正确逻辑是只要栈顶三个点不构成左拐，就要循环弹出栈顶；同时你跳过共线点的逻辑会误删凸包点。
修正方案：

void Point2DSet::buildConvexHull(Point2DSet& aConvexHull)
{
    // 前面排序、设Origin的逻辑省略
    aConvexHull.add(fPoints[0]);
    aConvexHull.add(fPoints[1]);
    for(size_t i = 2; i < size(); i++) 
    {
        // 循环弹出直到构成左拐
        while(aConvexHull.size() >= 2 && aConvexHull.doesNotTurnLeft(fPoints[i]))
        {
            aConvexHull.removeLast();
        }
        aConvexHull.add(fPoints[i]);
    }
    // 可选：添加第一个点闭合凸包，方便输出边
    aConvexHull.add(fPoints[0]);
}

6. 其他细节错误 #

• Point2D::operator<只比较y坐标，y相等时应该比较x坐标，确保找到y最小、x最小的基准点：

bool Point2D::operator<(const Point2D& aRHS) const
{
    if (fabs(fPosition.getY() - aRHS.getY()) > 1e-8) {
        return fPosition.getY() < aRHS.getY();
    }
    return fPosition.getX() < aRHS.getX();
}

• isClockwise函数中无用的val2计算可以删除，减少不必要的性能开销。

• 极角排序可以直接用叉乘判断，不需要计算atan2，既避免象限问题又提升性能。
• 共线点处理可以统一在排序阶段完成，极角相同的点保留距离最远的，遍历阶段不需要单独处理。
• 可以添加输入校验逻辑，避免点集数量小于3时的边界错误。

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