Skip to main content

Validation and Automatic Repair of Planar Partitions Using a Constrained Triangulation Validierung und automatische Korrektur von planaren Graphen unter Benutzung von bedingter Triangulation

Buy Article:

$39.00 plus tax (Refund Policy)

Abstract:

Planar partitions are frequently used to model, among others, land cover, cadastral parcels and administrative boundaries. In practice, they are often stored as a set of individual polygons to which attributes are attached, e.g. with the paradigm, causing different errors and inconsistencies, e.g. gaps, overlaps and disconnected polygons, which are introduced during their creation, manipulation and exchange. These errors severely hamper the use of planar partitions in other software, e.g. due to false assumptions causing erroneous calculations. Existing approaches to validate planar partitions involve first building a planar graph of the polygons and enforcing constraints, then repair is done by snapping vertices and edges of this graph. We argue that these approaches have many shortcomings in terms of complexity, numerical robustness and difficulty of implementation, and do not guarantee valid results. Furthermore, they are semi-automatic, requiring manual user intervention. We propose in this paper a novel method to validate and repair planar partitions. It uses a constrained triangulation of the polygons as a base – which by definition is a planar partition – and only simple operations are needed, i.e., labelling of triangles, to both validate and repair. Perhaps the biggest advantage of our method is that we can guarantee that a planar partition is valid after repair. In the paper we describe the details of our method, our implementation, and the experiments we have done with real-world datasets. We show that our implementation scales to big datasets and that it offers better capabilities and overall performance than existing solutions.

German
Planare Graphen werden neben anderen Methoden oft für die Modellierung von Landnutzung, Kataster und Verwaltungsgrenzen verwendet. In der praktischen Anwendung werden die Flächeneinheiten oft als selbstständige Polygone, denen Attribute zugeordnet sind, gespeichert, z.B. als Simple Features. Die Anwendung dieser Methode verursacht oft Inkonsistenzen, z.B. Lücken, Überlappungen und nicht verbundene Polygone. Diese Fehler behindern die Weiterverarbeitung der Flächenaufteilung in anderen Anwendungen, z.B. wenn falsche Annahmen den Folgeberechnungen zu Grunde gelegt werden müssen. Existierende Verfahren zur Validierung von planaren Graphen nutzen oft einen bedingten planaren Graphen. Die Korrektur wird dann durch Snapping auf Knoten und Kanten des Graphen durchgeführt. Wir sind der Meinung, dass dieses Verfahren Nachteile bezüglich Komplexität, numerischer Stabilität und Implementierung hat. Vor allem kann ein richtiges Ergebnis nicht garantiert werden. Darüber hinaus sind die Algorithmen oft nur halbautomatisch. Daher schlagen wir in diesem Artikel ein neues Verfahren zur Validierung und automatischen Korrektur von planaren Graphen vor. Es beginnt mit einer bedingten Triangulation der gegebenen Polygone, die per De nition ein pla narer Graph ist. Danach sind nur einfache Operationen zur Beschreibung der Dreiecke, zur Validierung und zur Korrektur erforderlich. Wahrscheinlich ist der größte Vorteil unserer Methode, dass eine gültige Raumaufteilung im Ergebnis garantiert wird. Im Artikel beschreiben wir unsere Methode, die Implementierung und die Anwendung auf reale Datensätze. Wir zeigen, dass unsere Methode auch für große Datensätze geeignet und sogar leistungsfähiger als andere Methoden ist.

Keywords: PLANAR PARTITION; POLYGONAL COVERAGE; REPAIR; TOPOLOGICAL DATA STRUCTURE; TRIANGULATION

Document Type: Research Article

DOI: https://doi.org/10.1127/1432-8364/2012/0143

Publication date: 2012-10-01

More about this publication?
  • Photogrammetrie - Fernerkundung - Geoinformation (PFG) is an international scholarly journal covering the progress and application of photogrammetric methods, remote sensing technology and the intricately connected field of geoinformation processing.

    Papers published in PFG highlight new developments and applications of these technologies in practice. The journal hence addresses both researchers and student of these disciplines at academic institutions and universities and the downstream users in both the private sector and public administration.

    PFG places special editorial emphasis on the communication of new methodologies in data acquisition, new approaches to optimized processing and interpretation of all types of data which were acquired by photogrammetric methods, remote sensing, image processing and the computer-aided interpretation of such data in general.

    PFG is the official journal of the German Society of Photogrammetry and Remote Sensing.
  • Editorial Board
  • Information for Authors
  • Subscribe to this Title
  • Ingenta Connect is not responsible for the content or availability of external websites
  • Access Key
  • Free ContentFree content
  • Partial Free ContentPartial Free content
  • New ContentNew content
  • Open Access ContentOpen access content
  • Partial Open Access ContentPartial Open access content
  • Subscribed ContentSubscribed content
  • Partial Subscribed ContentPartial Subscribed content
  • Free Trial ContentFree trial content
Cookie Policy
X
Cookie Policy
Ingenta Connect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more