Java【算法分享 02】道格拉斯-普克 Douglas-Peucker 抽稀算法分析及15w个坐标点抽稀到3.7w耗时从360s+优化到365ms接近1000倍的速度提升(并行流+多线程+泛型)

简介: Java【算法分享 02】道格拉斯-普克 Douglas-Peucker 抽稀算法分析及15w个坐标点抽稀到3.7w耗时从360s+优化到365ms接近1000倍的速度提升(并行流+多线程+泛型)

1.分析

算法详细流程可查看《道格拉斯抽稀算法流程图解+使用JDK8方法实现+详细注解源码》经典的 D-P 算法描述如下【红色部分用于辅助理解 可忽略】:

  1. 连接当前矢量曲线首尾点a、b,该直线AB为当前矢量曲线的弦;
  2. 计算首尾点a、b间所有坐标点到该弦AB的距离,并获取最大距离d及其的坐标点c
  3. 比较最大距离d与给定的阈值thresholdVal,小于阈值,当前弦AB可作为曲线的近似【首尾间的坐标点将被抽稀】,该段矢量曲线处理完毕。
  4. 大于阈值,使用最大距离坐标点c分割当前矢量曲线,分割后的两段矢量曲线分别使用1~3的流程进行处理。
  5. 全部处理完毕后,依次连接各个分割点形成的折线,即可以作为整个曲线的近似。

算法耗时及问题分析:

  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 :image.png

坐标点较多时,每个点都要计算 A、B、C 三个参数并求解 d 将消耗不少时间。【耗时】

  1. 得到分割点后,递归调用起止点计算标记删除点方法,可能出现栈溢出。【问题】
  2. thresholdVal 值越小保留细节将越多,分割点会呈现指数级增长,耗时会增加,需要找到合理值。【耗时+问题】
  3. 返回对象包含字段不统一,抽稀算法无法接收不同类型参数。【问题】

2.优化

1️⃣ 个算法使用的封装类和 1️⃣ 个业务使用封装类用于举例【为了简洁注解未使用DOC规范】:

// 类1 坐标数据封装
@Data
public class PointData {
    // 标记是否删除(0保留 1删除)
    private int isDelete;
    // 数据点的 index 用于优化运算速度(核心优化点)
    private int indexEx;
  // 数据点的经度
    private double longitudeEx;
    // 数据点的纬度
    private double latitudeEx;
}
// 类2 业务查询返回的数据封装【主要是实现了 PointData 类】具体字段不再贴出
@Data
public class Mobile2g extends PointData implements Serializable {
}

线程池不做过多介绍:

public class ThreadAllBaseStation {
    private static int corePoolSize = Runtime.getRuntime().availableProcessors();
    private static ThreadFactory namedFactory = new ThreadFactoryBuilder().setNameFormat("XXX数据查询线程-%d").build();
    /**
     * corePoolSize用于指定核心线程数量
     * maximumPoolSize指定最大线程数
     * keepAliveTime和TimeUnit指定线程空闲后的最大存活时间
     */
    public static ThreadPoolExecutor executor = new ThreadPoolExecutor(corePoolSize, corePoolSize + 1, 10L, TimeUnit.SECONDS,
            new LinkedBlockingQueue<>(1000), namedFactory, new ThreadPoolExecutor.AbortPolicy());
}

优化后的算法核心代码【为了简洁部分注解未使用DOC规范】:

