关键词: GPS 航迹, 线化简, 折半查找, 最优骨架点

Abstract:

This paper proposes an adaptive binary search polyline simplification algorithm for simplifying GPS trajectories, 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: (1)Dynamically predicting the search step to determine quickly a search interval within which at least one skeleton point falls; (2)Applying a binary search in the search interval of the GPS trajectory 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.

Key words: GPS trajectories, binary search, polyline simplification, the optimal skeleton point