优先选Graham扫描法：时间复杂度稳定O(n log n)，排序后用叉积判断左转、显式处理共线点，避免Jarvis步进法在大量共线点时退化至O(n²)。
凸包算法选哪个？Graham 扫描比 Jarvis 步进更稳
直接用 Graham 扫描法，别碰 jarvis march（尤其是点数超过 1000 时）。后者最坏 O(n²)，实际中容易卡在退化场景（比如大量共线点或近似共线），而 Graham 稳定 O(n log n)，且 C++ 标准库没内置凸包函数，必须手写或依赖轻量库。
常见错误是先按极角排序再逐点判断叉积符号，但漏处理共线点——结果可能把内部点误判为顶点，或漏掉共线边上的端点。正确做法是在排序后对共线点按距离极点远近二次排序，并在主循环中显式跳过中间共线点。
- 极点选 y 最小（y 相同时 x 最小）的点，避免 atan2 计算误差和边界除零
- 排序用
std::sort+ 自定义比较器，别用atan2，改用叉积判断相对位置 - 叉积计算用
long long防 int 溢出，地理坐标经度纬度乘 1e6 转整数再算
坐标要不要投影？WGS84 下直接算会偏
WGS84 经纬度不是欧氏平面，两点间“直线”其实是大圆弧，直接套用平面凸包算法，结果在高纬度区域明显内凹（比如北欧一堆点，凸包边会弯向北极）。必须先投影——但不用 GIS 全家桶，EPSG:3857（Web Mercator）足够应付大多数可视化场景，且有轻量转换公式。
实操建议：用 lat, lng → x, y 的墨卡托投影（注意纬度上限 85.0511°，超限直接 clamp），再跑 Graham；输出顶点后逆投影回经纬度。别用 proj 库，几行代码就能写完：
立即学习“C++免费学习笔记（深入）”；
double lat_rad = lat * M_PI / 180.0; double x = lng * M_PI / 180.0; double y = log(tan(M_PI/4.0 + lat_rad/2.0)); // 再乘地球半径 R = 6378137.0 得米制坐标
- 如果只是画图或粗略包围，且点全在纬度 ±30° 内，可跳过投影，误差通常
- 若需精确地理意义（如围栏面积计算），必须用等距圆柱投影或 UTM 分带，但得知道中心经度
- 所有坐标统一转成
double，别混用float，纬度差 0.0001° 在赤道约 11 米，float 有效位不够
怎么验证凸包顶点顺序对不对？检查叉积符号一致性
输出顶点数组 hull 后，立刻验证：对每三个连续点 hull[i-1], hull[i], hull[i+1]（循环索引），计算叉积 cross(hull[i]-hull[i-1], hull[i+1]-hull[i])，所有结果必须同号（全 ≥0 或全 ≤0）。否则要么排序错，要么栈弹出逻辑漏判。
- 叉积为 0 表示三点共线——允许，但只保留首尾两个端点，中间点必须剔除
- 顺时针还是逆时针取决于你叉积定义方式，只要一致就行；GIS 系统通常要逆时针（外环），OpenGL 渲染也偏好逆时针
- 用
assert加一层校验：hull.size() < 3 || cross(...) * cross(...) >= 0，上线前关掉，调试时开
点太多（>10⁵）怎么办？先格网抽稀再算凸包
纯 Graham 到 10⁵ 点时，排序和扫描本身不慢，但投影转换和浮点运算误差开始累积，尤其墨卡托在高纬度拉伸严重。这时不能硬算，得预处理。
简单有效的方法：用固定大小网格（比如 0.1°×0.1°）覆盖全部点，每个格网只保留离中心最近的点，再对抽稀后点集求凸包。实测 50 万 GPS 轨迹点，抽到 2000 点内，凸包形状保真度 >95%，耗时降为原来的 1/20。
- 格网大小按业务精度定：0.01° ≈ 1km（赤道），城市级用 0.005°，省级用 0.1°
- 别用随机采样——会丢掉关键拐点；格网法天然保留边缘点
- 抽稀后仍要重跑凸包，不能直接用原凸包缩放，投影非线性，缩放会变形
真正难的是共线点密集又跨投影边界的场景，比如国际日期变更线附近的航线点——这时候得切分、分别投影、再合并凸包，手动处理边界点。这种 case 少，但一旦出现，调试花的时间比写算法还长。