@Slf4j
public class Douglas {
    // 点数据
    private static List<? extends PointData> points = new ArrayList<>();
    // 距离阈值(值越大效果越好但丢失细节就越多)【这个值已经算很小的了】
    private static final double DISTANCE_THRESHOLD = 0.00001;
    // 最大线程数
    private static final int MAX_THREAD_SIZE = 60;
    /**
     * 标记要删除的点(并获取分割点数据)
     *
     * @param from 矢量曲线的起始点
     * @param to   矢量曲线的终止点
     * @return 起始点 终止点 分割点
     */
    private static PointData[] markDeletePointsAndGetSplitPoint(PointData from, PointData to) {
        // 计算由起始点和终止点构成直线方程一般式的系数
        double fromLat = from.getLatitudeEx();
        double fromLng = from.getLongitudeEx();
        double toLat = to.getLatitudeEx();
        double toLng = to.getLongitudeEx();
        // 求解点到直线距离方程的参数
        double fromLatMinusToLat = fromLat - toLat;
        double fromLngMinusToLng = fromLng - toLng;
        double sqrtPowAddVal = Math.sqrt(Math.pow(fromLatMinusToLat, 2) + Math.pow(fromLngMinusToLng, 2));
        double parameterA = (fromLatMinusToLat) / sqrtPowAddVal;
        double parameterB = (toLng - fromLng) / sqrtPowAddVal;
        double parameterC = (fromLng * toLat - toLng * fromLat) / sqrtPowAddVal;
        // 获取点数据下标(并排除相邻两点的情况)【最核心的优化】
        int fromIndex = from.getIndexEx();
        int toIndex = to.getIndexEx();
        if (toIndex == fromIndex + 1) {
            return new PointData[]{};
        }
        // 起止点之间的点到起止点连线的距离数据集合并获取最大距离及分割点
        double distanceMax = 0;
        PointData splitPoint = null;
        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);
            if (distance > distanceMax) {
                distanceMax = distance;
                splitPoint = points.get(i);
            }
        }
        // 最大距离与距离阈值进行比较
        if (distanceMax < DISTANCE_THRESHOLD) {
            // 小于则标记 points(fromIndex,toIndex) 内的坐标(用于删除)
            for (int i = fromIndex + 1; i < toIndex; i++) {
                points.get(i).setIsDelete(1);
            }
        } else {
            // 返回起止点和分割点坐标
            return new PointData[]{from, to, splitPoint};
        }
        return new PointData[]{};
    }
    /**
     * 进行抽稀:标记要删除的点并筛选
     *
     * @param source 矢量曲线点数据
     * @return 抽稀后的点数据
     */
    public static List<? extends PointData> toDilute(List<? extends PointData> source) throws InterruptedException {
        // 抽稀前的点数据
        points = source;
        // 进行标记
        if (!CollectionUtils.isEmpty(points)) {
            // 首次标记
            long s1 = System.currentTimeMillis();
            PointData[] pointData = markDeletePointsAndGetSplitPoint(points.get(0), points.get(points.size() - 1));
            long s2 = System.currentTimeMillis();
            log.info("首次标记用时:" + (s2 - s1) + "ms");
            // 如果有分割点将进行分割标记
            int pointDataLength = 3;
            if (pointData.length == pointDataLength) {
                CopyOnWriteArrayList<PointData[]> splitPointList = new CopyOnWriteArrayList<>();
                splitPointList.add(pointData);
                // 使用线程池进行分割标记
                do {
                    splitPointList = markDeletePointsAndGetSplitPointByThread(splitPointList);
                } while (!splitPointList.isEmpty());
            }
        }
        // 筛选掉标记为删除的点
        return points.parallelStream().filter(point -> point.getIsDelete() != 1).collect(Collectors.toList());
    }
    /**
     * 使用多线程:标记要删除的点(并获取分割点数据)
     *
     * @param splitPointList 起始点及分割点栈数据
     * @return 新的起始点及分割点栈数据
     * @throws InterruptedException 线程等待可能出现的问题
     */
    private static CopyOnWriteArrayList<PointData[]> markDeletePointsAndGetSplitPointByThread(CopyOnWriteArrayList<PointData[]> splitPointList) throws InterruptedException {
        // 新一轮要处理的分割数据
        CopyOnWriteArrayList<PointData[]> splitPointListRes = new CopyOnWriteArrayList<>();
        int pointDataLength = 3;
        int splitPointListSize = splitPointList.size();
        log.info("当前列表Size:" + splitPointListSize);
        int numberBatch = MAX_THREAD_SIZE;
        double number = splitPointListSize * 1.0 / numberBatch;
        int n = ((Double) Math.ceil(number)).intValue();
        for (int i = 0; i < n; i++) {
            int end = numberBatch * (i + 1);
            if (end > splitPointListSize) {
                end = splitPointListSize;
            }
            List<PointData[]> pointData = splitPointList.subList(numberBatch * i, end);
            log.info("当前执行 " + numberBatch * i + " 到 " + end + "条数据");
            CountDownLatch countDownLatch = new CountDownLatch(pointData.size());
            ThreadPoolExecutor executor = ThreadAllBaseStation.executor;
            pointData.forEach(point -> {
                executor.submit(() -> {
                    PointData[] pointDataLeft = markDeletePointsAndGetSplitPoint(point[0], point[2]);
                    if (pointDataLeft.length == pointDataLength) {
                        splitPointListRes.add(pointDataLeft);
                    }
                    PointData[] pointDataRight = markDeletePointsAndGetSplitPoint(point[2], point[1]);
                    if (pointDataRight.length == pointDataLength) {
                        splitPointListRes.add(pointDataRight);
                    }
                    countDownLatch.countDown();
                });
            });
            countDownLatch.await();
        }
        return splitPointListRes;
    }
}

算法使用结合业务【伪代码】:

