maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2023-4-340-353MSOUJWmais-1824Research ArticleAlgorithms in Computer ScienceСовместное упрощение пространственных объектов различного типа с сохранением топологических отношенийJoint simplification of various types spatial objects while preserving topological relationshipshttps://orcid.org/0000-0001-8816-2802ЯкимоваОльга ПавловнаYakimovaOlga P.olga_pavl02@mail.ruhttps://orcid.org/0000-0002-8068-0784МуринДмитрий МихайловичMurinDmitriy M.d.murin@uniyar.ac.ruhttps://orcid.org/0000-0002-2424-3942ГоршковВладислав ГеннадьевичGorshkovVladislav G.gorshkov.vladik@mail.ruЯрославский государственный университет им П.Г. ДемидоваРоссияP.G. Demidov Yaroslavl State UniversityRussian Federation202311122023304340353Copyright © Якимова О.П., Мурин Д.М., Горшков В.Г., 20232023Якимова О.П., Мурин Д.М., Горшков В.Г.Yakimova O.P., Murin D.M., Gorshkov V.G.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1824

Картографическая генерализация включает выбор отображаемых на карте объектов и явлений и их упрощение (обобщение) с сохранением основных типичных черт и характерных особенностей, а также взаимосвязей в соответствии с критериями, задаваемыми в запросе пользователем, в том числе решаемой задачей и масштабом отображаемой карты. Различные преобразования карт могут изменить отношения между объектами, тем более что общепринятой является практика упрощения каждого типа пространственных объектов независимо (сначала административные границы, потом дорожная сеть, населенные пункты, гидрографическая сеть и т. д.). Разрешение топологических конфликтов — одна из важнейших задач цифровой генерализации карт, решению которой уделяется особое внимание с начала исследований в этой области. Рассмотрение покрытий и сеточных структур позволяет свести более общую проблему коррекции топологических конфликтов к задаче разрешения топологических конфликтов внутри одной ячейки сетки. В настоящей работе предлагается новый алгоритм геометрического упрощения. Его особенностью является совместное упрощение множества пространственных объектов различного типа с сохранением их топологических отношений. Предлагаемый алгоритм имеет единственный параметр минимальный размер отображаемой на карте детали (обычно он равен одному миллиметру в целевом масштабе карты). Первым шагом алгоритма является построение специальной сеточной структуры данных. На ее основе для каждого пространственного объекта формируется последовательность ячеек, которым принадлежат точки данного объекта. Если в ячейке находятся точки только одного объекта, то его геометрическое упрощение происходит в рамках ограничивающей ячейки по алгоритму sleeve-fitting. Если в ячейке содержатся точки нескольких объектов, то геометрическое упрощение осуществляется с помощью специальной, сохраняющей топологию, процедуры.

Cartographic generalization includes the process of graphically reducing information from reality or larger scaled maps to display only the information that is necessary at a specific scale. After generalization, maps can show the main things and essential characteristics. The scale, use and theme of maps, geographical features of cartographic regions and graphic dimensions of symbols are the main factors affecting cartographic generalization. Geometric simplification is one of the core components of cartographic generalization. The topological relations of spatial features also play an important role in spatial data organization, queries, updates, and quality control. Various map transformations can change the relationships between features, especially since it is common practice to simplify each type of spatial feature independently (first administrative boundaries, then road network, settlements, hydrographic network, etc.). In order to detect the spatial conflicts a refined description of topological relationships is needed. Considering coverings and mesh structures allows us to reduce the more general problem of topological conflict correction to the problem of resolving topological conflicts within a single mesh cell. In this paper, a new simplification algorithm is proposed. Its peculiarity is the joint simplification of a set of spatial objects of different types while preserving their topological relations. The proposed algorithm has a single parameter — the minimum map detail size (usually it is equal to one millimeter in the target map scale). The first step of the algorithm is the construction of a special mesh data structure. On its basis for each spatial object a sequence of cells is formed, to which points of this object belong. If a cell contains points of only one object, its geometric simplification is performed within the bounding cell using the sleeve-fitting algorithm. If a cell contains points of several objects, geometric simplification is performed using a special topology-preserving procedure.

