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

doi:10.3969/j.issn.1001-2400.2014.05.026

J4 ›› 2014, Vol. 41 ›› Issue (5): 155-160.doi: 10.3969/j.issn.1001-2400.2014.05.026

• Original Articles • Previous Articles Next Articles

Adaptive binary search polyline simplification algorithm for GPS trajectories

WANG Jing¹;TAN Xiangshuang¹;SONG Xianfeng^1,2;WANG Chaoliang²

(1. College of Resources and Environment, Graduate University of Chinese Academy of Sciences, Beijing 100049, China;
2. Academy of Opto-Electronics, Chinese Academy of Sciences, Beijing 100094, China)

Received:2013-07-09 Online:2014-10-20 Published:2014-11-27
Contact: WANG Jing E-mail:qiufengwj@163.com

Abstract

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

CLC Number:

P208

WANG Jing;TAN Xiangshuang;SONG Xianfeng;WANG Chaoliang. Adaptive binary search polyline simplification algorithm for GPS trajectories[J].J4, 2014, 41(5): 155-160.

References

［1］ Ivanov R. Real-time GPS Track Simplification Algorithm for Outdoor Navigation of Visually Impaired［J］. Journal of Network and Computer Applications, 2012, 35(5): 1559-1567.
［2］ Park W, Yu K. Hybrid Line Simplification for Cartographic Generalization［J］. Pattern Recognition Letters, 2011, 32(9): 1267-1273.
［3］ McMaster R B. The Geometric Properties of Numerical Generalization［J］. Geographical Analysis, 1987, 19(4): 330-346.
［4］ Douglas D, Peucker T. Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature［J］. The Canadian Cartographer, 1973, 10(2): 112-122.
［5］黄娟, 程耀东. 多分辨率小波分析在GIS线状要素简化中的应用［J］. 唐山学院学报, 2010, 23(7): 13-16.
Huang Juan, Cheng Yaodong. Application of Multi-resolution Wavelet Analysis in GIS Linear Element Simplification［J］. Journal of Tangshan College, 2010, 23(7): 13-16.
［6］任海艳, 陈飞翔. 自适应遗传算法的改进及在曲线化简中的应用［J］. 计算机工程与应用, 2012, 48(11): 152-155.
Ren Haiyan, Chen Feixiang. Improvement of Adaptive Genetic Algorithms and Application in Line Simplification［J］. Computer Engineering and Applications, 2012, 48(11): 152-155.
［7］武芳, 邓红艳. 基于遗传算法的线要素自动化简模型［J］. 测绘学报, 2003, 32(4): 349-355.
Wu Fang, Deng Hongyan. Using Genetic Algorithms for Solving Problems in Automated Line Simplification［J］. Acta Geodaetica et Cartographica Sinica, 2003, 32(4): 349-355.
［8］ Zhao Z, Saalfeld A. Linear-time Sleeve-fitting Polyline Simplification Algorithms［DB/OL］. ［2012-12-30］. http://mapcontext.com/autocarto/proceedings/auto-carto-131pdf/linear-time-sleeve-fitting-pdyline-simplification-algorithm.pdf.
［9］ Reumann K, Witkam A P M. Optimizing Curve Segmentation in Computer Graphics［C］//Proceedings of International Computing Symposium. Amsterdam: North-Holland, 1974: 467-472.
［10］ Opheim H. Fast Data Reduction of a Digitized Curve［J］. Geo-Processing, 1982, 2: 33-40.
［11］ Lang T. Rules for Robot Draughtsmen［J］. Geographical Magazine, 1969, 42(1): 50-51.

Adaptive binary search polyline simplification algorithm for GPS trajectories

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 1

Metrics

Comments

Recommended 0