阅读 122

凸多边形航线规划算法优化

本文是对参考文章《无人机航线规划思路剖析,基于凸多边形地块往复式运动》算法实现的一个优化,优化内容点:

  1. 航线间隔的优化
  2. 航线外扩

注:接下来的内容,请务必掌握参考文章内容的知识点。

航线间隔计算的优化

优化前写法:

作者使用了一个非常简单粗暴的写法,即用多边形外接矩形计算出最北方向和最南方向的距离,然后除以航线间隔距离,得出规划航线的数量:

function distance(p1,p2){
  /**leaflet提供的方法*/
  return L.latLng(p1.lat,p1.lng).distanceTo(L.latLng(p2.lat,p2.lng))
}

/** nw到sw的距离*/
var dist = distance(nw,sw);

/** 得出答案*/
var lines = parseInt(dist / 20)
复制代码

然后再用最北方向的纬度减去最南方向的纬度,除以已知的航线数量,即可得到每条航线之间的纬度差,以此从上往下计算出每条航线的纬度:

var N=[];
var stepLat=(nw.lat-sw.lat)/lines;
for(var i=0;i<lines;i++){
  N.push(nw.lat - i * stepLat)
}
复制代码

我们可以举个简单的例子来表明此方法的弊端,假设北纬与南纬之间的间隔距离为 100 米,并且要求航线间隔是 30 米,按照上述代码可计算出 lines = 3,然后再计算出纬度差画出航线,我们所期望的间隔 30 米,在此平均算法后,实际的每条间隔却变成了 33.33 米,如图:

image.png

导致了旁向重叠率一直不准确。

优化后写法

使用方位角算法:已知一点经纬度,方位角,距离,求另一点经纬度。

 public static MapLatLng getBearingLatLng(MapLatLng latLng, int distance, double bearing) {
        double R = 6371.393 * 1000;

        double δ = distance / R;
        double θ = toRadius(bearing);

        double φ1 = toRadius(latLng.getLatitude());
        double λ1 = toRadius(latLng.getLongitude());

        double sinφ2 = Math.sin(φ1) * Math.cos(δ) + Math.cos(φ1) * Math.sin(δ) * Math.cos(θ);
        double φ2 = Math.asin(sinφ2);

        double y = Math.sin(θ) * Math.sin(δ) * Math.cos(φ1);
        double x = Math.cos(δ) - Math.sin(φ1) * sinφ2;
        double λ2 = λ1 + Math.atan2(y, x);

        double lat = toDegree(φ2);
        double lng = toDegree(λ2);

        return new MapLatLng(lat, lng);
    }

  	private static double toRadius(double value) {
        return value * Math.PI / 180;
    }

    private static double toDegree(double value) {
        return value * 180 / Math.PI;
    }
复制代码

具体实现是,以最北纬度为基准点,在航线间隔距离下,计算出 180 度方向(正北为0度)的一个点,该点则是第一条航线上的点,然后再通过该点为基准点,一直反复计算出下一个点,直到下一个航点的位置小于最南纬度为止,仍是上述的例子,计算后的航线效果如图:

image.png

航线外扩

航线外扩功能主要是为了无人机能更好的拍摄地块边界,在合成三维模型中有更好的展现。在参考文章中,作者并未对航线的外扩进行实现,我们在分析竞品时,可以看见 DJI Pilot 是有该功能的实现的:

image.png

具体实现:
仍是利用方位角算法,对航线中的两点进行向左外扩和向右外扩,示意图如下:

image.png


红线是我们外扩的距离,该距离为航线间隔距离即可。我们知道线是由两点构成的,也即意味着,航点集是一个偶数,那么我们可以每次以步长为 2 进行循环遍历航点集,每次取两个点进行经度的比较,如果 点1  的经度大于 点2  的经度,那么 点1  就要向右进行外扩, 点2  就要向左进行外扩,外扩算出来的点需要替换原集合位置的点,以此类推下去,即可实现所有点的外扩,实现效果如下:

a.gif

参考文章

1、方位角的计算

最后

如果有开发者对无人机相关内容感兴趣的话,可以联系作者,微信号:codelang94

关注下面的标签,发现更多相似文章
评论