C++如何计算一组地理坐标点的凸包（Convex Hull）-C++-PHP中文网

优先选graham扫描法：时间复杂度稳定o(n log n)，排序后用叉积判断左转、显式处理共线点，避免jarvis步进法在大量共线点时退化至o(n²)。

c++如何计算一组地理坐标点的凸包（convex hull）

凸包算法选哪个？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++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

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）。否则要么排序错，要么栈弹出逻辑漏判。