Solving the horizontal conflation problem with a constrained Delaunay triangulation

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)
10 Downloads (Pure)

Abstract

Datasets produced by different countries or organisations are seldom properly aligned and contain several discrepancies (e.g., gaps and overlaps). This problem has been so far almost exclusively tackled by snapping vertices based on a user-defined threshold. However, as we argue in this paper, this leads to invalid geometries, is error-prone, and leaves several discrepancies along the boundaries. We propose a novel algorithm to align the boundaries of adjacent datasets. It is based on a constrained Delaunay triangulation to identify and eliminate the discrepancies, and the alignment is performed without moving vertices with a snapping operator. This allows us to guarantee that the datasets have been properly conflated and that the polygons are geometrically valid. We present our algorithm, our implementation (based on the stable and fast triangulator in CGAL), and we show how it can be used it practice with different experiments with real-world datasets. Our experiments demonstrate that our approach is highly efficient and that it yields better results than snapping-based methods.
Original languageEnglish
Pages (from-to)21-42
JournalJournal of Geographical Systems: geographical information, analysis, theory and decision
Volume19
Issue number1
DOIs
Publication statusPublished - 2017

Keywords

  • Conflation
  • Edge-matching
  • Triangulation
  • Boundary alignment
  • Data quality

Fingerprint Dive into the research topics of 'Solving the horizontal conflation problem with a constrained Delaunay triangulation'. Together they form a unique fingerprint.

  • Cite this