湖床测量船地面站多GPS点栅格规划路径分割算法咨询

参考效果 #

以下为Measure Ground Control软件输出的规划路径效果，为本次开发的对齐目标：
Measure Ground Control规划路径参考图1
Measure Ground Control规划路径参考图2

现状说明 #

目前已在ESP32平台完成4个GPS点（矩形测区）场景的路径生成开发，现有代码硬编码了矩形边界的边配对逻辑，无法适配GPS点数量大于4的任意多边形测区，现有实现代码如下：

double get_target_list (int i, int _step_no, double _target_1, double _target_2, double _target_3, double _target_4){
    double _target_list = 0;
    int k_int = 0;
    int mod_4 = 0;
    k_int = i/4;
    mod_4 = i%4;

    if (mod_4 == 0)
        _target_list = get_target((2*k_int), _step_no, _target_1, _target_2);

    if (mod_4 == 1)
        _target_list = get_target((2*k_int+1), _step_no, _target_1, _target_2);

    if (mod_4 == 2)
        _target_list = get_target((2*k_int), _step_no, _target_4, _target_3);

    if (mod_4 == 3)
        _target_list = get_target((2*k_int+1), _step_no, _target_4, _target_3);

    return _target_list;
}

相关技术关键词 #

• 牛耕式（弓字形）覆盖路径规划（Boustrophedon Coverage Path Planning）
• 多边形扫描线算法（Scanline Algorithm）
• WGS84转UTM平面坐标投影
• 凸/凹多边形线段求交
• 航点最近邻排序优化

核心实现步骤 #

现有4点代码的本质是硬编码了矩形测区两对平行边的往复扫线逻辑，适配任意N点测区只需替换为通用多边形扫描流程，即可和Measure Ground Control的输出效果完全对齐：

1. 坐标预处理
   所有输入GPS经纬度点先转换为UTM平面坐标（单位为米），所有几何计算全部在平面坐标系下完成，最终生成的航点再转回WGS84经纬度输出。禁止直接在经纬度坐标系下做距离计算、线段求交，球面坐标的非线性误差会导致测线间距不准、路径偏移。
2. 测区多边形校验清洗
   将输入的N个GPS点按输入顺序组成闭合多边形，先做基础数据清洗：剔除距离过近的重复点，统一顶点的顺时针/逆时针环绕顺序，简单校验多边形是否存在自相交（常规湖床测量测区均为无自相交的简单多边形）。
3. 平行扫描线生成
   先确定扫测方向：默认取测区最小外接矩形的长边方向，可最大程度减少无效折返次数，和Measure Ground Control的默认设置一致，也可预留参数支持手动输入扫测方向角。再根据声呐有效扫幅宽度设置测线间距，生成一组平行于扫测方向、等间距的扫描线，完全覆盖整个测区的外接矩形范围。
4. 有效作业航段提取
   逐根计算扫描线和测区多边形所有边的交点，将同一条扫描线上的交点沿扫描线延伸方向排序，两两配对即为该扫描线落在测区内部的有效作业航段。注意处理扫描线恰好经过多边形顶点的边界情况，避免出现交点重复、遗漏导致的航段断裂。

   凹多边形场景下单条扫描线可能和多边形产生2个以上交点，会拆分为多段不连续的作业航段，属于正常情况。

5. 航点拼接输出
   按相邻扫描线交替反向的弓字形规则拼接航段：第一条航段从起点航行至终点，下一条航段选择距离上一终点最近的端点作为起点，航行至另一端点，依次往复遍历所有航段，最终按顺序存储所有端点即为输出航点列表。凹多边形的多段航段同样按最近邻原则衔接即可，输出效果和商用地面站一致。

ESP32平台适配优化建议 #

• 不需要引入重型计算几何库，UTM坐标转换、线段求交的逻辑都可以用精简版代码实现，单测区顶点数不超过100的场景下，ESP32的算力和RAM完全足够。
• 原有4点矩形场景的逻辑不需要完全废弃，本质是通用扫描线算法在矩形场景下的特例，可以保留作为快速计算分支。
• 测线间距直接用平面坐标下的米级距离计算，不要用经纬度差估算，保证声呐扫测的重叠率符合湖床测量的精度要求。

参考方向 #

可以参考开源地面站的航测区域规划模块代码，核心扫线逻辑和Measure Ground Control完全同源，无特殊闭源算法。

内容的提问来源于stack exchange，提问作者triệu trinh