алгоритм упрощениятопологические отношениясеточная структура данныхпространственные данныесогласованная картографическая генерализацияsimplification algorithmtopological relationshipsmesh data structurespatial dataconsistent cartographic generalizationЯрославский государственный университет им. П.Г. Демидова, проект №GM-2023-03.P.G. Demidov Yaroslavl State University, project No. GM-2023-03.ReferencesW. Tobler, Numerical map generalization. Department of Geography, University of Michigan Ann Arbour, MI, USA, 1966.W. Tobler, Numerical map generalization. Department of Geography, University of Michigan Ann Arbour, MI, USA, 1966.F. Töpfer and W. Pillewizer, “The principles of selection,” Cartographic Journal, vol. 3, no. 1, pp. 10–16, 1966.F. Töpfer and W. Pillewizer, “The principles of selection,” Cartographic Journal, vol. 3, no. 1, pp. 10–16, 1966.J. D. Perkal, “Proba obiektywnej generalizacji,” Geodezia I Kartografia, vol. 7, no. 2, pp. 130–142, 1958.J. D. Perkal, “Proba obiektywnej generalizacji,” Geodezia I Kartografia, vol. 7, no. 2, pp. 130–142, 1958.U. Ramer, “An iterative procedure for the polygonal approximation of plane curves,” Computer Graphics and Image Processing, vol. 1, no. 3, pp. 244–256, 1972.U. Ramer, “An iterative procedure for the polygonal approximation of plane curves,” Computer Graphics and Image Processing, vol. 1, no. 3, pp. 244–256, 1972.D. H. Douglas and T. K. Peucker, “Algorithms for the reduction of the number of points required to represent a digitized line or its caricature,” Cartographica: the international journal for geographic information and geovisualization, vol. 10, no. 2, pp. 112–122, 1973.D. H. Douglas and T. K. Peucker, “Algorithms for the reduction of the number of points required to represent a digitized line or its caricature,” Cartographica: the international journal for geographic information and geovisualization, vol. 10, no. 2, pp. 112–122, 1973.J. S. Marino, “Identification of characteristic points along naturally occurring lines. an empirical study,” The Canadian cartographer Toronto, vol. 16, no. 1, 1979.J. S. Marino, “Identification of characteristic points along naturally occurring lines. an empirical study,” The Canadian cartographer Toronto, vol. 16, no. 1, 1979.G. Dutton, “Scale, sinuosity, and point selection in digital line generalization,” Cartography and Geographic Information Science, vol. 26, no. 1, pp. 33–54, 1999.G. Dutton, “Scale, sinuosity, and point selection in digital line generalization,” Cartography and Geographic Information Science, vol. 26, no. 1, pp. 33–54, 1999.A. Chehreghan and R. Ali Abbaspour, “Estimation of empirical parameters in matching of linear vector datasets: an optimization approach,” Model. Earth Syst. Environ , no. 3, pp. 1029–1043, 2017.A. Chehreghan and R. Ali Abbaspour, “Estimation of empirical parameters in matching of linear vector datasets: an optimization approach,” Model. Earth Syst. Environ , no. 3, pp. 1029–1043, 2017.A. Chehreghan and R. Ali Abbaspour, “A geometric-based approach for road matching on multi-scale datasets using a genetic algorithm,” Cartography and Geographic Information Science , vol. 45, no. 3, pp. 255–269, 2018.A. Chehreghan and R. Ali Abbaspour, “A geometric-based approach for road matching on multi-scale datasets using a genetic algorithm,” Cartography and Geographic Information Science , vol. 45, no. 3, pp. 255–269, 2018.R. A. Finkel and J. L. Bentley, “Quad trees a data structure for retrieval on composite keys,” Acta informatica, vol. 4, pp. 1–9, 1974.R. A. Finkel and J. L. Bentley, “Quad trees a data structure for retrieval on composite keys,” Acta informatica, vol. 4, pp. 1–9, 1974.A. Guttman, “R-trees: A dynamic index structure for spatial searching,” in Proceedings of the 1984 ACM SIGMOD international conference on Management of data, 1984, pp. 47–57.A. Guttman, “R-trees: A dynamic index structure for spatial searching,” in Proceedings of the 1984 ACM SIGMOD international conference on Management of data, 1984, pp. 47–57.U. A. Kravchenko, “Information geomodeling: the problem of data and knowledge representation.” 2013.U. A. Kravchenko, “Information geomodeling: the problem of data and knowledge representation.” 2013.G. Dettori and E. Puppo, “How generalization interacts with the topological and metric structure of maps,” in Proceedings of the 7th International Symposium on Spatial Data Handling, 1996, pp. 559–570.G. Dettori and E. Puppo, “How generalization interacts with the topological and metric structure of maps,” in Proceedings of the 7th International Symposium on Spatial Data Handling, 1996, pp. 559–570.D. Rhind, “Generalization and realism with automated cartographic system,” Canadian Cartographer , vol. 10, no. 1, pp. 51–62, 1973.D. Rhind, “Generalization and realism with automated cartographic system,” Canadian Cartographer , vol. 10, no. 1, pp. 51–62, 1973.M. Monmonier, “Displacement in vector-and raster-mode graphics,” Cartographica: The International Journal for Geographic Information and Geovisualization, vol. 24, no. 4, pp. 25–36, 1987.M. Monmonier, “Displacement in vector-and raster-mode graphics,” Cartographica: The International Journal for Geographic Information and Geovisualization, vol. 24, no. 4, pp. 25–36, 1987.P. M. Van Der Poorten and C. B. Jones, “Characterisation and Generalisation of Cartographic Lines Using Delaunay Triangulation,” International Journal of Geographical Information Science, vol. 16, no. 8, pp. 773–794, 2002.P. M. Van Der Poorten and C. B. Jones, “Characterisation and Generalisation of Cartographic Lines Using Delaunay Triangulation,” International Journal of Geographical Information Science, vol. 16, no. 8, pp. 773–794, 2002.Z. Li and S. Openshaw, “Algorithms for automated line generalization1 based on a natural principle of objective generalization,” International journal of geographical information systems, vol. 6, no. 5, pp. 373–389, 1992.Z. Li and S. Openshaw, “Algorithms for automated line generalization1 based on a natural principle of objective generalization,” International journal of geographical information systems, vol. 6, no. 5, pp. 373–389, 1992.P. Raposo, “Scale-specific automated line simplification by vertex clustering on a hexagonal tessellation,” Cartography and Geographic Information Science, vol. 40, no. 5, pp. 427–443, 2013.P. Raposo, “Scale-specific automated line simplification by vertex clustering on a hexagonal tessellation,” Cartography and Geographic Information Science, vol. 40, no. 5, pp. 427–443, 2013.L. Zhilin, Algorithmic Foundation of Multi-Scale Spatial Representation. Taylor & Francis Group, LLC, 2007.L. Zhilin, Algorithmic Foundation of Multi-Scale Spatial Representation. Taylor & Francis Group, LLC, 2007.Z. Zhao and A. Saalfeld, “Linear-time sleeve-fitting polyline simplification algorithms,” in Proceedings of AutoCarto, 1997, vol. 13, pp. 214–223.Z. Zhao and A. Saalfeld, “Linear-time sleeve-fitting polyline simplification algorithms,” in Proceedings of AutoCarto, 1997, vol. 13, pp. 214–223.M. Egenhofer and J. Herring, “Categorizing binary topological relations between regions, lines and points in geographic databases, the 9-intersection: Formalism and its Use for Naturallanguage Spatial Predicates,” Santa Barbara CA National Center for Geographic Information and Analysis Technical Report, vol. 94, pp. 1–28, 1990.M. Egenhofer and J. Herring, “Categorizing binary topological relations between regions, lines and points in geographic databases, the 9-intersection: Formalism and its Use for Naturallanguage Spatial Predicates,” Santa Barbara CA National Center for Geographic Information and Analysis Technical Report, vol. 94, pp. 1–28, 1990.V. G. Gorshkov, D. M. Murin, and O. P. Yakimova, “Research of models of topological relations of spatial objects,” Modelirovanie i Analiz Informatsionnykh Sistem, vol. 29, no. 3, pp. 154–165, 2022.V. G. Gorshkov, D. M. Murin, and O. P. Yakimova, “Research of models of topological relations of spatial objects,” Modelirovanie i Analiz Informatsionnykh Sistem, vol. 29, no. 3, pp. 154–165, 2022.M.-P. Dubuisson and A. K. Jain, “A modified Hausdorff distance for object matching,” in Proceedings of 12th international conference on pattern recognition, 1994, vol. 1, pp. 566–568.M.-P. Dubuisson and A. K. Jain, “A modified Hausdorff distance for object matching,” in Proceedings of 12th international conference on pattern recognition, 1994, vol. 1, pp. 566–568.

The authors declare that there are no conflicts of interest present.