Zwei Polygone sind benachbart wenn sie gemeinsame Kantensegmente teilen („Kanten-
Nachbarschaft“) oder wenn sie gemeinsame Punkte auf einer Kante besitzen („Punkt-
Nachbarschaft“) oder wenn sie sich gar nicht berühren, sondern in einer gewissen Nähe zueinander liegen („lose Nachbarschaft“). Die vorliegende Arbeit beschäftigt sich mit
Verfahren zur Auffindung dieser drei Arten von Nachbarschaftsbeziehungen in Mengen
von planaren, nicht-konvexen sich nicht-überschneidenden Polygonen. Nach der Vorstellung
eines bereits bekannten Algorithmus zur „Kanten-Nachbarschaft“-Suche werden im
Hauptteil der Arbeit die beiden Algorithmen zur Auffindung der „Punkt-Nachbarschaft“
und der „losen Nachbarschaft“ entwickelt. Im worst case liegt die Zeitkomplexität dieser
beiden Algorithmen in O(m²) (wobei m die Gesamtanzahl aller Kanten bzw. Eckpunkte
ist). Eine Sortierung aller Eckpunkte nach der x-Koordinate und eine anschließende, effiziente Vorauswahl führen in der Praxis jedoch zu einem vielfachen Speedup der
Laufzeiten (im Vergleich zu einer rein quadratischen Zeitkomplexität). Durch die Tatsache,
dass die beiden Algorithmen hochgradig parallelisierbar sind, kann ein weiterer
Speedup erreicht werden. Diese Möglichkeit wird zum Schluss der Arbeit diskutiert.
Inhaltsverzeichnis
1 Einleitung
2 Grundlagen
2.1 Definitionen
2.2 Verwendete Formelzeichen
3 Stand der Technik
3.1 Algorithmus: Kanten-Nachbarschaft
4 Algorithmen
4.1 Überlegungen zur Darstellung von Geraden
4.2 Algorithmus 1: Punkt-Nachbarschaft
4.3 Algorithmus 2: Lose Nachbarschaft
4.4 Alternative Auffasungen der losen Nachbarschaft
5 Untersuchungen zur Parallelisierbarkeit
5.1 Parallelisierung des Hauptteils
5.2 Parallelisierung der Vorausberechnung
6 Bewertung und Vergleich
6.1 Benchmarks
6.2 Auswertung
Zielsetzung & Themen
Die Arbeit untersucht effiziente Methoden zur Erkennung von Nachbarschaftsbeziehungen in Mengen von planaren, nicht-konvexen und nicht-überschneidenden Polygonen, mit dem Ziel, die im Vergleich zu rein quadratischen Ansätzen hohen Laufzeiten zu optimieren und Algorithmen parallelisierbar zu gestalten.
- Grundlagen topologischer Beziehungen in Geoinformationssystemen (GIS)
- Entwicklung von Algorithmen zur Kanten-, Punkt- und losen Nachbarschaft
- Optimierung der Suchprozesse durch Sortierverfahren und Intervall-Einschränkungen
- Strategien zur Parallelisierung der Algorithmen zur Performance-Steigerung
- Empirische Evaluation und Benchmarking der implementierten Lösungsansätze
Auszug aus dem Buch
4.2 Algorithmus 1: Punkt-Nachbarschaft
Der im letzten Kapitel erwähnte Algorithmus zur Bestimmung der Kanten-Nachbarschaft erreicht seine relativ geringe Komplexität im Wesentlichen durch die Ausnutzung der Tatsache, dass Kanten von benachbarten Polygonen auf derselben Geraden liegen. Dies ermöglicht mit Hilfe der Sortierung die Aufteilung der ganzen Menge der Kanten in Teilmengen, was letztendlich zur Reduzierung der Komplexität führt.
Im Falle der Punkt-Nachbarschaft lässt sich keine ähnliche Beobachtung finden. Ein Punkt, der auf einer Kante liegt, hat mit dieser Kante keine Parameter in dem Sinne gemeinsam, dass der Punkt keine Steigung und keinen y-Achsenabschnitt hat. Es lassen sich auch keine weiteren, irgendwie gearteten „Gemeinsamkeiten“ finden, die zur Reduktion der Komplexität beitragen könnten. Aus diesem Grunde wird sich kein ähnlich effizienter Algorithmus finden lassen. Ein Ziel dieser Arbeit ist es aber einen Algorithmus zu entwickeln, der den in der Praxis zu betrachtenden Polygonzahlen (n ≤ 100000) akzeptable Verarbeitungszeiten liefert.
Zusammenfassung der Kapitel
1 Einleitung: Diese Einleitung führt in die Bedeutung der Extraktion topologischer Beziehungen in Geoinformationssystemen ein und stellt die Zielsetzung der Arbeit sowie den Aufbau der nachfolgenden Kapitel vor.
2 Grundlagen: Hier werden zentrale Definitionen für Polygone, Planarität, Konvexität sowie die verschiedenen Arten der Nachbarschaft (Kanten-, Punkt- und lose Nachbarschaft) eingeführt.
3 Stand der Technik: Dieses Kapitel erläutert einen bestehenden Ansatz für die Kanten-Nachbarschaft und diskutiert dessen theoretische Grundlagen sowie die Komplexität.
4 Algorithmen: Es werden spezifische Algorithmen für Punkt- und lose Nachbarschaft entwickelt und deren Implementierung sowie mathematische Grundlagen im Detail dargelegt.
5 Untersuchungen zur Parallelisierbarkeit: Dieser Abschnitt befasst sich mit der Aufteilung der Algorithmen in unabhängige Prozesse, um durch Parallelisierung die Gesamtlaufzeit zu verkürzen.
6 Bewertung und Vergleich: Das abschließende Kapitel dokumentiert die durchgeführten Benchmarks unter Windows XP und wertet die Performance der entwickelten Algorithmen im Vergleich zu quadratischen Verfahren aus.
Schlüsselwörter
Polygon, Nachbarschaftssuche, Geoinformationssysteme, Kanten-Nachbarschaft, Punkt-Nachbarschaft, lose Nachbarschaft, Parallelisierung, Algorithmen, Laufzeitkomplexität, GIS, Computergraphik, Object Aligned Bounding Box, Benchmarking, Performance-Optimierung, Datenstrukturen
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit beschäftigt sich mit der algorithmischen Lösung, Nachbarschaftsbeziehungen zwischen Polygonen in Geoinformationssystemen effizient zu ermitteln.
Was sind die zentralen Themenfelder?
Die zentralen Themen umfassen die Definition topologischer Beziehungen, die Entwicklung spezialisierter Suchalgorithmen für verschiedene Nachbarschaftstypen und deren Performancemessung.
Was ist das primäre Ziel der Untersuchung?
Das Ziel ist die Entwicklung von Algorithmen, die Nachbarschaftsprobleme bei großen Polygonmengen effizienter als durch rein quadratische Ansätze lösen und parallel ausgeführt werden können.
Welche wissenschaftlichen Methoden werden verwendet?
Neben der theoretischen Herleitung werden algorithmische Verfahren entwickelt, mathematisch optimiert (z.B. durch Intervall-Einschränkungen) und in einer Testumgebung empirisch mittels Benchmarks validiert.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil widmet sich der detaillierten Beschreibung der Algorithmen für Punkt- und lose Nachbarschaft sowie Strategien zu deren Parallelisierung.
Durch welche Schlüsselwörter lässt sich die Arbeit charakterisieren?
Die Arbeit lässt sich primär durch Begriffe wie Nachbarschaftssuche, Polygon, Parallelisierung und Laufzeitkomplexität beschreiben.
Wie unterscheidet sich die „lose Nachbarschaft“ von anderen Formen?
Die lose Nachbarschaft betrachtet auch Polygone als benachbart, wenn sie sich nicht berühren, aber innerhalb einer bestimmten Distanz zueinander liegen, was über die Ausdehnung einer Bounding Box definiert wird.
Warum ist die Parallelisierung für die Arbeit relevant?
Die Parallelisierung ist entscheidend, um bei sehr großen Datenmengen von bis zu 100.000 Polygonen akzeptable Antwortzeiten zu erreichen, da die Aufgaben in unabhängige Teilmengen zerlegt werden können.
Welches Fazit ziehen die Benchmarks zur Effizienz?
Die Benchmarks zeigen, dass die entwickelten Algorithmen eine signifikante Beschleunigung gegenüber naiven, rein quadratischen Ansätzen ermöglichen und somit in der Praxis für komplexe GIS-Daten einsetzbar sind.
- Quote paper
- Konstantin Sokolov (Author), 2010, Nachbarschaftssuche in Mengen von planaren, nicht-konvexen, nicht-überschneidenden Polygonen, Munich, GRIN Verlag, https://www.grin.com/document/146775
