Geodesic
Joint simplification of various types spatial objects while preserving topological relationships
Modelirovanie i analiz informacionnyh sistem, Tome 30 (2023) no. 4, pp. 340-353.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Mots-clés : simplification algorithm, spatial data
Keywords: topological relationships, mesh data structure, consistent cartographic generalization. 
@article{MAIS_2023_30_4_a2,
     author = {O. P. Yakimova and D. M. Murin and V. G. Gorshkov},
     title = {Joint simplification of various types spatial objects while preserving topological relationships},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {340--353},
     publisher = {mathdoc},
     volume = {30},
     number = {4},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2023_30_4_a2/}
}
TY  - JOUR
AU  - O. P. Yakimova
AU  - D. M. Murin
AU  - V. G. Gorshkov
TI  - Joint simplification of various types spatial objects while preserving topological relationships
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2023
SP  - 340
EP  - 353
VL  - 30
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2023_30_4_a2/
LA  - ru
ID  - MAIS_2023_30_4_a2
ER  - 
%0 Journal Article
%A O. P. Yakimova
%A D. M. Murin
%A V. G. Gorshkov
%T Joint simplification of various types spatial objects while preserving topological relationships
%J Modelirovanie i analiz informacionnyh sistem
%D 2023
%P 340-353
%V 30
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2023_30_4_a2/
%G ru
%F MAIS_2023_30_4_a2
O. P. Yakimova; D. M. Murin; V. G. Gorshkov. Joint simplification of various types spatial objects while preserving topological relationships. Modelirovanie i analiz informacionnyh sistem, Tome 30 (2023) no. 4, pp. 340-353. http://geodesic.mathdoc.fr/item/MAIS_2023_30_4_a2/

[1] W. Tobler, Numerical map generalization, Department of Geography, University of Michigan, Ann Arbour, MI, USA, 1966, 78 pp.

[2] F. Topfer, W. Pillewizer, “The principles of selection”, Cartographic Journal, 3:1 (1966), 10–16 | DOI

[3] J. D. Perkal, “Proba obiektywnej generalizacji”, Geodezia I Kartografia, 7:2 (1958), 130–142 (in Polish)

[4] U. Ramer, “An iterative procedure for the polygonal approximation of plane curves”, Computer Graphics and Image Processing, 1:3 (1972), 244–256 | DOI

[5] D. H. Douglas, 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, 10:2 (1973), 112–122 | DOI

[6] J. S. Marino, “Identification of characteristic points along naturally occurring lines. An empirical study”, The Canadian cartographer Toronto, 16:1 (1979) | Zbl

[7] G. Dutton, “Scale, sinuosity, and point selection in digital line generalization”, Cartography and Geographic Information Science, 26:1 (1999), 33–54 | DOI | MR

[8] A. Chehreghan, R. Ali Abbaspour, “Estimation of empirical parameters in matching of linear vector datasets: An optimization approach”, Model. Earth Syst. Environ, 3 (2017), 1029-1043 | DOI

[9] A. Chehreghan, R. Ali Abbaspour, “A geometric-based approach for road matching on multi-scale datasets using a genetic algorithm”, Cartography and Geographic Information Science, 45:3 (2018), 255–269 | DOI

[10] R. A. Finkel, J. L. Bentley, “Quad trees a data structure for retrieval on composite keys”, Acta informatica, 4 (1974), 1–9 | DOI | Zbl

[11] A. Guttman, “R-trees: A dynamic index structure for spatial searching”, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, 1984, 47–57

[12] U. A. Kravchenko, Information geomodeling: The problem of data and knowledge representation, Abstract of the dissertation for the degree of Doctor of Technical Sciences, 2013 (In Russian)

[13] G. Dettori, E. Puppo, “How generalization interacts with the topological and metric structure of maps”, Proceedings of the 7th International Symposium on Spatial Data Handling, 1996, 559–570

[14] D. Rhind, “Generalization and realism with automated cartographic system”, Canadian Cartographer, 10:1 (1973), 51–62 | DOI

[15] M. Monmonier, “Displacement in vector-and raster-mode graphics”, Cartographica: The International Journal for Geographic Information and Geovisualization, 24:4 (1987), 25–36 | DOI

[16] P. M. Van Der Poorten, C. B. Jones, “Characterisation and generalisation of cartographic lines using delaunay triangulation”, International Journal of Geographical Information Science, 16:8 (2002), 773–794 | DOI

[17] Z. Li, S. Openshaw, “Algorithms for automated line generalization1 based on a natural principle of objective generalization”, International journal of geographical information systems, 6:5 (1992), 373–389 | DOI

[18] P. Raposo, “Scale-specific automated line simplification by vertex clustering on a hexagonal tessellation”, Cartography and Geographic Information Science, 40:5 (2013), 427–443 | DOI

[19] L. Zhilin, Algorithmic Foundation of Multi-Scale Spatial Representation, Taylor Francis Group, LLC, 2007, 282 pp.

[20] Z. Zhao, A. Saalfeld, “Linear-time sleeve-fitting polyline simplification algorithms”, Proceedings of AutoCarto, 13 (1997), 214–223

[21] M. Egenhofer, 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 No 94, 1990, 28 pp.

[22] V. G. Gorshkov, D. M. Murin, O. P. Yakimova, “Research of models of topological relations of spatial objects”, Modelirovanie i Analiz Informatsionnykh Sistem, 29:3 (2022), 154–165 (in Russian)

[23] M.-P. Dubuisson, A. K. Jain, “A modified Hausdorff distance for object matching”, Proceedings of 12th international conference on pattern recognition, v. 1, 1994, 566–568 | DOI