Nachbarschaftssuche in Mengen von planaren, nicht-konvexen, nicht-überschneidenden Polygonen

Inhaltsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

1 Einleitung

2 Grundlagen
2.1 De nitionen
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 Au asungen 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

Literaturverzeichnis

Abstract

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 Au ndung dieser drei Arten von Nachbarschaftsbeziehungen in Mengen von planaren, nicht-konvexen sich nicht-überschneidenden Polygonen. Nach der Vorstel- lung eines bereits bekannten Algorithmus zur Kanten-Nachbarschaft -Suche werden im Hauptteil der Arbeit die beiden Algorithmen zur Au ndung der Punkt-Nachbarschaft und der losen Nachbarschaft entwickelt. Im worst case liegt die Zeitkomplexität dieser beiden Algorithmen in O(m² ges)(wobeimges die Gesamtanzahl aller Kanten bzw. Eck- punkte ist). Eine Sortierung aller Eckpunkte nach der x-Koordinate und eine anschlie- ÿende, e ziente Vorauswahl führen in der Praxis jedoch zu einem vielfachen Speedup der Laufzeiten (im Vergleich zu einer rein quadratischen Zeitkomplexität). Durch die Tat- sache, dass die beiden Algorithmen hochgradig parallelisierbar sind, kann ein weiterer Speedup erreicht werden. Diese Möglichkeit wird zum Schluss der Arbeit diskutiert.

Abbildungsverzeichnis

2.1 Konvexe und konkave Polygone, Kanten- und Punkt-Nachbarschaft

2.2 Lose Nachbarschaft

4.1 Punkt-Nachbarschaft; zwei Fälle

4.2 Einschränkung des Suchbereiches durch das x-Intervall

4.3 Sortierte Punktmenge

4.4 OBB und ABB

4.5 Berechnung der Object Aligned Bounding Box

4.6 Problemfälle bei der Bestimmung der losen Nachbarschaft

6.1 Punkt-Nachbarschaft: 1.000 Polygone

6.2 Punkt Nachbarschaft: 10.000 Polygone

6.3 Punkt Nachbarschaft: 100.000 Polygone

6.4 Lose Nachbarschaft: 1.000 Polygone

6.5 Lose Nachbarschaft: 10.000 Polygone

6.6 Lose Nachbarschaft: 100.000 Polygone

Tabellenverzeichnis

6.1 mittlere Kantenanzahl und Mittlere Laufzeit der drei Testfelder

6.2 Punkt-Nachbarschaft: Speedup gegenüber rein quadratischer Zeit

6.3 lose Nachbarschaft: Speedup gegenüber rein quadratischer Zeit

1 Einleitung

Die Gewinnung von nützlicher, struktureller Information, aus eingangs unstrukturierten Rohdaten, ist ein zentraler Aspekt in Geoinformationssystemen (GIS). Neben räumli- cher (topogra scher) Information nimmt die Extraktion und Darstellung von topologi- schen Beziehungen zwischen Geoobjekten (z.B. Flächen) eine wichtige Stellung ein (vgl. [Röo98] Topologische Beziehungen in Geo-Informationssystemen , S. 8 .). Die Topo- logie beschreibt nichtmetrische, strukturelle Beziehungen zwischen beliebigen Objekten. Topologische Beziehungen können u.a. die Nachbarschaft, das Enhaltensein und die Über- schneidung von Objekten betre en.

Die vorliegende Arbeit beschäftigt sich mit verschiedenen Ansätzen zur Au ndung von Nachbarschaftsbeziehungen zwischen Polygonen. In Geoinformationssystemen können Polygone zur Repräsentation beliebig geformter Flächen eingesetzt werden. Verwendung ndet die Nachbarschaftssuche beispielsweise bei der Generalisierung von Flächen (d.h. bei der Zusammenfassung von benachbarten Flächen mit dem Ziel der Komplexitätsre- duktion) oder in der Kartographie: ...die topologische Beschreibung der Nachbarschaft von Objekten [ist] eine wichtige Grundlage für die Gestaltung raumbezogener Datenstruk- turen... (vgl. [HGM02] Kartographie , S. 100). Andere Einsatzgebiete für die Nachbar- schaftssuche in Geoinformationssystemen liegen überall dort, wo die Festestellung der Nachbarschaft eine Voraussetzung ist für weitere di erenziertere, semantsiche Analysen (vgl. [ESR05] GIS Topology , S. 2).

