About the algorithm for linking the coordinates of an object to the road graph

Irina Polyakova, Svetlana Burdukovskaya


The article deals with algorithm for linking the coordinates of an object to a road graph. Similar algorithms are used in every application due to the widespread use of electronic devices. Such algorithms may have some inaccuracies, which makes it difficult to determine the exact location of the object. In this paper, we search for the reasons for the inaccuracies of the algorithm using previously existing approaches, and propose an algorithm that eliminates some inaccuracies and time delays. The presented algorithm has estimates of similarity, proximity, and orientation. For the estimates, methods are considered that allow you to determine the location on each graph more accurately and quickly. The formulas for finding the exact GPS-coordinates which are used in this algorithm are presented. All the data obtained were compared with the reference solution. The algorithm showed the greatest improvement - 90% - that occurred during the turn. Previously, the maximum position error was 88 m, while the solution of the new algorithm differed only by 8 m from the reference trajectory. Studies have shown that the data received from the GPS receiver coincides almost everywhere with the road graph. The proposed algorithm showed improvements of an average of 50% compared to the algorithm, which is based on previously existing approaches. The algorithm works well even with relatively poor or busy GPS data. The algorithm in question was implemented in C# using the platform .NET and Unity3D, as well as Visual Studio development environments

Full Text:

PDF (Russian)


Lianxia Xi, Quan Liu, Minghua Li, Zhong Liu, “Map Matching Algorithm and Its Application,” College of Computer Science and Technology, Soochow University, SuZhou 215006, P. R. China, State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, P. R. China, vol. 7, 2007.

Greenfeld, J.S. “Matching GPS observations to locations on a digital map,” - Washington: In proceedings of the 81st Annual Meeting of the Transportation Research Board. 2002.

Hofmann-Wellenhoff, B., Lichtenegger H. and Collins J. GPS: Theory and Practice, 4th Edition, Springer-Verlag, New York, 1997.

Joshua S. Greenfeld. “Matching GPS Observations to Locations on a Digital Map. - Washington,” DC: Department of Civil and Environmental Engineering, New Jersey Institute of Technology, 2002. p.13

Pereira, F.C., Costa, H. and Pereira, N.M. “An off-line map-matching algorithm for incomplete map databases,” European Conference of Transport Research Institutes (ECTRI), 2009. p. 124

Pingfu Chao, Yehong Xu, Wen Hua, and Xiaofang Zhou. “A Survey on Map-Matching Algorithms, Australia: School of Information Technology and Electrical Engineering,” The University of Queensland, 2009. p.12

Zheng, K., Zheng, Y., Xie, X., Zhou, X. “Reducing uncertainty of low-sampling-rate trajectories” IEEE 28th International Conference on Data Engineering. 2012. pp.1144–1155.

Chen, W., Yu, M., Li, Z.-L. Chen, Y.-Q. “Integrated vehicle navigation system for urban applications” Proceedings of the 7th International Conference on Global Navigation Satellite Systems (GNSS), 2003, pp. 15-22.

Quddus M.A., Ochieng W.Y., Zhao L., Noland R.B. “A general map matching algorithm for transport telematics applications”, GPS Solutions, 2003. pp. 157-167.

Gustafsson, F., Gunnarsson, F., Bergman, N. Forssell, U, Jansson, J., Karlsson, R., Nordlund. P. “Particle filters for positioning, navigation, and tracking”, IEEE Transactions on Signal Processing. 2002, pp. 50, 425- 435.

Krakiwsky, E. J., Harris C. B., Wong R. V. C. “A Kalman Filter for Integrating Dead Reckoning, Map Matching and GPS Positioning”, Proceedings of IEEE Position Location and Navigation Symposium. 1988, pp. 39-46.

Bernstein D., Kornhauser A. An introduction to map matching for personal navigation assistants [Электронный ресурс]. – Электрон. дан. - URL: http://www.njtude.org/reports/mapmatchintro.pdf. (Дата обращения: 19 февраля 2020).

White, C.E., Bernstein, D., Kornhauser, A.L. “Some map matching algorithms for personal navigation assistants”, Transportation Research Part C 8, 2000. pp. 91-108.

Blazquez, C.A., Vonderohe, A.P. “Simple map-matching algorithm applied to intelligent winter maintenance vehicle data”, Transportation Research Record 1935, 2005. pp .68-76.

Yin H., Wolfson O. “A weight-based map matching method in moving objects databases”, Scientific and Statistical Database Management, 2004. pp. 437-438.

Meng, Y. “Improved Positioning of Land Vehicle in ITS Using Digital Map and Other Accessory Information”, 2006.

Taylor, G., Blewitt, G., Steup, D., Corbett, S., Car, A. “ Road reduction filtering for GPS-GIS navigation”, 2001, pp. 193-207.

Ochieng, W.Y., Quddus, M.A. and Noland, R.B. “Map matching in complex urban road networks”, Brazilian Journal of Cartography (Revista Brasileira de Cartografia), 55(2), 1-18.

Ларкович С.Н. “Unity на практике. Создаем 3D-игры и 3D-миры.” - М.: Наука и Техника, 2019. - 272 с.

Jeremy Gibson Bond. “Introduction to Game Design, Prototyping, and Development: From Concept to Playable Game with Unity and C#, Addison-Wesley Professional”, 2017, vol. 928.

Thorn A. “Unity Animation Essentials” - Packt Publishing Ltd, 2015, 176 p.

Troelsen A., Japikse P. “Pro C# 7 With .NET and .NET Core”, Apress, 2017, vol. 1328 .

Gittleman A. “Computing with C# and the .NET Framework”, 2011, Jones & Bartlett Learning, vol. 756.

Albahari J., Albahari B. “C# 7.0 Pocket Reference”, 2017, O′Reilly, vol. 240.


  • There are currently no refbacks.

Abava  Absolutech Convergent 2020

ISSN: 2307-8162