Print Email Facebook Twitter Validation and Automatic Repair of Planar Partitions using a Constrained Triangulation Title Validation and Automatic Repair of Planar Partitions using a Constrained Triangulation Author Arroyo Ohori, G.A.K. Contributor Van Oosterom, P.J.M. (mentor) Ledoux, H. (mentor) Meijers, B.M. (mentor) Department GIS technology Programme Geomatics Date 2010-08-27 Abstract Planar partitions (subdivisions of the plane into polygonal areas) constitute one of the most important data representations in GIS. They are used to model concepts as varied as land use, administrative units, natural features and cadastral parcels, among many others. However, since polygons are often stored separately, different errors and inconsistencies are introduced during their creation, manipulation (both manual and automatic) and exchange. These come in the form of invalid polygons, gaps, overlaps and disconnected polygons, which severely hampers their use in other software. Existing approaches to solve this problem usually involve polygon repair using a list of constraints, and complex planar partition repair operations performed on a planar graph. However, these have many shortcomings in terms of complexity, numerical robustness and difficulty of implementation. Moreover, they leave many invalid cases untouched. To solve this problem, a novel method to validate and automatically repair planar partitions has been developed. It uses a constrained triangulation of the polygons as a base, which being by definition a planar partition, means that only relatively simple operations are needed to ensure that the output becomes valid. Point locations are maintained throughout the process, while fully automatic repair is possible using customisable criteria. This approach is also extensible to individual polygons, is capable of handling a larger variety of cases and has good performance compared to existing alternatives; all of this with numerical robustness and maintaining topological consistency throughout. In order to analyse, test and improve the developed algorithms, and encourage further development, a fast and efficient implementation has been written in C++, which has been tested with several large data sets and compared with other available software, regarding both performance and functionality. This prototype is able to successfully repair planar partitions of more than 100,000 polygons. It is also open source and freely available on the GDMC website (http://www.gdmc.nl/). Subject planar partitionspolygonal coveragestopologyvalidationautomatic repairsimple featuresconstrained delaunay triangulation To reference this document use: http://resolver.tudelft.nl/uuid:78807acb-4115-478c-93de-68b9db884c8e Embargo date 2010-08-27 Part of collection Student theses Document type master thesis Rights (c) 2010 Arroyo Ohori, G.A.K. Files PDF thesis.pdf 7.02 MB Close viewer /islandora/object/uuid:78807acb-4115-478c-93de-68b9db884c8e/datastream/OBJ/view