In der vorliegenden Arbeit werden bezüglich der Darstellung der Polygone und Repräsentation der Nachbarschaftsbeziehungen keine, in irgendeiner Weise einschränkenden, Annahmen gemacht. Aus diesem Grunde ist der Einsatz der entwickelten und vorgestellten Algorithmen nicht nur auf Geoinformationssysteme beschränkt, sondern kann sich auf beliebige Bereiche der Computergra k erstrecken.

Im Folgenden wird der Aufabau der Arbeit kurz erläutert. Einleitend werden neben an- deren notwendigen De nitionen, die drei Arten von Nachbarschaftsbeziehungen de niert, die in dieser Arbeit betrachtet werden. Das dritte Kapitel stellt einen bereits vorhandenen Algorithmus zur Nachbarschaftssuche vor, der jedoch nur eine Art der Nachbarschafts- beziehung überdeckt. Aus diesem Grunde werden im vierten Kapitel, dem Hauptteil der Arbeit, ausgehend von dem Algorithmus aus Kapitel drei, zwei weitere Algorithmen ent- wickelt, die sich auf die anderen beiden Arten von Nachbarschaftsbeziehungen erstrecken. Kapitel fünft diskutiert die Parallelisierbarkeit der beiden im vierten Kapitel vorgestellten Algorithmen und enthält Vorschläge zu Parallelisierungsansätzen. Kapitel sechs schlieÿt die Arbeit mit einer Diskussion und Auswertung der Benchmarks der beiden Algorithmen aus Kapitel vier ab.

2 Grundlagen

In diesem Kapitel werden Grundlagen eingeführt, die zum Verständnis der, in dieser Arbeit behandelten Themen und Algorithmen, notwendig sind. Weiter reichende Aspekte und Ergänzungen, die hier nicht erwähnt sind, werden in den folgenden Kapiteln an den entsprechend sinnvollen Stellen gesondert behandelt.

2.1 De nitionen

1. Polygon

Ein Polygon ist eine zusammenhängende Fläche, die dadurch entsteht, dass man mindestens drei voneinander verschiedene Punkte (Eckpunkte des Polygons) durch Strecken (Kanten) miteinander verbindet. Ein Polygon ist also ein Vieleck. Bemerkung: Die Anzahl der Kanten in einem Polygon ist stets gleich der Anzahl der Punkte.

2. Planarität

Ein Polygon ist planar, wenn es in der Ebene liegt (und nicht im Raum).

3. Nicht-Überschneidung

Nicht-überschneidende Polygone besitzen keine gemeinsamen Punkte, die nicht auf ihren Kanten liegen.

4. Konvexität

In einem konvexen Polygon sind alle Innenwinkel kleiner als 180 . Ein nicht-konvexes (konkaves) Polygon besitzt mindesten einen Innenwinkel, der gröÿer ist als 180 Anschaulich ist ein Polygon konvex, wenn von jedem seiner Punkte aus alle Punkte des Polygons sichtbar sind. Wobei ein Punkt q von einem Punkt p aus sichtbar ist, wenn die Verbindungsstrecke zwischen p und q ganz im Polygon liegt.

Abbildung 2.1 zeigt vier Polygone: A und B sind konvex, C und D sind nicht-konvex. Beim Polygon C ist beispielsweise zu sehen, dass p von q aus nicht sichtbar ist (und umgekehrt), weil die (rote) Verbindungsstrecke nicht vollständig im Polygon liegt.

5. Kanten-Nachbarschaft

Zwei Polygone sind Kanten-benachbart, wenn sie gemeinsame Kantensegmente besitzen. Ein Kantensegment ist eine Teilstrecke einer Kante.

In der Abbildung 2.1 sind nur die Polygone A und D Kanten-benachbart.

2.1. DEFINITIONEN 7

6. Punkt-Nachbarschaft

Zwei Polygone sind Punkt-benachbart, wenn sie mindestens einen gemeinsamen Punkt auf ihren Kanten besitzen.

In der Abbildung 2.1 sind die Polygone A und B, A und C, sowie A und D Punktbenachbart.

7. Lose Nachbarschaft

Zwei Polygone sind lose benachbart (mit Parameter r), falls ein Punk des einen Polygons innerhalb der Object Aligned Bounding Box einer Kante des anderen Polygons liegt. Abbildung 2.2 veranschaulicht lose Nachbarschaft.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Konvexe und konkave Polygone. A und B sind konvex, C und D sind konkav. Kanten-benachbart sind: A und D. Punkt-benachbart sind: A und B, A und C, A und D.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Lose Nachbarschaft. Gestrichtelte Linie: Object Aligned Bounding Box.

