Edge-matching polygons with a constrained traingulation

Edge-matching polygons with a constrained traingulation

Ledoux, H.
Arroyo Ohori, K.

OTB Research Institute for the Built Environment

OTB Research

2011-01-23

While the edge-matching problem is usually tackled by snapping geometries within a certain threshold, we argue in this paper that this method is error-prone and often leads to geometries that are invalid. We present a novel edge-matching algorithm for polygons where vertices are not moved (no snapping is involved); instead gaps and overlaps between polygons are corrected by using a constrained triangulation as a supporting structure and assigning values to triangles. Our approach has three main benefits: (i) no user-defined tolerance needs to be defined, the matching is adaptative to the configuration of the polygons; (ii) we can control locally how the polygons should be matched to obtain different results; (iii) we guarantee that the resulting edge-matched polygons are valid (no self-intersection and no gaps/overlaps exist between polygons). We present in the paper our novel algorithm and our implementation, which is based on the stable and fast triangulator in CGAL. We also present some experiments we have made with some real-world cross-boundary datasets in Europe. Our experiments demonstrate that our implementation is highly efficient and permits us to avoid the tedious task of finding the optimal threshold for a dataset, for the polygons are properly edgematched and we can prove that no gaps/overlaps are left.

https://doi.org/10.4233/uuid:0a529efc-447f-448f-8bab-f3485746ed95

Technical University of Ostrava

978-80-248-2366-9

Proceedings Symposium GIS, Ostrava, Czech Republic, 23-26 January 2011

Institutional Repository

conference paper

(c) 2011 The Author(s)
Delft University of Technology