道格拉斯压缩算法

  1. import java.util.List;
  2. public interface Track {
  4.     /**
  5.      * 轨迹压缩
  6.      * @param coordinate        原始轨迹 Array<{latitude,longitude,UTC}>
  7.      * @return douglasResult    压缩后的轨迹
  8.      */
  9.      List<double[]> compress(List<double[]> coordinate);
  10. }
  13. import lombok.Data;
  14. import lombok.Setter;
  15. import java.util.ArrayList;
  16. import java.util.Arrays;
  17. import java.util.Comparator;
  18. import java.util.List;
  19. public class Douglas implements Track{
  21.     private int dMax;
  22.     private int dMaxLimit;
  24.     /**
  25.      * @param dMax              允许最大距离误差
  26.      * @param dMaxLimit         允许最大距离误差上限，超过该上限，认为异常点
  27.      */
  28.     public Douglas(int dMax,int dMaxLimit){
  29.         this.dMax = dMax;
  30.         this.dMaxLimit = dMaxLimit;
  31.     }
  33.     /**
  34.      * @param coordinate        原始轨迹 Array<{latitude,longitude}>
  35.      * @return douglasResult    压缩后的轨迹
  36.      */
  37.     @Override
  38.     public List<double[]> compress(List<double[]> coordinate) {
  39.         //抽稀点数量需要大于2
  40.         if (coordinate == null || coordinate.size() <= 2) {
  41.             return null;
  42.         }
  44.         List<double[]> coordinate2 = new ArrayList<>();
  45.         for (int i = 0; i < coordinate.size(); i++) {
  46.             double[] point = Arrays.copyOf(coordinate.get(i),4) ;
  47.             point[3] = i;
  48.             coordinate2.add(point);
  49.         }
  50.         List<double[]> result = new ArrayList<>();
  51.         compressLine(coordinate2, result, 0, coordinate2.size() - 1, dMax,dMaxLimit);
  52.         result.add(coordinate2.get(0));
  53.         result.add(coordinate2.get(coordinate.size() - 1));
  54.         result.sort(new Comparator<double[]>() {
  55.             @Override
  56.             public int compare(double[] u1, double[] u2) {
  57.                 if (u1[3] > u2[3]) {
  58.                     return 1;
  59.                 } else if (u1[3] < u2[3]) {
  60.                     return -1;
  61.                 }
  62.                 // 相等
  63.                 return 0;
  64.             }
  65.         });
  66.         return result;
  67.     }
  69.     /**
  70.      * 计算点pX到点pA和pB所确定的直线的距离
  71.      */
  72.     private  double distToSegment(double[] start, double[] end, double[] center) {
  73.         double a = Math.abs(calculationDistance(start, end));
  74.         double b = Math.abs(calculationDistance(start, center));
  75.         double c = Math.abs(calculationDistance(end, center));
  76.         double p = (a + b + c) / 2.0;
  77.         double s = Math.sqrt(Math.abs(p * (p - a) * (p - b) * (p - c)));
  78.         return s * 2.0 / a;
  79.     }
  81.     /**
  82.      * 递归方式压缩轨迹
  83.      */
  84.     private void compressLine(List<double[]> coordinate, List<double[]> result, int start, int end, int dMax, int dMaxLimit) {
  85.         if (start < end) {
  86.             double maxDist = 0;
  87.             int currentIndex = 0;
  88.             double[] startPoint = coordinate.get(start);
  89.             double[] endPoint = coordinate.get(end);
  90.             for (int i = start + 1; i < end; i++) {
  91.                 double currentDist = distToSegment(startPoint, endPoint, coordinate.get(i));
  92.                 if (currentDist > maxDist) {
  93.                     maxDist = currentDist;
  94.                     currentIndex = i;
  95.                 }
  96.             }
  97.             if (maxDist >= dMax && maxDist <= dMaxLimit) {
  98.                 //将当前点加入到过滤数组中
  99.                 result.add(coordinate.get(currentIndex));
  100.                 //将原来的线段以当前点为中心拆成两段，分别进行递归处理
  101.                 compressLine(coordinate, result, start, currentIndex, dMax,dMaxLimit);
  102.                 compressLine(coordinate, result, currentIndex, end, dMax,dMaxLimit);
  103.             }
  104.         }
  105.     }
  107.     /**
  108.      * 计算两点距离
  109.      */
  110.     private double calculationDistance(double[] point1, double[] point2) {
  111.         double lat1 = point1[0];
  112.         double lat2 = point2[0];
  113.         double lng1 = point1[1];
  114.         double lng2 = point2[1];
  115.         double radLat1 = lat1 * Math.PI / 180.0;
  116.         double radLat2 = lat2 * Math.PI / 180.0;
  117.         double a = radLat1 - radLat2;
  118.         double b = (lng1 * Math.PI / 180.0) - (lng2 * Math.PI / 180.0);
  119.         double s = 2 * Math.asin(Math.sqrt(Math.pow(Math.sin(a / 2), 2)
  120.                 + Math.cos(radLat1) * Math.cos(radLat2) * Math.pow(Math.sin(b / 2), 2)));
  121.         return s * 6370996.81;
  122.     }
  123. }