2.2 Verwendete Formelzeichen

1. n ist die Anzahl der zu betrachtenden Polygone
2. mi ist die Anzahl der Kanten bzw. Eckpunkte des i-ten Polygons
3. Ei ist die Menge der Kanten des i-ten Polygons
4. Vi ist die Menge der Eckpunkte des i-ten Polygons ∑n

Abbildung in dieser Leseprobe nicht enthalten

[Abbildung in dieser Leseprobe nicht enthalten] sind Multimengen, denn es ist möglich, dass zwei verschiedene Polygone die gleiche Kante besitzen.

3 Stand der Technik

3.1 Algorithmus: Kanten-Nachbarschaft

Der in [ACD+01] Finding Adjacencies in Non-Overlapping Polygons vorgestellte Ansatz zur Nachbarschaftssuche in Mengen von nicht-konvexen, nicht-überschneidenden Polygonen betrachtet nur die Kanten-Nachbarschaft zwischen Polygonen.

Zur Bestimmung der Nachbarschaft werden drei Beobachtungen zu Nutze gemacht (vgl. [ACD+01], S. 3):

1. Kanten von benachbarten Polygonen liegen auf derselben Geraden. Ist also die erste Kante eine Teilstrecke der Geraden [Abbildung in dieser Leseprobe nicht enthalten] und die zweite Kante eine Teilstrecke der Geraden [Abbildung in dieser Leseprobe nicht enthalten], dann gilt:

m1 = m2 und b1 = b2

2. Die x-Intervalle der Kanten benachbarter Polygone überlappen sich. D.h. falls die erste Kante durch die Punkte (x1, y1), (x2, y2) und die zweite Kante durch die Punkte (x3, y3), (x4, y4) bestimmt ist, dann gilt:

Abbildung in dieser Leseprobe nicht enthalten

3. Falls für zwei Kanten die beiden obigen Bedingungen erfüllt sind, so sind die zuge- hörigen Polygone benachbart.

Der Algorithmus extrahiert zunächst die Kanten aller Polygone und legt sie in einem Array ab. Zu jeder Kante wird das x-Intervall, die Steigung, der y-Achsenabschnitt und ein Verweis auf das zugehörige Polygon gespeichert.

Das Array wird nach der Steigung sortiert, bei Gleichheit wird nach dem y-Achsenabschnitt unterschieden, bei weiterer Gleichheit nach dem linken Rand des x-Intervalls. Nach der Sortierung kann das Array als eine Menge von Sub-Arrays betrachtet werden, wobei in jedem Sub-Array die Steigungen und die y-Achsenabschnitte der Kanten gleich sind während die x-Intervalle aufsteigend nach der Koordinate des linken Randes geord- net sind.

Es genügt anschlieÿend ein linearer Durchlauf des Arrays, um alle Nachbarschaften zu bestimmen (vgl. [ACD+01], S.4).

Der vorgestellte Algorithmus berücksichtigt jedoch den Fall senkrechter Kanten (Geraden) nicht. In diesem Fall reicht die Betrachtung des x-Intervalls alleine nicht aus, es muss vielmehr auch das y-Intervall einer Kante hinzugezogen werden. Dieser Aspekt wird auf Seite 13f. genauer erläutert.

3.1. ALGORITHMUS: KANTEN-NACHBARSCHAFT 10

Die Laufzeit des vorgeschlagenen Algorithmus wird durch die Sortierung des Arrays dominiert und liegt bei der Anwendung eines Standard-Sortieralgorithmus (z.B. Quick-Sort) in O(mgeslog(mges)).

4 Algorithmen

4.1 Überlegungen zur Darstellung von Geraden

Ein wichtiger Aspekt bei den, in diesem Kapitel, vorgstellten Algorithmen (ebenso wie beim Algorithmus aus dem letzten Kapitel) ist die Art der Geradendarstellung. Aus diesem Grund werden an dieser Stelle die verschiedenen Möglichkeiten sowie ihre Vorund Nachteile diskutiert.

Es gibt prinzipiell zwei verschiedene Möglichkeiten zur Beschreibung von Geraden:

- durch lineare Funktionen der Form:[Abbildung in dieser Leseprobe nicht enthalten]
- durch Vektorgleichungen der Form: [Abbildung in dieser Leseprobe nicht enthalten]

