EdgeCrack: A parallel divide-and-conquer algorithm for building a topological data structure

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

1 Citation (Scopus)

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 languageEnglish
Title of host publicationUrban and Regional Data Management
Subtitle of host publicationUDMS Annual 2013 - Proceedings of the Urban Data Management Society Symposium 2013
EditorsC. Ellul, S. Zlatanova, M. Rumor, R. Laurini
PublisherCRC Press
Pages107-116
Number of pages10
ISBN (Electronic)978-1-315-88523-0
ISBN (Print)978-1-138-00063-6
DOIs
Publication statusPublished - 2013
EventUrban Data Management Society Symposium 2013, UDMS Annual 2013 - London, United Kingdom
Duration: 29 May 201331 May 2013

Conference

ConferenceUrban Data Management Society Symposium 2013, UDMS Annual 2013
Abbreviated titleUBMS annual 2013
CountryUnited Kingdom
CityLondon
Period29/05/1331/05/13

Fingerprint Dive into the research topics of 'EdgeCrack: A parallel divide-and-conquer algorithm for building a topological data structure'. Together they form a unique fingerprint.

  • Cite this

    Meijers, M., & Ledoux, H. (2013). EdgeCrack: A parallel divide-and-conquer algorithm for building a topological data structure. In C. Ellul, S. Zlatanova, M. Rumor, & R. Laurini (Eds.), Urban and Regional Data Management: UDMS Annual 2013 - Proceedings of the Urban Data Management Society Symposium 2013 (pp. 107-116). CRC Press. https://doi.org/10.1201/b14914-14