Lade Inhalt...

Repräsentation konvexer Objekte durch lineare Constraints in Geoinformationssystemen

Diplomarbeit 1997 95 Seiten

Informatik - Theoretische Informatik

Zusammenfassung

Inhaltsangabe:Gang der Untersuchung:
Wie aus der Mathematik bekannt ist, können konvexe Objekte jeder Dimension mit Hilfe linearer Ungleichungen spezifiziert werden (Constraint Repräsentation). Diese linearen Constraints können z.B. aus der sogenannten Boundary Representation, die ein Objekt anhand seiner Eckpunkte und Kanten charakterisiert, gewonnen werden.
Ein Ziel der Arbeit ist die effiziente Herleitung der Eckpunkte und Kanten zwei- bzw. dreidimensionaler Objekte, die durch die Constraint Repräsentation dargestellt werden, um diese Objekte visualisieren zu können. Das verwendete Verfahren basiert auf dem SIMPLEX-Algorithmus: der Breadth-First SIMPLEX.
Im zweiten Teil werden die Möglichkeiten betrachtet, die die Constraint Repräsentation im Zusammenhang mit dem SIMPLEX-Verfahren bietet, wenn zwei Objekte geschnitten werden. Als Seiteneffekt werden zum einen die geometrische Lage der Objekte zueinander bzgl. topologischer Relationen nach Egenhofer und zum anderen die durch den Schnitt redundanten Ungleichungen ermittelt.
Schließlich wird ein Algorithmus vorgestellt, der ein konkaves Polygon in mehrere disjunkte, konvexe Objektteile partitioniert. Somit kann über die Constraintrepräsentation festgestellt werden, ob sich ein beliebiger Punkt in oder außerhalb eines konkaven Polygons oder, in der Praxis, einer Landkarte befindet.

Inhaltsverzeichnis:Inhaltsverzeichnis:
1.Einleitung1
2.Definitionen und Werkzeuge4
2.1Boundary-Repräsentation4
2.2Constraint-Repräsentation5
2.3SIMPLEX-Algorithmus7
2.3.1Tableau-Methode8
2.3.2Zusammenhang der SIMPLEX-Tableauschritte und des Gaußschen Eliminationsverfahrens14
2.3.3Künstliche Variablen16
2.4Constraint Solver21
3.Berechnung von Constraint- und Boundary-Repräsentatiom22
3.1Transformation Boundary- nach Constraint-Repräsentation22
3.1.1Zweidimensionale Objekte22
3.1.2Dreidimensionale Objekte25
3.2Transformation Constraint- nach Boundary-Repräsentation27
3.2.1Brute Force27
3.2.2Breadth-First SIMPLEX30
3.2.2.1Redundante Constraints36
3.2.2.2Entartete Eckpunkte41
3.2.2.3Vollständigkeit des Breadth-First SIMPLEX54
4.Operationen auf Objekten in Constraint Repräsentation56
4.1Durchschnitt56
4.2Vereinigung59
4.3Topologische Relationen60
4.3.1Relation „Disjoint“64
4.3.2Relation „Contains“ und „Inside“65
4.3.3Relation „Equal“65
4.3.4Relation „Overlap“66
4.3.5Relation „Covers” und „CoveredBy“66
4.3.6Relation „Meet“69
5.Constraint-Repräsentation und konkave Objekte72
5.1Zerlegung […]

Details

Seiten
95
Erscheinungsform
Originalausgabe
Jahr
1997
ISBN (eBook)
9783832404802
Dateigröße
3.8 MB
Sprache
Deutsch
Katalognummer
v216443
Institution / Hochschule
Rheinische Friedrich-Wilhelms-Universität Bonn – Unbekannt
Note
Schlagworte
constraint databases boundary representation

Autor

Teilen

Zurück

Titel: Repräsentation konvexer Objekte durch lineare Constraints in Geoinformationssystemen