Welche der beiden Darstellungsformen sich am besten für die Implementierung der Algo- rithmen eignet, wird im Folgenden untersucht. Speicher- und Zeite zienz sind die beiden in erster Linie zu betrachtenden Aspekte. Die Speichere zienz ergibt sich aus dem für die Speicherung der Geraden-Parameter(m und b bzw. n und c) benötigten Speicher. Die Zeite zienz bezieht sich auf die Bestimmung der jeweiligen Geraden-Parameter aus zwei gegebenen Punkten.

Lineare Funktionen

Für die Speichereffizienz ergibt sich eine Gleitkommazahl für die Steigung und eine Gleitkommazahl für den y-Achsenabschnitt, insgesamt also zwei Gleitkommazahlen. Die Zeiteffizienz wird durch die Berechnung der Steigung und des y-Achsenabschnitts be-

Abbildung in dieser Leseprobe nicht enthalten

Insgesamt also drei Additionen, eine Division und eine Multiplikation.

Das Problem bei der Darstellung durch lineare Funktionen ist, dass sich keine senkrechten (zur y-Achse parallelen) Geraden beschreiben lassen, da eine Division durch Null nicht de niert ist bzw. die Steigung in diesem Fall gegen Unendlich geht.

Vektorgleichungen

Für die Speichereffizienz ergeben sich zwei Gleitkommazahlen für den Normalenvektor und eine Gleitkommazahl für die Konstante, insgesamt also drei Gleitkommazahlen. Die Zeitefffizienz wird durch die Berechnung des Einheits-Normalenvektors n und der Konstanten c bestimmt. Mit

4.1. ÜBERLEGUNGEN ZUR DARSTELLUNG VON GERADEN

Abbildung in dieser Leseprobe nicht enthalten

ergeben sich also vier Additionen, zwei Divisionen, vier Multiplikationen und eine Wurzeloperation.

Das Problem bei der Darstellung durch Vektorgleichungen besteht darin, dass der klei- ner als (gröÿer als)-Operator auf Vektoren de niert werden müsste, um eine Sortierung zu ermöglichen, was für den Algorithmus aus dem letzten Kapitel gefordert ist. Eine Al- ternative wäre beispielsweise nicht den Normalenvektor selbst, sondern seinen Winkel zur x-Achse zu sortieren, was aber mit zusätzlichen Berechnung verbunden wäre. Zusätzliche Schwierigkeiten ergeben sich auÿerdem durch die Nichteindeutigkeit des Normalenvek- tors.

Auswertung

Wie der Vergleich zeigt, ist die Darstellung durch eine lineare Funktion die e zientere Möglichkeit der Implementierung. Das Problem der unendlichen Steigung ist mathematisch zwar schwer zu handhaben, führt bei der Implementierung jedoch zu keinen groÿen Schwierigkeiten. Das IEEE 754-Gleitkommaformat (heute am häu gsten verwendet) ermöglicht eine problemlose Darstellung der Unendlichkeit, indem es dafür bestimmte, sonst nie auftretende Werte vorsieht. Dem Problem der Division durch Null kann man mit einer Fallunterscheidung begegnen.

Der folgende C++ Quellcode zeigt eine mögliche Implementierung der Funktion zur Berechnung der Steigung. Interessant dabei sind die Zeilen 4 - 7. Falls die Di erenz der x-Koordinaten der beiden Punkte 0 ist, handelt es sich um eine senkrechte Gerade und es wird der double-Wert für die Unendlichkeit zurückgegeben. Dieser Wert wird von der C++-Standardbibliothek zur Verfügung gestellt, wie man in Zeile 6 sieht.

Abbildung in dieser Leseprobe nicht enthalten

Die IEEE 754 Spezi kation garantiert, dass die Semantik der Vergleichsoperatoren beim Unendlichkeitswert erhalten bleibt, so dass am Sortierungsalgorithmus keine Verände- rungen vorgenommen werden müssen, um mit der Unendlichkeit umgehen zu können. Es ist aber auch möglich einen beliebigen Wert für die Unendlichkeit zu de nieren, solange dafür gesorgt ist, dass er einzigartig ist und bei keinen anderen Berechnungen zustan- de kommen kann. In diesem Fall wäre explizit zu gewährleisten, dass die Semantik der Vergleichsoperatoren erhalten bleibt.

Es bleibt nur noch zu betrachten, was bei einer unendlichen Steigung mit dem y-Achsenabschnitt passiert. Bei der Benutzung der oben erwähnten Formel zur Berechnung des y-Achsenabschnitts und dem Einsetzen des Unendlichkeitswertes für die Steigung, ergibt sich für den y- Achsenabschnitt der negative Unendlichkeitswert .

[...]