Measuring the similarity between multipolygons using convex hulls and position graphs

ABSTRACT

Polygon similarity can play an important role in geographic information retrieval, map matching and updating, and spatial data mining applications. Geographic information science (GIS) represents various spatial objects as polygons, including simple polygons and polygons with holes, as well as multipolygons. Spatial objects of multipolygons possess complex structure which makes it difficult to assess their similarity. This study develops a method based on convex hulls and position graphs to measure the similarity between multipolygons. The proposed method first finds correspondences between subpolygons in the two multipolygons based on a control polygon. Thereafter, the method constructs a position graph to denote the distribution of these subpolygons and applies a turning function to compute the similarity between various graphs. Fourier transformation and moment invariants were combined to characterize the different matching relationships among subpolygons. The experiments involve three different kinds multipolygons to verify the effectiveness and robustness of proposed method. The experiments show that this approach effectively measures similarity between multipolygons. Moreover, the proposed method accounts for the relationships across the entire complex geometrical shape and components of multipolygon during measuring similarity.

KEYWORDS:

• Geometric similarity
• multipolygon
• position graph
• Fourier transform
• moment invariant

Acknowledgments

We would like to thank the editor, Prof. May Yuan, and the anonymous reviewers for their insightful comments and feedbacks, especially during the Covid-19 pandemic.

Data and codes availability statement

The data and codes that support the findings of this study are available at figshare.com: http://doi.org/10.6084/m9.figshare.11439951.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This study was funded by the National Natural Science Foundation of China [41671400]; National Key Research and Development Program of China [Nos. 2018YFB0505500, 2018YFB0505504] and Key Laboratory of Geological Survey and Evaluation of Ministry of Education [GLAB2020ZR05].

Notes on contributors

Yongyang Xu

Yongyang Xu, received the B.Sc. degrees in computer science and technology from China University of Geosciences (Wuhan), in 2014, and the Ph.D. degree in geographic information engineering from China University of Geosciences (Wuhan), in 2019. He is currently an associate professor in School of Geography and Information Engineering, China University of Geosciences (Wuhan). His main interests include deep learning, vector data rendering and processing, spatial analysis.

Zhong Xie

Zhong Xie, received B.E, M.E and PH.D degrees in the China University of Geosciences, Wuhan, China, in respectively 1990, 1998 and 2002. Now, he is a professor School of Geography and Information Engineering, China University of Geosciences. His research interests are spatial analysis, 3D rebuilding and image processing.

Zhanlong Chen

Zhanlong Chen, received his master’s degree in Geodesy and Surveying Engineering from Kunming University of Science and Technology, China, in 2006, and PhD in Cartography and Geographic Information Engineering from China University of Geosciences, China, in 2009. He is currently a professor in the School of Geography and Information Engineering, China University of Geosciences, China. His research interests include spatial representation, spatial analysis and query, spatial cognition and spatial reasoning.

Mingyu Xie

Mingyu Xie is currently an undergraduate in computer science from University of California, Santa Barbara in America. His research interests include quantum computing and machine learning.