Algorithm for consistent geometric simplification of spatial objects of various types based on the Voronoi diagram

DOI: 10.35595/2414-9179-2025-1-31-355-368

View or download the article (Rus)

About the Authors

Olga P. Yakimova

Demidov Yaroslavl State University,
14, Sovetskaya str., Yaroslavl, 150003, Russia,
E-mail: olga_pavl02@mail.ru

Ivan K. Elistratov

Demidov Yaroslavl State University,
14, Sovetskaya str., Yaroslavl, 150003, Russia,
E-mail: ivan.elistrat@mail.ru

Abstract

Cartographic generalization is the process of graphically reducing information from reality or larger-scale maps. The objective is to display only the information necessary at a specific scale. After generalization, maps can show the main things and essential characteristics. The scale, application and theme of maps, geographical features of cartographic regions and graphic dimensions of symbols are the main factors affecting cartographic generalization. Geometric simplification is a fundamental aspect of cartographic generalization. The practice of independently simplifying separate layers of spatial data is common, which leads to topological conflicts and necessitates manual correction of errors. This paper proposes an original algorithm for consistent geometric simplification. In the first step of the algorithm, a Delaunay triangulation is constructed for points from all spatial data layers. A Voronoi diagram is then created using this triangulation. A cell of the diagram is marked with the object identifier to which the point inside the cell belongs, or by a list of identifiers if the point is an intersection or touch point of multiple objects. The simplification is based on two rules: a point can be deleted if the rotation angle is less than a specified parameter and if the constricting segment does not intersect a cell with an identifier different from the one marking the cell of the point to be deleted. The proposed algorithm was tested on fragments of 1:500 000 and 1:1 000 000 scale maps. The results of the consistent simplification algorithm were compared with the Douglas-Peucker and Visvalingham-Whyatt algorithms implemented in QGIS, and their parameters were chosen so that the result was approximately the same number of points. The spatial data layers simplified by the proposed algorithm do not contain discontinuities and overlaps of objects, i. e. they preserve topological relations.

Keywords

consistent simplification algorithm, topological relations, Voronoi diagram, Delaunay triangulation, spatial data

References

  1. Berlyant A.M. Cartography. 4th ed. Moscow: KDU, 2014. 448 p. (in Russian).
  2. De Berg M., Van Kreveld M., Schirra S. Topologically Correct Subdivision Simplification Using the Bandwidth Criterion. Cartography and Geographic Information Science, 1998. V. 25. P. 243–257. DOI: 10.1559/152304098782383007.
  3. Delone B.N. On the Emptiness of a Sphere. News of the Academy of Sciences of USSR, Department of Mathematical and Natural Sciences, 1934. No. 4. P. 793–800 (in Russian).
  4. Dettori G., Puppo E. How Generalization Interacts with the Topological and Metric Structure of Maps, in Proceedings of the VII International Symposium on Spatial Data Handling, 1997. P. 559–570.
  5. Douglas D.H., Peucker T.K. Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or its Caricature. Canadian Cartographer, 1973. V. 10. No. 2. P. 112–122.
  6. Dubuisson M.P., Jain A.A Modified Hausdorff Distance for Object Matching. Proceedings of XII International Conference on Pattern Recognition. IEEE Computer Society Press, 1994. V. 1. P. 566–568. DOI: 10.1109/ICPR.1994.576361.
  7. Li Z., Openshaw S. Algorithms for Automated Line Generalization Based on a Natural Principle of Objective Generalization. International Journal of Geographical Information Systems, 1992. V. 6. No. 5. P. 373–389. DOI: 10.1080/02693799208901921.
  8. McMaster R.B. Automated Line Generalization. Cartographica: The International Journal for Geographic Information and Geovisualization, 1987. V. 24. No. 2. P. 74–111. DOI: 10.3138/3535-7609-781G-4L20.
  9. Monmonier M. Displacement in Vector-And Raster-Mode Graphics. Cartographica: The International Journal for Geographic Information and Geovisualization, 1987. V. 24. No. 4. P. 25–36. DOI: 10.3138/FW8R-2122-PT42-53M2.
  10. Raposo P. Scale-Specific Automated Line Simplification by Vertex Clustering on a Hexagonal Tessellation. Cartography and Geographic Information Science, 2013. V. 40. No. 5. P. 427–443. DOI: 10.1080/15230406.2013.803707.
  11. Rhind D. Generalization and Realism Within Automated Cartographic System. Canadian Cartographer, 1973. V. 10. No. 1. P. 51–62.
  12. Saalfeld A. Topologically Consistent Line Simplification with the Douglas-Peucker Algorithm. Cartography and Geographic Information Science, 1999. V. 26. No. 1. P. 7–18. DOI: 10.1559/152304099782424901.
  13. Salishchev K.A. Cartography. 1 ed. Moscow: Moscow University Press, 1976. 438 p. (in Russian).
  14. Samsonov T.E., Yakimova O.P., Alekseev V.V., Bogaevskaya V.G., Gorokhov A.A., Knyazev V.N., Preobrazhenskaya M.M., Ukhalov A.Yu., Edelsbrunner H. An Algorithm for Geometric Simplification of a Set of Lines by Contracting Graph Edges While Preserving Topology. Geodesy and Cartography, 2014. No. 3. P. 29–36 (in Russian). DOI: 10.22389/0016-7126-2014-885-3-29-36.
  15. Skvortsov A.V. A Review of Algorithm for Constructing the Delaunay Triangulation. Numerical Methods and Programming, 2002. V. 3. Iss. 1. P. 14–39 (in Russian).
  16. Sventek Yu.V. Theoretical and Applied Aspects of Modern Cartography. Moscow: Editorial URSS, 1999. 80 p. (in Russian).
  17. Van Der Poorten P.M., Jones C.B. Characterisation and Generalisation of Cartographic Lines Using Delaunay Triangulation. International Journal of Geographical Information Science, 2002. V. 16. No. 8. P. 773–794. DOI: 10.1080/13658810210149434.
  18. Visvalingham M., Whyatt J. Line Generalization by Repeated Elimination of Points. Cartographic Journal, 1993. V. 30. No. 1. P. 46–51. DOI: 10.1179/000870493786962263.
  19. Voronoi G.F. New Applications of Continuous Parameters to the Theory of Quadratic Forms. Journal for the Queen and Mathematics, 1908. V. 134. P. 198–287 (in French). DOI: 10.1515/crll.1908.133.97/html.
  20. Wang Z., Muller J.C. Complex Coastline Generalization. Cartography and Geographic Information Systems, 1993. V. 20. Iss. 2. P. 96–106. DOI: 10.1559/152304093782610333.
  21. Wei Z., Liu Y., Cheng L., Ding S.A Progressive and Combined Building Simplification Approach with Local Structure Classification and Backtracking Strategy. ISPRS International Journal of Geo-Information, 2021. V. 10. Iss. 5. Art. 302. DOI: 10.3390/ijgi10050302.
  22. Yakimova O.P., Murin D.M., Gorshkov V.G. Joint Simplification of Various Types of Spatial Objects While Preserving Topological Relations. Automatic Control and Computer Sciences, 2024. V. 58. No. 7. P. 202–212. DOI: 10.3103/S0146411624700378.

For citation: Yakimova O.P., Elistratov I.K. Algorithm for consistent geometric simplification of spatial objects of various types based on the Voronoi diagram. InterCarto. InterGIS. Moscow: MSU, Faculty of Geography, 2025. V. 31. Part 1. P. 355–368. DOI: 10.35595/2414-9179-2025-1-31-355-368 (in Russian)