A fast O(N) multiresolution polygonal approximation algorithm for GPS trajectory simplification.
Recent advances in geopositioning mobile phones have made it possible for users to collect a large number of GPS trajectories by recording their location information. However, these mobile phones with built-in GPS devices usually record far more data than needed, which brings about both heavy data storage and a computationally expensive burden in the rendering process for a Web browser. To address this practical problem, we present a fast polygonal approximation algorithm in 2-D space for the GPS trajectory simplification under the so-called integral square synchronous distance error criterion in a linear time complexity. The underlying algorithm is designed and implemented using a bottom-up multiresolution method, where the input of polygonal approximation in the coarser resolution is the polygonal curve achieved in the finer resolution. For each resolution (map scale), priority-queue structure is exploited in graph construction to construct the initialized approximated curve. Once the polygonal curve is initialized, two fine-tune algorithms are employed in order to achieve the desirable quality level. Experimental results validated that the proposed algorithm is fast and achieves a better approximation result than the existing competitive methods.
School of Computing, University of Eastern Finland, 80101 Joensuu, Finland. mchen@cs.joensuu.fi
Minjie
M
Chen
Mantao
M
Xu
Pasi
P
Fränti
D000465:Algorithms; D040362:Geographic Information Systems; D007089:Image Enhancement / Q000379:methods; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D021621:Imaging, Three-Dimensional / Q000379:methods*; D016247:Information Storage and Retrieval / Q000379:methods*; D010363:Pattern Recognition, Automated / Q000379:methods*; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity