A Matching Algorithm Based on Voronoi Diagram for Multi-Scale Polygonal Residential Areas
Matching spatial entities (e.g., polygonal residential areas) from sources of significantly different map scales is challenging. The reason is that the same entities in two map scales have significant variations in their positions, structure shapes and numbers, and topological relationships. Traditi...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2018-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8258984/ |
| _version_ | 1819163236108337152 |
|---|---|
| author | Jianhua Wu Yangyang Wan Yao-Yi Chiang Zhongliang Fu Min Deng |
| author_facet | Jianhua Wu Yangyang Wan Yao-Yi Chiang Zhongliang Fu Min Deng |
| author_sort | Jianhua Wu |
| collection | DOAJ |
| description | Matching spatial entities (e.g., polygonal residential areas) from sources of significantly different map scales is challenging. The reason is that the same entities in two map scales have significant variations in their positions, structure shapes and numbers, and topological relationships. Traditional matching methods based on minimum boundary rectangles (MBRs) or buffers usually lead to missed matches or mismatching. Furthermore, most of the previous approaches on entity similarity calculation are designed for datasets with specified map scales, which cannot directly apply to another set of dataset with a different scale. In this paper, we present a general approach using the Voronoi diagram for spatial entity matching on multi-scale datasets. Our approach first employs an efficient algorithm to construct the Voronoi diagram from the small-scale dataset. Next, the approach traverses each Voronoi polygon to find the corresponding large-scale features as the matching candidates (for each small-scale feature). Using the Voronoi diagram for identifying matching candidates does not require a manually determined search space (in contrast to the buffer-based approach). Also, our algorithm effectively uses the Voronoi diagram to prune the number of matching candidates even when the sources for matching contain large inconsistent position deviations. Finally, our approach utilizes three similarity indexes, namely, the convex hull shape similarity, convex hull area similarity, and overlapping area ratio to confirm the final matching results. We conducted experiments on two sets of datasets of two cities in China. The scales of the tested datasets were 1:10 000 and 1:50 000 and 1:1000 and 1:10 000. We compared our Voronoi-based method to both the MBR and buffer-based methods. The experiments showed that our method outperformed both the previous methods in generality and quality. Specifically, for the datasets where the inconsistent position deviations were large (i.e., the datasets of 1:1000 and 1:10 000 scales), the average F-measure of our results were 12.46%, 20.8%, and 64.45% higher than the MBR-based, 6-m buffer-based, and 3-m buffer-based methods, respectively. |
| first_indexed | 2024-12-22T17:40:55Z |
| format | Article |
| id | doaj.art-f9f0c57f1cec44399487cc6cb80f6947 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-22T17:40:55Z |
| publishDate | 2018-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-f9f0c57f1cec44399487cc6cb80f69472022-12-21T18:18:25ZengIEEEIEEE Access2169-35362018-01-0164904491510.1109/ACCESS.2018.27933028258984A Matching Algorithm Based on Voronoi Diagram for Multi-Scale Polygonal Residential AreasJianhua Wu0https://orcid.org/0000-0002-2600-6916Yangyang Wan1Yao-Yi Chiang2Zhongliang Fu3Min Deng4School of Geosciences and Info-Physics, Central South University, Changsha, ChinaSchool of Geography and Environment, Jiangxi Normal University, Nanchang, ChinaSpatial Sciences Institute, University of Southern California, Los Angeles, CA, USASchool of Remote Sensing and Information Engineering, Wuhan University, Wuhan, ChinaSchool of Geosciences and Info-Physics, Central South University, Changsha, ChinaMatching spatial entities (e.g., polygonal residential areas) from sources of significantly different map scales is challenging. The reason is that the same entities in two map scales have significant variations in their positions, structure shapes and numbers, and topological relationships. Traditional matching methods based on minimum boundary rectangles (MBRs) or buffers usually lead to missed matches or mismatching. Furthermore, most of the previous approaches on entity similarity calculation are designed for datasets with specified map scales, which cannot directly apply to another set of dataset with a different scale. In this paper, we present a general approach using the Voronoi diagram for spatial entity matching on multi-scale datasets. Our approach first employs an efficient algorithm to construct the Voronoi diagram from the small-scale dataset. Next, the approach traverses each Voronoi polygon to find the corresponding large-scale features as the matching candidates (for each small-scale feature). Using the Voronoi diagram for identifying matching candidates does not require a manually determined search space (in contrast to the buffer-based approach). Also, our algorithm effectively uses the Voronoi diagram to prune the number of matching candidates even when the sources for matching contain large inconsistent position deviations. Finally, our approach utilizes three similarity indexes, namely, the convex hull shape similarity, convex hull area similarity, and overlapping area ratio to confirm the final matching results. We conducted experiments on two sets of datasets of two cities in China. The scales of the tested datasets were 1:10 000 and 1:50 000 and 1:1000 and 1:10 000. We compared our Voronoi-based method to both the MBR and buffer-based methods. The experiments showed that our method outperformed both the previous methods in generality and quality. Specifically, for the datasets where the inconsistent position deviations were large (i.e., the datasets of 1:1000 and 1:10 000 scales), the average F-measure of our results were 12.46%, 20.8%, and 64.45% higher than the MBR-based, 6-m buffer-based, and 3-m buffer-based methods, respectively.https://ieeexplore.ieee.org/document/8258984/Shape similarityentity matchingVoronoi diagrammulti-scaledata conflation |
| spellingShingle | Jianhua Wu Yangyang Wan Yao-Yi Chiang Zhongliang Fu Min Deng A Matching Algorithm Based on Voronoi Diagram for Multi-Scale Polygonal Residential Areas IEEE Access Shape similarity entity matching Voronoi diagram multi-scale data conflation |
| title | A Matching Algorithm Based on Voronoi Diagram for Multi-Scale Polygonal Residential Areas |
| title_full | A Matching Algorithm Based on Voronoi Diagram for Multi-Scale Polygonal Residential Areas |
| title_fullStr | A Matching Algorithm Based on Voronoi Diagram for Multi-Scale Polygonal Residential Areas |
| title_full_unstemmed | A Matching Algorithm Based on Voronoi Diagram for Multi-Scale Polygonal Residential Areas |
| title_short | A Matching Algorithm Based on Voronoi Diagram for Multi-Scale Polygonal Residential Areas |
| title_sort | matching algorithm based on voronoi diagram for multi scale polygonal residential areas |
| topic | Shape similarity entity matching Voronoi diagram multi-scale data conflation |
| url | https://ieeexplore.ieee.org/document/8258984/ |
| work_keys_str_mv | AT jianhuawu amatchingalgorithmbasedonvoronoidiagramformultiscalepolygonalresidentialareas AT yangyangwan amatchingalgorithmbasedonvoronoidiagramformultiscalepolygonalresidentialareas AT yaoyichiang amatchingalgorithmbasedonvoronoidiagramformultiscalepolygonalresidentialareas AT zhongliangfu amatchingalgorithmbasedonvoronoidiagramformultiscalepolygonalresidentialareas AT mindeng amatchingalgorithmbasedonvoronoidiagramformultiscalepolygonalresidentialareas AT jianhuawu matchingalgorithmbasedonvoronoidiagramformultiscalepolygonalresidentialareas AT yangyangwan matchingalgorithmbasedonvoronoidiagramformultiscalepolygonalresidentialareas AT yaoyichiang matchingalgorithmbasedonvoronoidiagramformultiscalepolygonalresidentialareas AT zhongliangfu matchingalgorithmbasedonvoronoidiagramformultiscalepolygonalresidentialareas AT mindeng matchingalgorithmbasedonvoronoidiagramformultiscalepolygonalresidentialareas |