EDGE-MATCHING POLYGONS WITH A CONSTRAINED TRIANGULATION
Hugo Ledoux, Ken Arroyo Ohori · 2011
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.