道格拉斯-普克算法

我们都知道，线是由许多的点组成的，而道格拉斯-普克算法的核心思想就是，以尽可能少的点去近似拟合一条曲线。

思路

对每一条曲线的首末点虚连一条直线，求所有点与直线的距离，并找出最大距离值dmax。用dmax与限差D相比：若dmax <D，这条曲线上的中间点全部舍去；若dmax ≥ D，保留dmax 对应的坐标点，并以该点为界，把曲线分为两部分，对这两部分重复使用该方法。

算法实现

基于道格拉斯-普克算法理念对路径进行抽稀，并保留点位的原始顺序

• GpsPoint.java

public class GpsPoint {

    /**
     * 纬度
     */
    private Double lat;

    /**
     * 经度
     */
    private Double lng;
}

• DPUtil.java

public class DPUtil {

    /**
     * 地球半径
     */
    public static final double EARTH_RADIUS = 6378137;

    /**
     * 默认的点到轨迹线最大距离误差阈值（单位：米）
     */
    private static final double DEFAULT_MAX_REFERENCE = 300;

    /**
     * DP算法入口
     * 传入压缩前的轨迹点集合
     * 输出压缩后的结果轨迹点集合
     * @param originPoints 压缩前的轨迹点集合
     * @return 压缩后的轨迹点
     */
    public static List<GpsPoint> dpCompress(List<GpsPoint> originPoints) {
        return dpCompress(originPoints, DEFAULT_MAX_REFERENCE);
    }

    /**
     * DP算法入口
     * 传入压缩前的轨迹点集合
     * 输出压缩后的结果轨迹点集合
     * @param originPoints 压缩前的轨迹点集合
     * @param dMax 点到轨迹线最大距离误差阈值
     * @return 压缩后的轨迹点
     */
    public static List<GpsPoint> dpCompress(List<GpsPoint> originPoints, Double dMax) {
        List<GpsPoint> resultPoints = new ArrayList<>();
        
        int start = 0;
        int end = originPoints.size() - 1;
        
        //获取第一个原始经纬度点坐标并添加到过滤后的数组中
        resultPoints.add(originPoints.get(start));

        //最大距离误差阈值默认值
        if (dMax == null) {
            dMax = DEFAULT_MAX_REFERENCE;
        }
       
        compression(originPoints, resultPoints, start, end, dMax);

        //获取最后一个原始经纬度点坐标并添加到过滤后的数组中
        resultPoints.add(originPoints.get(end));

        return resultPoints;
    }

    /**
     * 函数功能：根据最大距离限制，采用DP方法递归的对原始轨迹进行采样，得到压缩后的轨迹
     * @param originPoints：原始经纬度坐标点数组
     * @param resultPoints：保持过滤后的点坐标数组
     * @param start：起始下标
     * @param end：终点下标
     * @param dMax：预先指定好的最大距离误差
     */
    public static void compression(List<GpsPoint> originPoints, List<GpsPoint> resultPoints, int start, int end,
        double dMax) {
        //递归结束的条件
        if (start >= end) {
            return;
        }

        // 记录最大距离, 默认为0
        double maxDistance = 0;
        // 记录最大距离的下标, 默认为初始下标
        int maxPointLocation = start;

        for (int i = start + 1; i < end; i++) {
            // 计算当前点到对应线段的距离
            double currentDistance = distanceToSegment(originPoints.get(start), originPoints.get(end),
                                                       originPoints.get(i));

            // 若大于记录的最大距离，滚动更新记录值
            if (currentDistance > maxDistance) {
                // 更新最大距离
                maxDistance = currentDistance;
                // 更新最大距离的下标
                maxPointLocation = i;
            }
        }

        // 若当前最大距离大于等于最大距离误差，则根据最大距离点划分中心，继续进递归进行压缩
        // 若当前距离小于最大距离误差，则将中间所有的点舍去，即不做任何处理
        if (maxDistance >= dMax) {
            // 将原来的线段以当前点为中心拆成两段，按顺序将数据加入结果集，保证点的有序性
            // 将第一段加入结果集
            compression(originPoints, resultPoints, start, maxPointLocation, dMax);

            // 将当前点加入结果集
            resultPoints.add(originPoints.get(maxPointLocation));

            // 将第二段加入结果集
            compression(originPoints, resultPoints, maxPointLocation, end, dMax);
        }
    }

    /**
     * 函数功能：使用三角形面积（使用海伦公式求得）相等方法计算点pX到点pA和pB所确定的直线的距离
     * @param pA：起始点
     * @param pB：结束点
     * @param pX：第三个点
     * @return distance：点pX到pA和pB所在直线的距离
     */
    public static double distanceToSegment(GpsPoint pA, GpsPoint pB, GpsPoint pX) {
        double a = Math.abs(geoDistance(pA, pB));
        double b = Math.abs(geoDistance(pA, pX));
        double c = Math.abs(geoDistance(pB, pX));
        double p = (a + b + c) / 2.0;
        double s = Math.sqrt(Math.abs(p * (p - a) * (p - b) * (p - c)));
        return s * 2.0 / a;
    }

    /**
     * 函数功能：根据数学公式求两个经纬度点之间的距离
     * @param pA：起始点
     * @param pB：结束点
     * @return distance：距离
     */
    public static double geoDistance(GpsPoint pA, GpsPoint pB) {
        if (pA == null || pB == null) {
            return 0;
        }
        double radLat1 = radians(pA.getLat());
        double radLat2 = radians(pB.getLat());
        double deltaLng = radians(pB.getLng() - pA.getLng());
        double top1 = Math.cos(radLat2) * Math.sin(deltaLng);
        double top2 = Math.cos(radLat1) * Math.sin(radLat2) - Math.sin(radLat1) * Math.cos(radLat2) * Math.cos(
            deltaLng);
        double top = Math.sqrt(top1 * top1 + top2 * top2);
        double bottom = Math.sin(radLat1) * Math.sin(radLat2) + Math.cos(radLat1) * Math.cos(radLat2) * Math.cos(
            deltaLng);
        double deltaSigma = Math.atan2(top, bottom);
        return deltaSigma * EARTH_RADIUS;
    }

    /**
     * 函数功能：角度转弧度
     * @param d：角度
     * @return 返回的是弧度
     */
    public static double radians(double d) {
        return d * Math.PI / 180.0;
    }
}