C++凸包算法Graham扫描法怎么按极角排序极点-C++-PHP中文网

极点必须是y最小（y相同时x最小）的点，否则极角排序失效、叉积判断出错；需用std::min_element找极点，再按叉积和距离排序。

c++凸包算法graham扫描法怎么按极角排序极点

极点选错会导致整个凸包错乱

极点必须是所有点中 y 坐标最小（y 相同时 x 最小）的那个点，不能随便取原点或第一个点。选错后，极角排序失去参考基准，后续叉积判断方向会系统性出错，生成的“凸包”可能自交或漏点。

实操建议：

遍历所有点，用 std::min_element 配合自定义比较器找极点：

Point pivot = *std::min_element(points.begin(), points.end(),
    [](const Point& a, const Point& b) {
        return a.y

找到后，把 pivot 交换到 points[0] 位置，方便后续以索引 0 为基准做极角排序
别在排序时动态重算极点——极点必须固定，否则 atan2 或叉积比较会因基准漂移而失效

用叉积比 `atan2` 更稳、更快

很多人第一反应是用 atan2(dy, dx) 算每个点相对于极点的角度再排序，但浮点误差+象限边界（如 atan2(0,-1) vs atan2(-0,-1)）容易导致顺序错乱，且 atan2 计算开销大。

正确做法是用叉积符号作为排序依据：

对任意两点 A、B（都 ≠ 极点 P），计算向量 PA × PB，即 (A.x - P.x)*(B.y - P.y) - (A.y - P.y)*(B.x - P.x)
若结果 > 0：说明 B 在 PA 的逆时针方向 → A 应排在 B 前面
若结果 == 0：共线，此时按到极点的距离升序排（近的在前，保证扫描时远点不会被近点挡住）

排序函数示例：

std::sort(points.begin() + 1, points.end(), [pivot](const Point& a, const Point& b) {
    int cross = (a.x - pivot.x) * (b.y - pivot.y) - (a.y - pivot.y) * (b.x - pivot.x);
    if (cross != 0) return cross > 0;
    return dist2(pivot, a)

共线点处理不当会让凸包“塌陷”

Graham 扫描法默认只保留最外层点，但若多个点与极点共线，仅靠叉积为 0 判断还不够：必须确保距离极点最远的那个点留下，其余共线中间点要剔除，否则栈里会塞进不该存在的点，导致最终凸包边不直、顶点冗余甚至凹陷。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

关键动作在排序后、扫描前：

从排序后的数组尾部向前遍历，跳过所有与极点和前一点共线的点（即连续三点叉积为 0）
更稳妥的做法是在排序时就压缩共线段：对每组叉积为 0 的连续块，只保留距离极点最远的一个点
不要依赖排序后自动去重——std::unique 对浮点坐标不可靠，且不解决“该留远点还是近点”的逻辑问题

扫描过程栈顶检查必须用严格叉积符号

排序只是准备，真正构建凸包靠的是单调栈和叉积判向。常见错误是写成 cross 就弹栈，这会让三点共线时也弹出中间点，破坏凸包完整性（尤其当题目要求输出所有共线边界点时）。

务必根据题意选择：

求**严格凸包**（顶点间无三点共线）→ 弹栈条件：cross
求**最小凸包闭包**（保留所有位于边界上的点）→ 弹栈条件：cross ，共线点保留在栈中
每次检查用栈顶两个点 + 当前点构成的叉积：cross = (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x)，其中 p0 是栈底倒数第二点，p1 是栈顶，p2 是当前点

极角排序本身不难，难的是每个环节的判定条件都绑定着几何意义——叉积正负、零值处理、距离比较、栈弹入规则，任意一处松动，凸包就不是你想要的那个。