仿大疆司空2面状航线生成——凸多边形区域航线生成算法详解
<h1 id="仿大疆司空2面状航线生成凸多边形区域航线生成算法详解">仿大疆司空2面状航线生成——凸多边形区域航线生成算法详解</h1><h2 id="一前言">一、前言</h2>
<p>去年，在针对大疆上云API进行二次开发的过程中，有一个需求是实现大疆司空2中的面状航线功能。在经过上网搜索后，在github上找到了一个开源项目cpRPA（植保无人机凸多边形地块工作路线规划），可以实现面状航线的生成。</p>
<p>参考项目github地址：https://github.com/Char-Ten/cpRPA</p>
<p>经过对其中算法的研究，感觉其实现方式非常值得学习，遂用Java重新实现了相关的逻辑，将其中的关键算法思路整理到本篇博客中。</p>
<p><img src="https://img2024.cnblogs.com/blog/3476680/202604/3476680-20260415160915621-1131460356.png"></p>
<p><strong>本篇博客仅作为学习整理使用，由AI总结生成，实际代码请查看原项目。</strong></p>
<p>下面将详细整理这一算法的实现思路，涵盖坐标旋转、扫描线求交、面积计算等核心环节。</p>
<h2 id="二算法总体流程">二、算法总体流程</h2>
<pre><code>输入：凸多边形顶点坐标、飞行间隔(space)、旋转角度(rotate)
│
┌─────────▼──────────┐
│ 1. 计算多边形边界框│
└─────────┬──────────┘
│
┌───────────▼────────────┐
│ 2. 将多边形旋转 -rotate │
│ （使扫描线平行于纬线）│
└───────────┬────────────┘
│
┌───────────▼────────────┐
│ 3. 计算旋转后的边界框 │
└───────────┬────────────┘
│
┌───────────▼────────────┐
│ 4. 按间隔生成平行纬线 │
└───────────┬────────────┘
│
┌───────────▼────────────┐
│ 5. 每条纬线与多边形求交│
│ 奇偶行交替方向(锯齿形) │
└───────────┬────────────┘
│
┌───────────▼────────────┐
│ 6. 将航线旋转回原始方向 │
└───────────┬────────────┘
│
┌───────────▼────────────┐
│ 7. 计算面积等统计信息 │
└───────────┴────────────┘
│
输出：航线航点列表、多边形面积、航线覆盖面积
</code></pre>
<p><strong>先旋转再扫描原因：</strong> 因为扫描线逻辑固定为水平方向（平行纬线），如果用户希望航线方向是任意角度，就先把多边形反向旋转，在旋转后的坐标系中做水平扫描，最后再旋转回来。这样只需要实现水平扫描线一种逻辑。</p>
<h2 id="三核心算法详解">三、核心算法详解</h2>
<h3 id="31-坐标旋转--等距柱状投影--2d仿射变换">3.1 坐标旋转 — 等距柱状投影 + 2D仿射变换</h3>
<p>经纬度是球面坐标，不能直接做平面旋转。算法采用<strong>等距柱状投影</strong>（Equirectangular Projection）将经纬度近似转为平面坐标，再进行旋转。</p>
<p><strong>等距柱状投影的关键：</strong> 经度方向的实际距离与纬度有关，纬度越高，同样1度经度对应的实际距离越短。因此需要乘以 <code>cos(纬度)</code> 进行校正。</p>
<pre><code class="language-java">// 等距柱状投影：经度方向乘以 cos(纬度)
double cosLat = Math.cos(Math.toRadians(center.getLat()));
// 经纬度 -> 平面坐标
double px = point.getLng() * cosLat;
double py = point.getLat();
// 2D旋转变换
double rad = Math.toRadians(deg);
double newX = (px - cx) * cos(rad) - (py - cy) * sin(rad) + cx;
double newY = (px - cx) * sin(rad) + (py - cy) * cos(rad) + cy;
// 平面坐标 -> 经纬度
double newLng = newX / cosLat;
double newLat = newY;
</code></pre>
<p><strong>原理：</strong> 标准的2D旋转公式，绕点 <code>(cx, cy)</code> 旋转角度 <code>θ</code>：</p>
<p><img src="https://img2024.cnblogs.com/blog/3476680/202604/3476680-20260415161348589-2039943434.png"></p>
<h3 id="32-扫描线生成--按间隔划分平行纬线">3.2 扫描线生成 — 按间隔划分平行纬线</h3>
<p>根据旋转后多边形的南北边界和飞行间隔，计算需要多少条扫描线：</p>
<pre><code class="language-java">// 南北两端距离（米）
double distance = haversineDistance(nw, sw);
// 扫描线数量（除以2是因为锯齿形来回算两条航线宽度）
int steps = (int) (distance / space / 2);
// 每条扫描线之间的纬度差
double latStep = (nw.getLat() - sw.getLat()) / steps;
</code></pre>
<h3 id="33-扫描线与多边形求交--核心扫描逻辑">3.3 扫描线与多边形求交 — 核心扫描逻辑</h3>
<p>对每条水平扫描线，遍历多边形的每条边，求交点：</p>
<pre><code class="language-java">/**
* 计算纬线 y 与线段 (p1, p2) 的交点
* p1, p2 格式:
* 返回交点 ，无交点返回 null
*/
private double[] createInlinePoint(double[] p1, double[] p2, double y) {
double s = p1 - p2;
if (s == 0) return null;// 水平边，无交点
// 线性插值求交点的经度
double x = (y - p1) * (p1 - p2) / s + p1;
// 检查交点是否在线段范围内
if (x > p1 && x > p2) return null;
if (x < p1 && x < p2) return null;
return new double[]{x, y};
}
</code></pre>
<p><strong>几何原理：</strong> 已知线段两端点 <code>(x1, y1)</code> 和 <code>(x2, y2)</code>，水平线 <code>y = Y</code>，由相似三角形得：</p>
<p><img src="https://img2024.cnblogs.com/blog/3476680/202604/3476680-20260415161520515-1256443386.png"></p>
<h3 id="34-锯齿形路径生成">3.4 锯齿形路径生成</h3>
<p>对于凸多边形，每条扫描线恰好得到<strong>两个交点</strong>。将这两个交点按奇偶行交替排列，形成锯齿形路径：</p>
<pre><code>偶数行（第0, 2, 4...行）：从左到右→
奇数行（第1, 3, 5...行）：从右到左←
</code></pre>
<pre><code class="language-java">for (int i = 0; i < latLine.len; i++) {
// ... 求出当前扫描线与多边形的两个交点 line, line ...
if (i % 2 != 0) {
// 奇数行：先右后左
polyline.add(new LatLng(y, Math.max(lng1, lng2)));
polyline.add(new LatLng(y, Math.min(lng1, lng2)));
} else {
// 偶数行：先左后右
polyline.add(new LatLng(y, Math.min(lng1, lng2)));
polyline.add(new LatLng(y, Math.max(lng1, lng2)));
}
}
</code></pre>
<p>生成的航线示意：</p>
<pre><code> ┌──────────────────────┐
│·──────────────→· │
│·←──────────────· │
│ ·──────────→· │
│ ·←────────· │
└──────────────────────┘
</code></pre>
<h3 id="35-haversine公式--球面距离计算">3.5 Haversine公式 — 球面距离计算</h3>
<p>计算地球上两点间的距离，使用经典的 Haversine 公式：</p>
<pre><code class="language-java">private double haversineDistance(LatLng p1, LatLng p2) {
double lat1 = Math.toRadians(p1.getLat());
double lat2 = Math.toRadians(p2.getLat());
double dLat = Math.toRadians(p2.getLat() - p1.getLat());
double dLng = Math.toRadians(p2.getLng() - p1.getLng());
double a = sin(dLat/2) * sin(dLat/2)
+ cos(lat1) * cos(lat2) * sin(dLng/2) * sin(dLng/2);
double c = 2 * atan2(sqrt(a), sqrt(1-a));
return EARTH_RADIUS * c;// EARTH_RADIUS = 6371000 米
}
</code></pre>
<p><strong>公式推导：</strong></p>
<p><img src="https://img2024.cnblogs.com/blog/3476680/202604/3476680-20260415161553081-222301151.png"></p>
<h3 id="36-面积计算--shoelace公式">3.6 面积计算 — Shoelace公式</h3>
<p>多边形面积采用 <strong>Shoelace（鞋带）公式</strong>，先将经纬度转换为米制平面坐标：</p>
<pre><code class="language-java">private double getPolygonArea(List<LatLng> polygon) {
double s = 0;
for (int i = 0; i < polygon.size(); i++) {
LatLng curr = polygon.get(i);
LatLng next = polygon.get((i + 1) % polygon.size());
// 经纬度转米制坐标
double x1 = curr.getLng() * lng2m(curr);// 1度经度 = 多少米
double y1 = curr.getLat() * lat2m(curr); // 1度纬度 = 多少米
double x2 = next.getLng() * lng2m(next);
double y2 = next.getLat() * lat2m(next);
s += x1 * y2 - y1 * x2;// 叉积累加
}
return Math.abs(s) / 2;
}
</code></pre>
<p><strong>Shoelace公式：</strong></p>
<p><img src="https://img2024.cnblogs.com/blog/3476680/202604/3476680-20260415161610383-233284539.png"></p>
<h2 id="四前端凸多边形检测">四、前端凸多边形检测</h2>
<p>后端算法仅适用于凸多边形，因此前端在用户绘制时实时检测凸性，使用<strong>叉积符号一致性</strong>判断：</p>
<pre><code class="language-javascript">function isConvex(pts) {
var n = pts.length;
if (n < 3) return true;
var sign = 0;
for (var i = 0; i < n; i++) {
var a = pts, b = pts[(i + 1) % n], c = pts[(i + 2) % n];
// 相邻三点的叉积
var cross = (b.lng - a.lng) * (c.lat - b.lat)
- (b.lat - a.lat) * (c.lng - b.lng);
if (cross !== 0) {
if (sign === 0) {
sign = cross > 0 ? 1 : -1;
} else if ((cross > 0 ? 1 : -1) !== sign) {
return false;// 叉积符号不一致，非凸多边形
}
}
}
return true;
}
</code></pre>
<p><strong>原理：</strong> 沿多边形顶点依次取相邻三个点，计算向量叉积。如果所有叉积符号一致（全正或全负），说明多边形始终朝同一方向转弯，即为凸多边形；一旦出现符号不同，说明存在"凹陷"。</p>
<h2 id="五算法复杂度分析">五、算法复杂度分析</h2>
<table>
<thead>
<tr>
<th>步骤</th>
<th>时间复杂度</th>
<th>说明</th>
</tr>
</thead>
<tbody>
<tr>
<td>计算边界框</td>
<td>O(n)</td>
<td>遍历所有顶点</td>
</tr>
<tr>
<td>坐标旋转</td>
<td>O(n)</td>
<td>逐点变换</td>
</tr>
<tr>
<td>扫描线求交</td>
<td>O(s * n)</td>
<td>s条扫描线，每条遍历n条边</td>
</tr>
<tr>
<td>面积计算</td>
<td>O(n)</td>
<td>Shoelface公式遍历顶点</td>
</tr>
</tbody>
</table>
<p>其中 n 为多边形顶点数，s 为扫描线数量（= 区域高度 / 飞行间隔）。</p>
<p>实际场景中 n 通常 < 20，s 通常 < 1000，计算量很小，可以实时响应。</p>
<h2 id="六总结">六、总结</h2>
<p>本算法的核心思想是 <strong>"旋转-扫描-逆旋转"</strong>：</p>
<ol>
<li>通过坐标旋转，将任意角度的扫描问题统一为水平扫描</li>
<li>利用凸多边形的性质（每条扫描线恰好两个交点），简洁地生成锯齿形路径</li>
<li>逆旋转还原到真实坐标系</li>
</ol>
<p>这种方法简洁高效，适用于无人机需要区域全覆盖飞行的场景。</p><br><br>
来源：https://www.cnblogs.com/foury/p/19872397
頁:
[1]