基于动态规划的逐点后退法在路线压缩中的应用研究  

A study on the application of the point-by-point backward methodbased on dynamic programming in route compression

作　　者：李岩 王佳豪 王利民[1] LI Yan;WANG Jiahao;WANG Limin(Hebei University of Architecture,Zhangjiakou,Hebei 075000)

机构地区：[1]河北建筑工程学院,河北张家口075000

出　　处：《河北建筑工程学院学报》2024年第1期238-243,共6页Journal of Hebei Institute of Architecture and Civil Engineering

摘　　要：提出了一种路线数据压缩算法,该算法以“道格拉斯-普克(Douglas-Peucker, DP)压缩算法”为基础,并对其进行了一系列的改进。该算法对路线中的矢量坐标,以所设定的阈值为参考标准,从后向前递归的进行压缩,并提取出特征点。相对于DP算法,本算法具有更高的压缩效率,更小的压缩误差,在相对复杂曲线的压缩上,本算法在准确度方面具有更优异的表现。通过进一步结合动态规划方法,可使该算法平均误差在原算法的基础上再降低70%的误差,从而保证了压缩后曲线的准确度和完整性。A route data compression algorithm based on Douglas-Peucker(DP)compression algorithm is presented.The algorithm uses the set threshold as a reference standard to compress vector coordinates in the path from backward to forward recursively and extract feature points.Compared with the DP algorithm,this algorithm has higher compression efficiency,smaller compression errors,and better curve compression accuracy.By combining the dynamic programming method,the average error can be reduced by 70%,and the optimal compression curve can be found,thus as to ensure the accuracy and completeness of the compression curve.

关 键 词：曲线压缩 DP算法 动态规划算法 特征点 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]