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

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

一、前言

客岁，在针对大疆上云API举行二次开发的过程中，有一个需求是实现大疆司空2中的面状航线功能。在颠末上网搜刮后，在github上找到了一个开源项目cpRPA（植保无人机凸多边形地块工作蹊径规划），可以实现面状航线的天生。
参考项目github所在：https://github.com/Char-Ten/cpRPA
颠末对此中算法的研究，感觉着实现方式非常值得学习，遂用Java重新实现了干系的逻辑，将此中的关键算法思绪整理到本篇博客中。

本篇博客仅作为学习整理使用，由AI总结天生，现实代码请检察原项目。
下面将详细整理这一算法的实现思绪，涵盖坐标旋转、扫描线求交、面积盘算等核心环节。
二、算法总体流程

1. 输入：凸多边形顶点坐标、飞行间隔(space)、旋转角度(rotate)
2.                           │
3.                 ┌─────────▼──────────┐
4.                 │ 1. 计算多边形边界框  │
5.                 └─────────┬──────────┘
6.                           │
7.               ┌───────────▼────────────┐
8.               │ 2. 将多边形旋转 -rotate │
9.               │   （使扫描线平行于纬线）  │
10.               └───────────┬────────────┘
11.                           │
12.               ┌───────────▼────────────┐
13.               │ 3. 计算旋转后的边界框    │
14.               └───────────┬────────────┘
15.                           │
16.               ┌───────────▼────────────┐
17.               │ 4. 按间隔生成平行纬线    │
18.               └───────────┬────────────┘
19.                           │
20.               ┌───────────▼────────────┐
21.               │ 5. 每条纬线与多边形求交  │
22.               │   奇偶行交替方向(锯齿形) │
23.               └───────────┬────────────┘
24.                           │
25.               ┌───────────▼────────────┐
26.               │ 6. 将航线旋转回原始方向   │
27.               └───────────┬────────────┘
28.                           │
29.               ┌───────────▼────────────┐
30.               │ 7. 计算面积等统计信息     │
31.               └───────────┴────────────┘
32.                           │
33. 输出：航线航点列表、多边形面积、航线覆盖面积

复制代码

先旋转再扫描缘故起因： 由于扫描线逻辑固定为水平方向（平行纬线），如果用户盼望航线方向是恣意角度，就先把多边形反向旋转，在旋转后的坐标系中做水平扫描，末了再旋转返来。如许只须要实现水平扫描线一种逻辑。
三、核默算法详解

3.1 坐标旋转 — 等距柱状投影 + 2D仿射变更

经纬度是球面坐标，不能直接做平面旋转。算法采取等距柱状投影（Equirectangular Projection）将经纬度近似转为平面坐标，再举行旋转。
等距柱状投影的关键： 经度方向的现实间隔与纬度有关，纬度越高，同样1度经度对应的现实间隔越短。因此须要乘以 cos(纬度) 举行校正。

1. // 等距柱状投影：经度方向乘以 cos(纬度)
2. double cosLat = Math.cos(Math.toRadians(center.getLat()));
4. // 经纬度 -> 平面坐标
5. double px = point.getLng() * cosLat;
6. double py = point.getLat();
8. // 2D旋转变换
9. double rad = Math.toRadians(deg);
10. double newX = (px - cx) * cos(rad) - (py - cy) * sin(rad) + cx;
11. double newY = (px - cx) * sin(rad) + (py - cy) * cos(rad) + cy;
13. // 平面坐标 -> 经纬度
14. double newLng = newX / cosLat;
15. double newLat = newY;

复制代码

原理： 标准的2D旋转公式，绕点 (cx, cy) 旋转角度 θ：

3.2 扫描线天生 — 按隔断分别平行纬线

根据旋转后多边形的南北界限和飞行隔断，盘算须要多少条扫描线：

1. // 南北两端距离（米）
2. double distance = haversineDistance(nw, sw);
4. // 扫描线数量（除以2是因为锯齿形来回算两条航线宽度）
5. int steps = (int) (distance / space / 2);
7. // 每条扫描线之间的纬度差
8. double latStep = (nw.getLat() - sw.getLat()) / steps;

复制代码

3.3 扫描线与多边形求交 — 核心扫描逻辑

对每条水平扫描线，遍历多边形的每条边，求交点：

1. /**
2. * 计算纬线 y 与线段 (p1, p2) 的交点
3. * p1, p2 格式: [lng, lat]
4. * 返回交点 [lng, lat]，无交点返回 null
5. */
6. private double[] createInlinePoint(double[] p1, double[] p2, double y) {
7.     double s = p1[1] - p2[1];
8.     if (s == 0) return null;  // 水平边，无交点
10.     // 线性插值求交点的经度
11.     double x = (y - p1[1]) * (p1[0] - p2[0]) / s + p1[0];
13.     // 检查交点是否在线段范围内
14.     if (x > p1[0] && x > p2[0]) return null;
15.     if (x < p1[0] && x < p2[0]) return null;
17.     return new double[]{x, y};
18. }

复制代码

多少原理： 已知线段两头点 (x1, y1) 和 (x2, y2)，水平线 y = Y，由相似三角形得：

