Name
Abstract | ||
|---|---|---|
lthough the validation of a single GIS polygon can be considered as a solved issue, the repair of an invalid polygon has not received much attention and is still in practice a semi-manual and time-consuming task. We investigate in this paper algorithms to automatically repair a single polygon. Automated repair algorithms can be considered as interpreting ambiguous or ill-defined polygons and returning a coherent and clearly defined output (the definition of the international standards in our case). We present a novel approach, based on the use of a constrained triangulation, to automatically repair invalid polygons. Our approach is conceptually simple and easy to implement as it is mostly based on labelling triangles. It is also flexible: it permits us to implement different repair paradigms (we describe two in the paper). We have implemented our algorithms, and we report on experiments made with large real-world polygons that are often used by practitioners in different disciplines. We show that our approach is faster and more scalable than alternative tools. HighlightsThe repair of invalid polygons is still in practice a manual and time-consuming task.We investigate methods to automatically repair invalid polygons (according to the international standards).We propose a constrained triangulation-based approach, and show that in practice, with typical real-world polygons used by practitioners in disciplines related to the geosciences, it is fast, stable and scales to massive polygons.Our implementation is open-source and freely available under a GPL licence. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.cageo.2014.01.009 | Computers & Geosciences |
Keywords | Field | DocType |
Constrained triangulation,Repair,Validation,Quality of data | Data mining,Polygon,Computer science,Triangulation (social science),Scalability | Journal |
Volume | Issue | ISSN |
66 | C | 0098-3004 |
Citations | PageRank | References |
4 | 0.41 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hugo Ledoux | 1 | 231 | 22.27 |
| Ken Arroyo Ohori | 2 | 46 | 8.14 |
| Martijn Meijers | 3 | 43 | 4.80 |