GPS航迹线的自适应折半查找化简算法

Adaptive binary search polyline simplification algorithm for GPS trajectories

提出了一种新的全球定位系统(GPS)航迹线自适应折半查找化简算法,采用了Sleeve-fitting算法的最优骨架点判断模式来保证航迹线的化简质量,通过粗筛与精选相结合的分步处理方式来提高化简效率:粗筛是利用经验步长值动态预测下一步搜索步长,快速确定包含骨架点的搜索区间;精选是在搜索区间内利用折半查找的方式搜索到骨架点.将某市城区的GPS航迹数据应用于文中算法,结果表明,该算法大幅度提高了化简效率,同时最大程度地保持了化简后航迹线与原始航迹在形态特征上的一致性.

This paper proposes an adaptive binary search polyline simplification algorithm for simplifying GPS traj ectories,which adopts the optimal skeleton point conceptual model of the Sleeve-fitting algorithm to retain a maximum point reduction.Meanwhile,the innovating modifications of screening roughly and handpickedly are suggested to improve the efficiency of simplification process significantly： Dynamically predicting the search step to determine quickly a search interval within which at least one skeleton point falls; Applying a binary search in the search interval of the GPS traj ectory to locate the optimal skeleton point.The GPS trajectories acquired in Huaibei City,China are used for testing polyline simplification.As a result,our proposed algorithm preserves the best shape characteristics with a shortest running time.