1.算法说明
道格拉斯-普克算法 Douglas-Peucker Algorithm 简称 D-P 算法，亦称为拉默-道格拉斯-普克算法、迭代适应点算法、分裂与合并算法，是将曲线近似表示为一系列点，并减少点的数量的一种算法。该算法的原始类型分别由乌尔斯·拉默于1972年以及大卫·道格拉斯和托马斯·普克于1973年提出，并在之后的数十年中由其他学者予以完善。
D-P 算法是公认的线状要素化简经典算法。现有的线化简算法中，有相当一部分都是在该算法基础上进行改进产生的。用来对大量冗余的图形数据点进行压缩以提取必要的数据点，它是一个整体算法，具有平移和旋转不变性，可保留较大弯曲形态上的特征点。且在给定曲线与阈值后，抽样结果一定。
保留了较大弯曲形态上的特征点：
经典的 D-P 算法描述如下【红色部分用于辅助理解 可忽略】：
- 连接当前矢量曲线首尾点
a、b，该直线AB为当前矢量曲线的弦； - 计算首尾点
a、b间所有坐标点到该弦AB的距离，并获取最大距离d及其的坐标点c； - 比较最大距离
d与给定的阈值thresholdVal，小于阈值，当前弦AB可作为曲线的近似【首尾间的坐标点将被抽稀】，该段矢量曲线处理完毕。 - 大于阈值，使用最大距离坐标点
c分割当前矢量曲线，分割后的两段矢量曲线分别使用1~3的流程进行处理。 - 全部处理完毕后，依次连接各个分割点形成的折线，即可以作为整个曲线的近似。
示意图如下：
2.源码分享
2.1 公式
点 M ( x 0 , y 0 ) M(x_{0},y_{0})M(x0,y0) 是平面上的一个点，它到直线 A x + B y + C = 0 Ax+By+C=0Ax+By+C=0 的距离 d 为：
d = ∣ A x 0 + B y 0 + C ∣ A 2 + B 2 d= \frac{|Ax_{0}+By_{0}+C|}{ \sqrt{A^{2}+B^{2}}}d=A2+B2∣Ax0+By0+C∣
2.2 源码
一下是优化前的代码，优化后的代码请查看《道格拉斯-普克 Douglas-Peucker 抽稀算法近1000倍的速度提升》两个对象封装类【为了简洁注解未使用DOC规范】：
// 类1 坐标数据封装 @Data @NoArgsConstructor @AllArgsConstructor public class PointData { // 标记是否删除（0保留 1删除） private int isDelete; // 数据点的经度 private double longitudeEx; // 数据点的纬度 private double latitudeEx; } // 类2 点INDEX及到线距离封装 @Data @NoArgsConstructor @AllArgsConstructor @Builder public class DistanceData { // 当前点的 INDEX 值 private int index; // 当前点到直线的距离值 private double distance; }
算法核心代码及测试代码【为了简洁部分注解未使用DOC规范】：
public class Douglas { // 矢量曲线的点数据 private static List<PointData> points = new ArrayList<>(); // 距离阈值（值越大效果越好但丢失细节就越多） private static final double DISTANCE_THRESHOLD = 0.00001; /** * 标记要删除的点 * * @param from 矢量曲线的起始点 * @param to 矢量曲线的终止点 */ private static void markDeletePoints(PointData from, PointData to) { // 计算由起始点和终止点构成直线方程一般式的系数 double fromLat = from.getLatitudeEx(); double fromLng = from.getLongitudeEx(); double toLat = to.getLatitudeEx(); double toLng = to.getLongitudeEx(); // 求解点到直线距离方程的参数 double sqrtPowAddVal = Math.sqrt(Math.pow((fromLat - toLat), 2) + Math.pow((fromLng - toLng), 2)); double parameterA = (fromLat - toLat) / sqrtPowAddVal; double parameterB = (toLng - fromLng) / sqrtPowAddVal; double parameterC = (fromLng * toLat - toLng * fromLat) / sqrtPowAddVal; int fromIndex = points.indexOf(from); int toIndex = points.indexOf(to); if (toIndex == fromIndex + 1) { return; } // 起止点之间的点到起止点连线的距离数据集合 List<DistanceData> distanceDataList = new ArrayList<>(); double powAddRes = Math.pow(parameterA, 2) + Math.pow(parameterB, 2); for (int i = fromIndex + 1; i < toIndex; i++) { double lng = points.get(i).getLongitudeEx(); double lat = points.get(i).getLatitudeEx(); // 点到直线的距离 double distance = Math.abs(parameterA * (lng) + parameterB * (lat) + parameterC) / Math.sqrt(powAddRes); distanceDataList.add(DistanceData.builder().index(i).distance(distance).build()); } // 获取最大距离 double distanceMax = 0; Optional<Double> max = distanceDataList.stream() .map(DistanceData::getDistance).max(Double::compareTo); if (max.isPresent()) { distanceMax = max.get(); } // 分割点 PointData splitPoint; // 最大距离与距离阈值进行比较 if (distanceMax < DISTANCE_THRESHOLD) { // 小于则标记 points(fromIndex,toIndex) 内的坐标（用于删除） for (int i = fromIndex + 1; i < toIndex; i++) { points.get(i).setIsDelete(1); } } else { // 大于极差则进行分割 double finalDistanceMax = distanceMax; // 存在多个最大点的情况 List<DistanceData> distanceMaxIndex = distanceDataList.stream() .filter(distanceData -> distanceData.getDistance() == finalDistanceMax) .collect(Collectors.toList()); int maxIndex = distanceMaxIndex.get(0).getIndex(); splitPoint = points.get(maxIndex); // 分割点左侧进行递归抽稀（标记全部要删除的点） markDeletePoints(from, splitPoint); // 分割点右侧进行递归抽稀（标记全部要删除的点） markDeletePoints(splitPoint, to); } } /** * 进行抽稀：标记要删除的点并筛选 * * @param source 矢量曲线点数据 * @return 抽稀后的点数据 */ public static List<PointData> toDilute(List<PointData> source) { // 抽稀前的点数据 points = source; // 进行标记 if (!CollectionUtils.isEmpty(points)) { markDeletePoints(points.get(0), points.get(points.size() - 1)); } // 筛选掉标记为删除的点 return points.stream().filter(point -> point.getIsDelete() != 1).collect(Collectors.toList()); } public static void main(String[] args) { List<PointData> list = new ArrayList<>(); PointData data; String[] points = new String[]{"117.212448,39.133785", "117.212669,39.133667", "117.213165,39.133297", "117.213203,39.13327", "117.213554,39.133099", "117.213669,39.13295", "117.213921,39.132462", "117.214088,39.132126", "117.214142,39.131962", "117.214188,39.13176", "117.214233,39.131397", "117.21418,39.13055", "117.214279,39.130459", "117.214539,39.130375", "117.214874,39.130188", "117.216881,39.128716", "117.217598,39.127995", "117.217972,39.12759", "117.218338,39.127178", "117.218407,39.127071", "117.218567,39.126911", "117.219704,39.125702", "117.219795,39.12561", "117.220284,39.125114", "117.220619,39.124802", "117.221046,39.124348", "117.221138,39.124245", "117.221268,39.124092", "117.222321,39.122955", "117.222824,39.122406", "117.222916,39.122311", "117.223663,39.121544", "117.2239,39.121452", "117.224113,39.12159", "117.224251,39.121677", "117.225136,39.122208", "117.225281,39.122292", "117.225319,39.122311", "117.226273,39.122875", "117.226685,39.123127", "117.227371,39.12352", "117.227806,39.123779", "117.228477,39.124134", "117.228531,39.124161", "117.228531,39.124161", "117.228668,39.124187", "117.228897,39.124325", "117.229767,39.12479", "117.230927,39.12545", "117.231186,39.12561", "117.231659,39.125908", "117.231834,39.126026", "117.232018,39.126186", "117.232185,39.126362", "117.232353,39.126583", "117.232658,39.126972", "117.232658,39.126972", "117.233124,39.12748", "117.233253,39.127609", "117.233368,39.127689", "117.233513,39.127762", "117.233665,39.127823", "117.233734,39.127846", "117.233833,39.127865", "117.233994,39.127888", "117.234138,39.127892", "117.234329,39.127884", "117.234612,39.127838", "117.234955,39.127754", "117.235252,39.12767", "117.236282,39.12738", "117.237137,39.127129", "117.237671,39.126961", "117.237953,39.126949", "117.238213,39.126865", "117.238472,39.126793", "117.2397,39.126434", "117.242233,39.125698", "117.243538,39.12532", "117.243645,39.125298",}; for (String point : points) { data = new PointData(); data.setLongitudeEx(Double.parseDouble(point.split(",")[0])); data.setLatitudeEx(Double.parseDouble(point.split(",")[1])); list.add(data); } List<PointData> gpsDataList = toDilute(list); System.out.println(points.length + "---------------" + gpsDataList.size()); System.out.println(gpsDataList.toString()); } }
2.3 结果
80---------------46 [PointData(isDelete=0, longitudeEx=117.212448, latitudeEx=39.133785), PointData(isDelete=0, longitudeEx=117.212669, latitudeEx=39.133667), PointData(isDelete=0, longitudeEx=117.213203, latitudeEx=39.13327), PointData(isDelete=0, longitudeEx=117.213554, latitudeEx=39.133099), PointData(isDelete=0, longitudeEx=117.213669, latitudeEx=39.13295), PointData(isDelete=0, longitudeEx=117.214088, latitudeEx=39.132126), PointData(isDelete=0, longitudeEx=117.214188, latitudeEx=39.13176), PointData(isDelete=0, longitudeEx=117.214233, latitudeEx=39.131397), PointData(isDelete=0, longitudeEx=117.21418, latitudeEx=39.13055), PointData(isDelete=0, longitudeEx=117.214279, latitudeEx=39.130459), PointData(isDelete=0, longitudeEx=117.214539, latitudeEx=39.130375), PointData(isDelete=0, longitudeEx=117.214874, latitudeEx=39.130188), PointData(isDelete=0, longitudeEx=117.216881, latitudeEx=39.128716), PointData(isDelete=0, longitudeEx=117.217598, latitudeEx=39.127995), PointData(isDelete=0, longitudeEx=117.218338, latitudeEx=39.127178), PointData(isDelete=0, longitudeEx=117.218407, latitudeEx=39.127071), PointData(isDelete=0, longitudeEx=117.219704, latitudeEx=39.125702), PointData(isDelete=0, longitudeEx=117.220284, latitudeEx=39.125114), PointData(isDelete=0, longitudeEx=117.220619, latitudeEx=39.124802), PointData(isDelete=0, longitudeEx=117.222824, latitudeEx=39.122406), PointData(isDelete=0, longitudeEx=117.223663, latitudeEx=39.121544), PointData(isDelete=0, longitudeEx=117.2239, latitudeEx=39.121452), PointData(isDelete=0, longitudeEx=117.225136, latitudeEx=39.122208), PointData(isDelete=0, longitudeEx=117.227806, latitudeEx=39.123779), PointData(isDelete=0, longitudeEx=117.228531, latitudeEx=39.124161), PointData(isDelete=0, longitudeEx=117.228668, latitudeEx=39.124187), PointData(isDelete=0, longitudeEx=117.228897, latitudeEx=39.124325), PointData(isDelete=0, longitudeEx=117.229767, latitudeEx=39.12479), PointData(isDelete=0, longitudeEx=117.230927, latitudeEx=39.12545), PointData(isDelete=0, longitudeEx=117.231659, latitudeEx=39.125908), PointData(isDelete=0, longitudeEx=117.231834, latitudeEx=39.126026), PointData(isDelete=0, longitudeEx=117.232018, latitudeEx=39.126186), PointData(isDelete=0, longitudeEx=117.232185, latitudeEx=39.126362), PointData(isDelete=0, longitudeEx=117.232658, latitudeEx=39.126972), PointData(isDelete=0, longitudeEx=117.233253, latitudeEx=39.127609), PointData(isDelete=0, longitudeEx=117.233368, latitudeEx=39.127689), PointData(isDelete=0, longitudeEx=117.233513, latitudeEx=39.127762), PointData(isDelete=0, longitudeEx=117.233734, latitudeEx=39.127846), PointData(isDelete=0, longitudeEx=117.233994, latitudeEx=39.127888), PointData(isDelete=0, longitudeEx=117.234329, latitudeEx=39.127884), PointData(isDelete=0, longitudeEx=117.234612, latitudeEx=39.127838), PointData(isDelete=0, longitudeEx=117.234955, latitudeEx=39.127754), PointData(isDelete=0, longitudeEx=117.236282, latitudeEx=39.12738), PointData(isDelete=0, longitudeEx=117.237671, latitudeEx=39.126961), PointData(isDelete=0, longitudeEx=117.237953, latitudeEx=39.126949), PointData(isDelete=0, longitudeEx=117.243645, latitudeEx=39.125298)]
3.优化说明
- 使用了JKD8的语法
- 查找最大距离点的方法进行了优化
