Совместное упрощение пространственных объектов различного типа с сохранением топологических отношений

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

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

2. F. Töpfer and W. Pillewizer, “The principles of selection,” Cartographic Journal, vol. 3, no. 1, pp. 10–16, 1966.

3. J. D. Perkal, “Proba obiektywnej generalizacji,” Geodezia I Kartografia, vol. 7, no. 2, pp. 130–142, 1958.

4. 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.

5. 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.

6. J. S. Marino, “Identification of characteristic points along naturally occurring lines. an empirical study,” The Canadian cartographer Toronto, vol. 16, no. 1, 1979.

7. G. Dutton, “Scale, sinuosity, and point selection in digital line generalization,” Cartography and Geographic Information Science, vol. 26, no. 1, pp. 33–54, 1999.

8. 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.

9. 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.

10. 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.

11. 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.

12. U. A. Kravchenko, “Information geomodeling: the problem of data and knowledge representation.” 2013.

13. 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.

14. D. Rhind, “Generalization and realism with automated cartographic system,” Canadian Cartographer , vol. 10, no. 1, pp. 51–62, 1973.

15. 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.

16. 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.

17. 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.

18. 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.

19. L. Zhilin, Algorithmic Foundation of Multi-Scale Spatial Representation. Taylor & Francis Group, LLC, 2007.

20. Z. Zhao and A. Saalfeld, “Linear-time sleeve-fitting polyline simplification algorithms,” in Proceedings of AutoCarto, 1997, vol. 13, pp. 214–223.

21. 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.

22. 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.

23. 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.