3.4 锯齿形路径天生

对于凸多边形，每条扫描线恰恰得到两个交点。将这两个交点按奇偶行瓜代分列，形成锯齿形路径：

1. 偶数行（第0, 2, 4...行）：从左到右  →
2. 奇数行（第1, 3, 5...行）：从右到左  ←

复制代码

1. for (int i = 0; i < latLine.len; i++) {
2.     // ... 求出当前扫描线与多边形的两个交点 line[0], line[1] ...
4.     if (i % 2 != 0) {
5.         // 奇数行：先右后左
6.         polyline.add(new LatLng(y, Math.max(lng1, lng2)));
7.         polyline.add(new LatLng(y, Math.min(lng1, lng2)));
8.     } else {
9.         // 偶数行：先左后右
10.         polyline.add(new LatLng(y, Math.min(lng1, lng2)));
11.         polyline.add(new LatLng(y, Math.max(lng1, lng2)));
12.     }
13. }

复制代码

天生的航线表示：

1.     ┌──────────────────────┐
2.     │  ·──────────────→·   │
3.     │  ·←──────────────·   │
4.     │   ·──────────→·      │
5.     │    ·←────────·       │
6.     └──────────────────────┘

复制代码

3.5 Haversine公式 — 球面间隔盘算

盘算地球上两点间的间隔，使用经典的 Haversine 公式：

1. private double haversineDistance(LatLng p1, LatLng p2) {
2.     double lat1 = Math.toRadians(p1.getLat());
3.     double lat2 = Math.toRadians(p2.getLat());
4.     double dLat = Math.toRadians(p2.getLat() - p1.getLat());
5.     double dLng = Math.toRadians(p2.getLng() - p1.getLng());
7.     double a = sin(dLat/2) * sin(dLat/2)
8.              + cos(lat1) * cos(lat2) * sin(dLng/2) * sin(dLng/2);
9.     double c = 2 * atan2(sqrt(a), sqrt(1-a));
11.     return EARTH_RADIUS * c;  // EARTH_RADIUS = 6371000 米
12. }

复制代码

公式推导：

3.6 面积盘算 — Shoelace公式

多边形面积采取 Shoelace（鞋带）公式，先将经纬度转换为米制平面坐标：

1. private double getPolygonArea(List<LatLng> polygon) {
2.     double s = 0;
3.     for (int i = 0; i < polygon.size(); i++) {
4.         LatLng curr = polygon.get(i);
5.         LatLng next = polygon.get((i + 1) % polygon.size());
7.         // 经纬度转米制坐标
8.         double x1 = curr.getLng() * lng2m(curr);  // 1度经度 = 多少米
9.         double y1 = curr.getLat() * lat2m(curr);   // 1度纬度 = 多少米
10.         double x2 = next.getLng() * lng2m(next);
11.         double y2 = next.getLat() * lat2m(next);
13.         s += x1 * y2 - y1 * x2;  // 叉积累加
14.     }
15.     return Math.abs(s) / 2;
16. }

复制代码

Shoelace公式：

四、前端凸多边形检测

后端算法仅实用于凸多边形，因此前端在用户绘制时实时检测凸性，使用叉积符号同等性判定：

1. function isConvex(pts) {
2.     var n = pts.length;
3.     if (n < 3) return true;
4.     var sign = 0;
5.     for (var i = 0; i < n; i++) {
6.         var a = pts[i], b = pts[(i + 1) % n], c = pts[(i + 2) % n];
7.         // 相邻三点的叉积
8.         var cross = (b.lng - a.lng) * (c.lat - b.lat)
9.                   - (b.lat - a.lat) * (c.lng - b.lng);
10.         if (cross !== 0) {
11.             if (sign === 0) {
12.                 sign = cross > 0 ? 1 : -1;
13.             } else if ((cross > 0 ? 1 : -1) !== sign) {
14.                 return false;  // 叉积符号不一致，非凸多边形
15.             }
16.         }
17.     }
18.     return true;
19. }

复制代码

原理： 沿多边形极点依次取相邻三个点，盘算向量叉积。如果全部叉积符号同等（全正或全负），分析多边形始终朝同一方向转弯，即为凸多边形；一旦出现符号差异，分析存在"凹陷"。
五、算法复杂度分析

步调时间复杂度分析盘算界限框O(n)遍历全部极点坐标旋转O(n)逐点变更扫描线求交O(s * n)s条扫描线，每条遍历n条边面积盘算O(n)Shoelface公式遍历极点此中 n 为多边形极点数，s 为扫描线数目（= 地区高度 / 飞行隔断）。
现实场景中 n 通常 < 20，s 通常 < 1000，盘算量很小，可以实时相应。
六、总结

本算法的核心头脑是 "旋转-扫描-逆旋转"：

• 通过坐标旋转，将恣意角度的扫描标题同一为水平扫描
  
• 使用凸多边形的性子（每条扫描线恰恰两个交点），轻巧地天生锯齿形路径
  
• 逆旋转还原到真实坐标系
  

这种方法轻巧高效，实用于无人机须要地区全覆盖飞行的场景。

免责声明：如果侵犯了您的权益，请联系站长及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金.