Solving the horizontal conflation problem with a constrained Delaunay triangulation

Solving the horizontal conflation problem with a constrained Delaunay triangulation

Ledoux, H. (TU Delft Urban Data Science)
Arroyo Ohori, G.A.K. (TU Delft Urban Data Science)

2017

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.

Conflation
Edge-matching
Triangulation
Boundary alignment
Data quality

http://resolver.tudelft.nl/uuid:05a0144e-030c-4ab7-866f-c3dc1ec5e647

https://doi.org/10.1007/s10109-016-0237-7

1435-5930

Journal of Geographical Systems: geographical information, analysis, theory and decision, 19 (1), 21-42

Institutional Repository

journal article

© 2017 H. Ledoux, G.A.K. Arroyo Ohori