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 Aundung 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 Aundung der Punkt-Nachbarschaft und der losen Nachbarschaft entwickelt. Im worst case liegt die Zeitkomplexität dieser

beiden Algorithmen in O(m 2 ges ) (wobei m ges die Gesamtanzahl aller Kanten bzw. Eckpunkte ist). Eine Sortierung aller Eckpunkte nach der x-Koordinate und eine anschlieÿende, eziente 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 2

Inhaltsverzeichnis   

Abbildungsverzeichnis   3

Tabellenverzeichnis 4   

1  Einleitung  5

2  Grundlagen  6

2.1  Denitionen  6

2.2  Verwendete Formelzeichen  8

3  Stand der Technik  9

3.1  Algorithmus: Kanten-Nachbarschaft  9

4  Algorithmen  11

4.1  Überlegungen zur Darstellung von Geraden  11

4.2  Algorithmus 1: Punkt-Nachbarschaft  13

4.3  Algorithmus 2: Lose Nachbarschaft  19

4.4  Alternative Auasungen der losen Nachbarschaft  24

5  Untersuchungen zur Parallelisierbarkeit  27

5.1  Parallelisierung des Hauptteils  27

5.2  Parallelisierung der Vorausberechnung  29

6  Bewertung und Vergleich  30

6.1  Benchmarks  30

6.2  Auswertung  33

Literaturverzeichnis   36

Abbildungsverzeichnis   3

Abbildungsverzeichnis   

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

2.2  Lose Nachbarschaft  7

4.1  Punkt-Nachbarschaft zwei Fälle  13

4.2  Einschränkung des Suchbereiches durch das x-Intervall  15

4.3  Sortierte Punktmenge  16

4.4  OBB und ABB  20

4.5  Berechnung der Object Aligned Bounding Box  21

4.6  Problemfälle bei der Bestimmung der losen Nachbarschaft  25

6.1  Punkt-Nachbarschaft: 1.000 Polygone  31

6.2  Punkt Nachbarschaft: 10.000 Polygone  32

6.3  Punkt Nachbarschaft: 100.000 Polygone  32

6.4  Lose Nachbarschaft: 1.000 Polygone  32

6.5  Lose Nachbarschaft: 10.000 Polygone  33

6.6  Lose Nachbarschaft: 100 000 Polygone  33

Tabellenverzeichnis 4   

Tabellenverzeichnis   

6.1  mittlere Kantenanzahl und Mittlere Laufzeit der drei Testfelder  35

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

6.3  lose Nachbarschaft: Speedup gegenüber rein quadratischer Zeit  35

5

1 Einleitung

Die Gewinnung von nützlicher, struktureller Information, aus eingangs unstrukturierten Rohdaten, ist ein zentraler Aspekt in Geoinformationssystemen (GIS). Neben räumlicher (topograscher) Information nimmt die Extraktion und Darstellung von topologischen Beziehungen zwischen Geoobjekten (z.B. Flächen) eine wichtige Stellung ein (vgl. [Röo98] Topologische Beziehungen in Geo-Informationssystemen , S. 8.). Die Topologie beschreibt nichtmetrische, strukturelle Beziehungen zwischen beliebigen Objekten. Topologische Beziehungen können u.a. die Nachbarschaft, das Enhaltensein und die Überschneidung von Objekten betreen.

Die vorliegende Arbeit beschäftigt sich mit verschiedenen Ansätzen zur Aundung 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ätsreduktion) oder in der Kartographie: ...die topologische Beschreibung der Nachbarschaft von Objekten [ist] eine wichtige Grundlage für die Gestaltung raumbezogener Datenstrukturen... (vgl. [HGM02] Kartographie , S. 100). Andere Einsatzgebiete für die Nachbarschaftssuche in Geoinformationssystemen liegen überall dort, wo die Festestellung der Nachbarschaft eine Voraussetzung ist für weitere dierenziertere, 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 Computergrak erstrecken.

Im Folgenden wird der Aufabau der Arbeit kurz erläutert. Einleitend werden neben anderen notwendigen Denitionen, die drei Arten von Nachbarschaftsbeziehungen deniert, die in dieser Arbeit betrachtet werden. Das dritte Kapitel stellt einen bereits vorhandenen Algorithmus zur Nachbarschaftssuche vor, der jedoch nur eine Art der Nachbarschaftsbeziehung überdeckt. Aus diesem Grunde werden im vierten Kapitel, dem Hauptteil der Arbeit, ausgehend von dem Algorithmus aus Kapitel drei, zwei weitere Algorithmen entwickelt, 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.

6

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 Denitionen

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

◦ . Ein nicht-konvexes In einem konvexen Polygon sind alle Innenwinkel kleiner als 180

◦ . (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 2.1: Konvexe und konkave Polygone. A und B sind konvex, C und D sind

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