仿大疆司空2面状航线生成——凸多边形区域航线生成算法详解

仿大疆司空2面状航线生成——凸多边形区域航线生成算法详解一、前言去年在针对大疆上云API进行二次开发的过程中有一个需求是实现大疆司空2中的面状航线功能。在经过上网搜索后在github上找到了一个开源项目cpRPA植保无人机凸多边形地块工作路线规划可以实现面状航线的生成。参考项目地址https://github.com/Char-Ten/cpRPA经过对其中算法的研究感觉其实现方式非常值得学习遂用Java重新实现了相关的逻辑将其中的关键算法整理到本篇博客中。本篇博客仅作为学习整理使用由AI总结生成实际代码请查看原项目。下面将详细整理这一算法的实现思路涵盖坐标旋转、扫描线求交、面积计算等核心环节。二、算法总体流程输入凸多边形顶点坐标、飞行间隔(space)、旋转角度(rotate) │ ┌─────────▼──────────┐ │ 1. 计算多边形边界框 │ └─────────┬──────────┘ │ ┌───────────▼────────────┐ │ 2. 将多边形旋转 -rotate │ │ 使扫描线平行于纬线 │ └───────────┬────────────┘ │ ┌───────────▼────────────┐ │ 3. 计算旋转后的边界框 │ └───────────┬────────────┘ │ ┌───────────▼────────────┐ │ 4. 按间隔生成平行纬线 │ └───────────┬────────────┘ │ ┌───────────▼────────────┐ │ 5. 每条纬线与多边形求交 │ │ 奇偶行交替方向(锯齿形) │ └───────────┬────────────┘ │ ┌───────────▼────────────┐ │ 6. 将航线旋转回原始方向 │ └───────────┬────────────┘ │ ┌───────────▼────────────┐ │ 7. 计算面积等统计信息 │ └───────────┴────────────┘ │ 输出航线航点列表、多边形面积、航线覆盖面积先旋转再扫描原因因为扫描线逻辑固定为水平方向平行纬线如果用户希望航线方向是任意角度就先把多边形反向旋转在旋转后的坐标系中做水平扫描最后再旋转回来。这样只需要实现水平扫描线一种逻辑。三、核心算法详解3.1 坐标旋转 — 等距柱状投影 2D仿射变换经纬度是球面坐标不能直接做平面旋转。算法采用等距柱状投影Equirectangular Projection将经纬度近似转为平面坐标再进行旋转。等距柱状投影的关键经度方向的实际距离与纬度有关纬度越高同样1度经度对应的实际距离越短。因此需要乘以cos(纬度)进行校正。// 等距柱状投影经度方向乘以 cos(纬度)doublecosLatMath.cos(Math.toRadians(center.getLat()));// 经纬度 - 平面坐标doublepxpoint.getLng()*cosLat;doublepypoint.getLat();// 2D旋转变换doubleradMath.toRadians(deg);doublenewX(px-cx)*cos(rad)-(py-cy)*sin(rad)cx;doublenewY(px-cx)*sin(rad)(py-cy)*cos(rad)cy;// 平面坐标 - 经纬度doublenewLngnewX/cosLat;doublenewLatnewY;原理标准的2D旋转公式绕点(cx, cy)旋转角度θ3.2 扫描线生成 — 按间隔划分平行纬线根据旋转后多边形的南北边界和飞行间隔计算需要多少条扫描线// 南北两端距离米doubledistancehaversineDistance(nw,sw);// 扫描线数量除以2是因为锯齿形来回算两条航线宽度intsteps(int)(distance/space/2);// 每条扫描线之间的纬度差doublelatStep(nw.getLat()-sw.getLat())/steps;3.3 扫描线与多边形求交 — 核心扫描逻辑对每条水平扫描线遍历多边形的每条边求交点/** * 计算纬线 y 与线段 (p1, p2) 的交点 * p1, p2 格式: [lng, lat] * 返回交点 [lng, lat]无交点返回 null */privatedouble[]createInlinePoint(double[]p1,double[]p2,doubley){doublesp1[1]-p2[1];if(s0)returnnull;// 水平边无交点// 线性插值求交点的经度doublex(y-p1[1])*(p1[0]-p2[0])/sp1[0];// 检查交点是否在线段范围内if(xp1[0]xp2[0])returnnull;if(xp1[0]xp2[0])returnnull;returnnewdouble[]{x,y};}几何原理已知线段两端点(x1, y1)和(x2, y2)水平线y Y由相似三角形得3.4 锯齿形路径生成对于凸多边形每条扫描线恰好得到两个交点。将这两个交点按奇偶行交替排列形成锯齿形路径偶数行第0, 2, 4...行从左到右 → 奇数行第1, 3, 5...行从右到左 ←for(inti0;ilatLine.len;i){// ... 求出当前扫描线与多边形的两个交点 line[0], line[1] ...if(i%2!0){// 奇数行先右后左polyline.add(newLatLng(y,Math.max(lng1,lng2)));polyline.add(newLatLng(y,Math.min(lng1,lng2)));}else{// 偶数行先左后右polyline.add(newLatLng(y,Math.min(lng1,lng2)));polyline.add(newLatLng(y,Math.max(lng1,lng2)));}}生成的航线示意┌──────────────────────┐ │ ·──────────────→· │ │ ·←──────────────· │ │ ·──────────→· │ │ ·←────────· │ └──────────────────────┘3.5 Haversine公式 — 球面距离计算计算地球上两点间的距离使用经典的 Haversine 公式privatedoublehaversineDistance(LatLngp1,LatLngp2){doublelat1Math.toRadians(p1.getLat());doublelat2Math.toRadians(p2.getLat());doubledLatMath.toRadians(p2.getLat()-p1.getLat());doubledLngMath.toRadians(p2.getLng()-p1.getLng());doubleasin(dLat/2)*sin(dLat/2)cos(lat1)*cos(lat2)*sin(dLng/2)*sin(dLng/2);doublec2*atan2(sqrt(a),sqrt(1-a));returnEARTH_RADIUS*c;// EARTH_RADIUS 6371000 米}公式推导3.6 面积计算 — Shoelace公式多边形面积采用Shoelace鞋带公式先将经纬度转换为米制平面坐标privatedoublegetPolygonArea(ListLatLngpolygon){doubles0;for(inti0;ipolygon.size();i){LatLngcurrpolygon.get(i);LatLngnextpolygon.get((i1)%polygon.size());// 经纬度转米制坐标doublex1curr.getLng()*lng2m(curr);// 1度经度 多少米doubley1curr.getLat()*lat2m(curr);// 1度纬度 多少米doublex2next.getLng()*lng2m(next);doubley2next.getLat()*lat2m(next);sx1*y2-y1*x2;// 叉积累加}returnMath.abs(s)/2;}Shoelace公式四、前端凸多边形检测后端算法仅适用于凸多边形因此前端在用户绘制时实时检测凸性使用叉积符号一致性判断functionisConvex(pts){varnpts.length;if(n3)returntrue;varsign0;for(vari0;in;i){varapts[i],bpts[(i1)%n],cpts[(i2)%n];// 相邻三点的叉积varcross(b.lng-a.lng)*(c.lat-b.lat)-(b.lat-a.lat)*(c.lng-b.lng);if(cross!0){if(sign0){signcross0?1:-1;}elseif((cross0?1:-1)!sign){returnfalse;// 叉积符号不一致非凸多边形}}}returntrue;}原理沿多边形顶点依次取相邻三个点计算向量叉积。如果所有叉积符号一致全正或全负说明多边形始终朝同一方向转弯即为凸多边形一旦出现符号不同说明存在凹陷。五、算法复杂度分析步骤时间复杂度说明计算边界框O(n)遍历所有顶点坐标旋转O(n)逐点变换扫描线求交O(s * n)s条扫描线每条遍历n条边面积计算O(n)Shoelface公式遍历顶点其中 n 为多边形顶点数s 为扫描线数量 区域高度 / 飞行间隔。实际场景中 n 通常 20s 通常 1000计算量很小可以实时响应。六、总结本算法的核心思想是“旋转-扫描-逆旋转”通过坐标旋转将任意角度的扫描问题统一为水平扫描利用凸多边形的性质每条扫描线恰好两个交点简洁地生成锯齿形路径逆旋转还原到真实坐标系这种方法简洁高效适用于无人机需要区域全覆盖飞行的场景。