@OverrideData
    public void douglasAlgorithmTest() {
        // 抽稀前数据查询(坐标点需要有序)
        List<Mobile2g> beforeDouglas = selectData("queryParam");
        // 抽稀字段处理(坐标点)【优化】
        beforeDouglas.forEach(bd -> {
          bd.setIndexEx(indexEx.getAndIncrement());
            bd.setLongitudeEx(bd.getLongitude());
            bd.setLatitudeEx(bd.getLatitude());
        });
        // 抽稀后保存
        List<Mobile2g> afterDouglas = null;
        try {
          // 调用抽稀算法
            afterDouglas = (List<Mobile2g>) Douglas.toDilute(beforeDouglas);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

3.总结

  1. 使用泛型解决了不同对象的抽稀问题。
  2. 优化最大距离及分割点的获取方法。
  3. 使用多线程和并行流计算缩短了抽稀时间【增大线程MAX_THREAD_SIZE仍然可以提升效率】。
  4. 最核心的优化
// 原始代码【这个速度是很慢的 要比对每个对象才能找到 index】
int fromIndex = points.indexOf(from); 
// 事先对 PointData 对象添加了indexEx 属性 结果是惊人的快
int fromIndex = from.getIndexEx();
目录
相关文章
|
7天前
|
安全 Java 调度
Java编程时多线程操作单核服务器可以不加锁吗?
Java编程时多线程操作单核服务器可以不加锁吗?
21 2
|
9天前
|
Java 调度
Java-Thread多线程的使用
这篇文章介绍了Java中Thread类多线程的创建、使用、生命周期、状态以及线程同步和死锁的概念和处理方法。
Java-Thread多线程的使用
|
7天前
|
Java 数据中心 微服务
Java高级知识:线程池隔离与信号量隔离的实战应用
在Java并发编程中,线程池隔离与信号量隔离是两种常用的资源隔离技术,它们在提高系统稳定性、防止系统过载方面发挥着重要作用。
6 0
|
9天前
|
Java 数据处理 调度
Java中的多线程编程:从基础到实践
本文深入探讨了Java中多线程编程的基本概念、实现方式及其在实际项目中的应用。首先,我们将了解什么是线程以及为何需要多线程编程。接着,文章将详细介绍如何在Java中创建和管理线程,包括继承Thread类、实现Runnable接口以及使用Executor框架等方法。此外,我们还将讨论线程同步和通信的问题,如互斥锁、信号量、条件变量等。最后,通过具体的示例展示了如何在实际项目中有效地利用多线程提高程序的性能和响应能力。
|
4天前
|
传感器 算法 C语言
基于无线传感器网络的节点分簇算法matlab仿真
该程序对传感器网络进行分簇,考虑节点能量状态、拓扑位置及孤立节点等因素。相较于LEACH算法,本程序评估网络持续时间、节点死亡趋势及能量消耗。使用MATLAB 2022a版本运行,展示了节点能量管理优化及网络生命周期延长的效果。通过簇头管理和数据融合,实现了能量高效和网络可扩展性。
|
1月前
|
算法 BI Serverless
基于鱼群算法的散热片形状优化matlab仿真
本研究利用浴盆曲线模拟空隙外形,并通过鱼群算法(FSA)优化浴盆曲线参数,以获得最佳孔隙度值及对应的R值。FSA通过模拟鱼群的聚群、避障和觅食行为,实现高效全局搜索。具体步骤包括初始化鱼群、计算适应度值、更新位置及判断终止条件。最终确定散热片的最佳形状参数。仿真结果显示该方法能显著提高优化效率。相关代码使用MATLAB 2022a实现。
|
1月前
|
算法 数据可视化
基于SSA奇异谱分析算法的时间序列趋势线提取matlab仿真
奇异谱分析(SSA)是一种基于奇异值分解(SVD)和轨迹矩阵的非线性、非参数时间序列分析方法,适用于提取趋势、周期性和噪声成分。本项目使用MATLAB 2022a版本实现从强干扰序列中提取趋势线,并通过可视化展示了原时间序列与提取的趋势分量。代码实现了滑动窗口下的奇异值分解和分组重构,适用于非线性和非平稳时间序列分析。此方法在气候变化、金融市场和生物医学信号处理等领域有广泛应用。
|
1月前
|
资源调度 算法
基于迭代扩展卡尔曼滤波算法的倒立摆控制系统matlab仿真
本课题研究基于迭代扩展卡尔曼滤波算法的倒立摆控制系统,并对比UKF、EKF、迭代UKF和迭代EKF的控制效果。倒立摆作为典型的非线性系统,适用于评估不同滤波方法的性能。UKF采用无迹变换逼近非线性函数,避免了EKF中的截断误差;EKF则通过泰勒级数展开近似非线性函数;迭代EKF和迭代UKF通过多次迭代提高状态估计精度。系统使用MATLAB 2022a进行仿真和分析,结果显示UKF和迭代UKF在非线性强的系统中表现更佳,但计算复杂度较高;EKF和迭代EKF则更适合维数较高或计算受限的场景。
|
1月前
|
算法
基于SIR模型的疫情发展趋势预测算法matlab仿真
该程序基于SIR模型预测疫情发展趋势,通过MATLAB 2022a版实现病例增长拟合分析,比较疫情防控力度。使用SIR微分方程模型拟合疫情发展过程,优化参数并求解微分方程组以预测易感者(S)、感染者(I)和移除者(R)的数量变化。![]该模型将总人群分为S、I、R三部分,通过解析或数值求解微分方程组预测疫情趋势。
|
1月前
|
算法 数据可视化 数据安全/隐私保护
基于LK光流提取算法的图像序列晃动程度计算matlab仿真
该算法基于Lucas-Kanade光流方法,用于计算图像序列的晃动程度。通过计算相邻帧间的光流场并定义晃动程度指标(如RMS),可量化图像晃动。此版本适用于Matlab 2022a,提供详细中文注释与操作视频。完整代码无水印。
下一篇
无影云桌面