Upload
dirk-lausch
View
103
Download
0
Embed Size (px)
Citation preview
Institut für Kartographie und GeoinformationProf. Dr. Lutz Plümer
Geoinformation IIIVorlesung 1
WS 2001/02
Punkt-in-Landkarte I (Streifenkarte)
Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01
2 2
Übersicht
Die Vorlesung besteht aus 3 Blöcken• räumliche Datenbanken
– Zugriffsstrukturen zur Unterstützung der Suche– Transaktionen (Sicherheit)
• Softwaretechnologie – (Dr. Gröger)
• Internet: Protokolle, Dienste und Formate– Dr. Kolbe
• Form: Vorlesung mit Übungsanteilen • Klausur: 1 Doppelseite A4 aus der eigenen Feder pro
Block
Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01
3 3
Problemstellung
• allgemein– gegeben ist eine räumliche Datenbank und eine Klasse
typischer Anfragen– wie strukturiere ich meine Daten so, dass ich diese Anfragen
möglichst effizient beantworten kann
• konkret– gegeben ist eine Landkarte– Frage: in welcher Masche liegt ein gegebener Punkt
Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01
4 4
Übersicht
• Punktsuche in Landkarten• Vorgehen I (naiv)• Vorgehen II (semi-naiv)• Eigenschaften der Zerlegung I• Eigenschaften der Zerlegung II• Eigenschaften der Zerlegung III• Vorgehen I• Algorithmus punktsuche• Binäre Suche in einem sortierten Array• Komplexität der Suche• Speicheranforderung• Speicheranforderung (Beispiel worst-case)
Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01
5 5
Punktsuche in Landkarten
In welcher Masche liegt q?
Außen
x
y
Landkarte S mitn Kanten
q
Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01
6 6
Anzahl der Schnittpunkte• gerade: außerhalb• ungerade: innerhalb
Vorgehen I (naiv)
Naives Verfahren: Test für jede Masche iterieren Aufwand: mindestens O(n) für die Suche nach einem
Punkt in einem Polygon mit n Kanten bei m Polygonen: O(m * n) Wie geht es schneller? genauer: Welcher „Index“ unterstützt die schnelle Antwort
auf die Frage: „In welcher Masche einer Landkarte liegt der Punkt q?“
Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01
7 7
Vorgehen II (etwas besser)
Außen
x
y
q
Aufteilung der Landkarte durchvertikale Linien Konstruktion einer Karte S‘
Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01
8 8
Außen
q
Eigenschaften der Zerlegung I
• Die Maschen werden in Trapeze (ggf. Dreiecke) zerlegt
• Dadurch werden auch die Kanten in Teilkanten zerlegt
• Kein Knoten liegt im Inneren eines Trapezes
• Die Teilkanten eines Streifens lassen sich anordnen
Übung: Vergleich mit Scan-Line beim Segmentschnitt
x
y
Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01
9 9
Jede Kante lässt sich einer in y-Richtung folgenden Masche zuordnen
q
x
yAußen
Eigenschaften der Zerlegung II
Jeder Abschnitt eines Streifens liegt in genau einer Masche
Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01
10 10
Jede Kante lässt sich einer in y-Richtung folgenden Masche zuordnen
q
x
yAußen
Eigenschaften der Zerlegung III
Jeder Abschnitt eines Streifens liegt in genau einer Masche
Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01
11 11
Vorgehen I
Aufteilung der Landkarte vertikale Linien Konstruktion einer Karte S‘
Außen
Sortierte Speicherung der x-Koordinaten der Vertikalen in einem Array
Sortierte Speicherung der Kantenjedes Streifens in einem Array
q
x
y
Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01
12 12
Algorithmus punktsuche
binäre Suche, wie q zu den Kanten(Segmenten) liegt
Algorithmus punktsuche{
binäre Suche des Streifens, der q enthält, im Array der x-Koordinaten
q
x
y
Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01
13 13
Algorithmus punktsuche
falls ein Segment direkt unterhalb q gefunden wird, ist die gesuchte Masche gefunden}
q
x
y
binäre Suche, wie q zu den Kanten(Segmenten) liegt
Algorithmus punktsuche{
binäre Suche des Streifens, der q enthält, im Array der x-Koordinaten
Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01
14 14
Binäre Suche in einem sortierten Array
• Suche der Position einer Zahl x in einem Array A der Länge n
• bestimme die mittlere Position i und den Wert A[i] • Fall x = A[i]: return i• Fall x < A[i]: setze die Suche in der linken Hälfte von A
rekursiv fort• Fall x > A[i]: setze die Suche in der rechten Hälfte von A
rekursiv fort
Übung: Adaptiere den Algorithmus so, dass er das nächst kleinere Element findet
Adaptiere den Algorithmus so, dass er auf beide Fälle unsers Algorithmus anwendbar ist. Nutze zum Vergleich der Segmente eine „Scan-Line“ durch den Punkt q.
Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01
15 15
Komplexität der Suche
Gesamtkomplexität: O(log n)
Algorithmus punktsuche{
binäre Suche des Streifens der q enthält im Array der x-Koordinaten
falls ein Segment direkt unterhalb q gefunden wird, ist die gesuchte Masche gefunden }
Binäre Suche in einem Array mit maximaler Länge 2n: O(log n)
Binäre Suche in einem Array mit maximaler Länge n: O(log n)
binäre Suche, wie q zu den Kanten(Segmenten) liegt
Gegeben ist eine Landkarte mit n Kanten.
Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01
16 16
Speicheranforderung
Aufteilung der Landkarte durch vertikale Linien Konstruktion einer Karte S‘
Sortierte Speicherung der x-Koordinaten der Vertikalen in einem Array
Sortierte Speicherung der Kantenjedes Streifens in einem Array
Array der x-Koordianten benötigt O(n)
Array jedes Streifens benötigt O(n)
Gesamtkomplexität: O(n²)
Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01Lutz Plümer - Geoinformation III - WS 01/02 - Vorlesung 1 - 22.10.01
17 17
Speicheranforderung (Beispiel worst-case)
4
n
4
n