Abstract
In this paper we consider the problem of converting a large database of 2D polygons into a topological data structure (a data structure with nodes, edges and faces). We present EdgeCrack, an algorithm to obtain the topological data structure (which is based on a known algorithm for segment intersection) and performs small geometric corrections of the input by snapping to avoid problems. We further show how we have extended this algorithm to a Divide-and-Conquer approach, which is also suited for parallel processing. We present experimental results based on our implementation and show that we have been able to convert a large database of 5.3 millions polygons into a topological data structure.
Original language | English |
---|---|
Title of host publication | Urban and Regional Data Management |
Subtitle of host publication | UDMS Annual 2013 - Proceedings of the Urban Data Management Society Symposium 2013 |
Editors | C. Ellul, S. Zlatanova, M. Rumor, R. Laurini |
Publisher | CRC Press |
Pages | 107-116 |
Number of pages | 10 |
ISBN (Electronic) | 978-1-315-88523-0 |
ISBN (Print) | 978-1-138-00063-6 |
DOIs | |
Publication status | Published - 2013 |
Event | Urban Data Management Society Symposium 2013, UDMS Annual 2013 - London, United Kingdom Duration: 29 May 2013 → 31 May 2013 |
Conference
Conference | Urban Data Management Society Symposium 2013, UDMS Annual 2013 |
---|---|
Abbreviated title | UBMS annual 2013 |
Country/Territory | United Kingdom |
City | London |
Period | 29/05/13 → 31/05/13 |