Алгоритм согласованного геометрического упрощения пространственных объектов различного типа на основе диаграммы Вороного

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

Посмотреть или загрузить статью (Rus)

Об авторах

О.П. Якимова

Ярославский государственный университет им. П.Г. Демидова,
ул. Советская, д. 14, Ярославль, Россия, 150003,
E-mail: olga_pavl02@mail.ru

И.К. Елистратов

Ярославский государственный университет им. П.Г. Демидова,
ул. Советская, д. 14, Ярославль, Россия, 150003,
E-mail: ivan.elistrat@mail.ru

Аннотация

Картографическая генерализация заключается в отборе значимых объектов и явлений для отображения на карте, а также в их обобщении таким образом, чтобы сохранились ключевые особенности, характерные черты и взаимосвязи, соответствующие требованиям конкретной задачи и выбранному масштабу карты. Важнейшим этапом картографической генерализации является геометрическое упрощение линейных и полигональных объектов. Общепринятой является практика независимого упрощения отдельных слоев пространственных данных, что ведет к возникновению топологических конфликтов и требует ручной коррекции ошибок. В настоящей работе предлагается оригинальный алгоритм согласованного геометрического упрощения. На первом этапе работы алгоритма строится триангуляция Делоне для точек из всех слоев пространственных данных. Далее по ней создается диаграмма Вороного. Ячейка диаграммы помечается идентификатором объекта, которому принадлежит точка внутри ячейки, или списком идентификаторов, если точка является точкой пересечения или касания нескольких объектов. Упрощение производится на основе двух правил: точку можно удалить, если угол поворота меньше заданного параметра и если стягивающий отрезок не пересекает ячейку с идентификатором, отличным от того, которым помечена ячейка удаляемой точки. Тестирование предлагаемого алгоритма производилось на фрагментах карт м-ба 1:500 000 и 1:1 000 000. Было произведено сравнение результатов работы алгоритма согласованного упрощения с алгоритмами Дугласа-Пейкера и Висвалингам-Уайатта, реализованными в ГИС QGIS, причем их параметры подбирались так, чтобы в результате было примерно одинаковое количество точек. Слои пространственных данных, упрощенные предлагаемым алгоритмом, не содержат разрывов и наложений объектов, т. е. сохраняют топологические отношения.

Ключ. слова

алгоритм согласованного упрощения, топологические отношения, диаграмма Вороного, триангуляция Делоне, пространственные данные

Список литературы

  1. Берлянт А.М. Картография. 4-е изд. М.: КДУ, 2014. 448 с.
  2. Делоне Б.Н. О пустоте сферы. Известия АН СССР, ОМЕН, 1934. № 4. С. 793–800.
  3. Салищев К.А. Картоведение. 1-е изд. М.: Издательство Московского университета, 1976. 438 с.
  4. Самсонов Т.Е., Якимова О.П., Алексеев В.В., Богаевская В.Г., Горохов А.А., Князев В.Н., Преображенская М.М., Ухалов А.Ю., Эдельсбруннер Х. Алгоритм геометрического упрощения множества линий путем стягивания ребер графа с сохранением топологии. Геодезия и картография, 2014. № 3. С. 29–36. DOI: 10.22389/0016-7126-2014-885-3-29-36.
  5. Свентэк Ю.В. Теоретические и прикладные аспекты современной картографии. М.: Эдиториал УРСС, 1999. 80 с.
  6. Скворцов А.В. Обзор алгоритмов построения триангуляции Делоне. Вычислительные методы и программирование, 2002. Т. 3. Вып. 1. С. 14–39.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. Rhind D. Generalization and Realism Within Automated Cartographic System. Canadian Cartographer, 1973. V. 10. No. 1. P. 51–62.
  16. 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.
  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. Nouvelles Applications des Paramètres Continus à la Théorie des Formes Quadratiques. Journal für die Reine und Angewandte Mathematik, 1908. V. 134. P. 198–287. 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.

Для цитирования: Якимова О.П., Елистратов И.К. Алгоритм согласованного геометрического упрощения пространственных объектов различного типа на основе диаграммы Вороного. ИнтерКарто. ИнтерГИС. M.: Географический факультет МГУ, 2025. Т. 31. Ч. 1. С. 355–368. DOI: 10.35595/2414-9179-2025-1-31-355-368

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)