Institut für Kartographie und Geoinformation Prof. Dr. Lutz Plümer Geoinformation II Vorlesung 8 SS 2000 Punkt-in-Polygon-Verfahren II (Trapezkarte)

Institut für Kartographie und GeoinformationProf. Dr. Lutz Plümer

Geoinformation IIVorlesung 8

SS 2000

Punkt-in-Polygon-Verfahren II(Trapezkarte)

Lutz Plümer - Geoinformation - 6. Semester - SS 2001 - Vorlesung 8 Lutz Plümer - Geoinformation - 6. Semester - SS 2001 - Vorlesung 8

2 2

Übersicht I

• Zur Erinnerung: Punktsuche in Landkarten• Lösung 1: Zerlegung in vertikale Streifen• Nachteil: O(n²) Speicherplatz im Worst Case• Lösung 2: Trapezkarte• Trapezkarte: Konstruktionsprinzip• Trapezkarte: vereinfachende Annahme• 5 Fälle für die vertikalen (linken) Kanten• Bezeichnungen• Trapezkarte - Eigenschaften• Probleme und weiteres Vorgehen


3 3

Übersicht II

• T(S) und D(S)• Schrittweise Konstruktion von T(S) und D(S)• Trapezkarte und Suchstruktur zweier Kanten• Beachte:• Datenstruktur für T(S)• Skizze: Konstruktion von T(S) und D(S)

• Von T(Si-1) und D(Si-1) zu T(Si) und D(Si)

• Einfügen einer Kante I

• Von T(Si-1) und D(Si-1) zu T(Si) und D(Si) Fall2

• Einfügen einer Kante II


4 4

Zur Erinnerung: Punktsuche in Landkarten

In welcher Masche liegt q?

Außen

x

y

Landkarte S mitn Kanten

q


5 5

Außen

q

Lösung 1: Zerlegung in vertikale Streifen

x

y


6 6

Nachteil: O(n²) Speicherplatz im Worst Case

4

n

4

n


7 7

Lösung 2: Trapezkarte

R


8 8

Trapezkarte: Konstruktionsprinzip

• Die Trapezkarte T(S) einer Landkarte S wird wie folgt konstruiert:– Bilde ein umschließendes Rechteck R

• Vermeidung der unbeschränkten Masche „Außen“– Konstruiere für jeden Endpunkt P eines Segments aus S

eine obere und eine untere vertikale Extension (Linie); diese Linien enden am Schnittpunkt mit dem nächsten Segment aus S oder an R

• Diese Konstruktion zerlegt R in disjunkte Trapeze, die von (höchstens) 4 Seiten begrenzt werden: – Ein oder zwei vertikale Seiten, gebildet aus den Extensionen– Eine obere und eine untere Seite, gebildet aus den

Segmenten


9 9

Trapezkarte: vereinfachende Annahme

• Es gibt keine zwei Knoten mit gleicher x-Koordinate, d.h. es gibt keine vertikalen Kanten

• Falls diese Annahme nicht erfüllt ist, kann sie durch Rotation um den Ursprung + Scherung mit einem sehr kleinen Winkel , der topologisch „nichts kaputt macht“, hergestellt werden

• Später werden wir sehen, dass diese Transformation rein virtuell ist


10 10

5 Fälle für die vertikalen (linken) Kanten

1. Kante entartet zu einem Punkt

2. Die untere vertikale Er-weiterung trifft auf eine Kante von S

3. Die obere vertikale Er-weiterung trifft auf eine Kante von S

4. Kante besteht aus oberer und unterer Erweiterung

5. Kante besteht aus einer Kante von R


11 11

Bezeichnungen

leftp

rightp

top

bottom


12 12

Trapezkarte - Eigenschaften

Satz: Eine Trapezkarte einer Landkarte S mit n Kanten enthält höchstens (a) 6n + 4 vertikale Linien und (b) 3n + 1 Trapeze.

Beweis: (a) Ein Knoten der Trapezkarte ist entweder– ein Eckpunkt von R 4– ein Knoten der Karte S 2n– ein Punkt, bei dem eine Erweiterung auf eine

Kante von S trifft 4n

Insgesamt: 6n + 4


13 13


Satz: Eine Trapezkarte einer Landkarte S mit n Kanten enthält höchstens 6n + 4 vertikale Linien und sowie 3n + 1 Trapeze.

Beweis: (b): aus a) mit Eulers Formel


14 14


Zwei Trapeze T und T‘ heißen adjazent, wenn sie sich entlang einer vertikalen Linie berühren

T‘T

Es gilt entweder top(T) = top(T‘) oder

bottom(T) = bottom(T‘)

T T‘

T‘T


15 15

Probleme und weiteres Vorgehen

Probleme:• Konstruktion der Trapezkarte T(S)• Unterstützung der Suche in einer Trapezkarte

Idee für das weitere Vorgehen:• Unterstützung der Suche durch eine Art „binärer

Suchbaum“ D(S) mit 2 Sorten von Knoten–X-Knoten für Endpunkte / Extensionen

• Links oder Rechts?–Y-Knoten für Segmente

• Oben oder Unten?

• Trapezkarte und „Baum“ werden simultan konstruiert


16 16

T(S) und D(S)

p1

A q1

s1

B

C

p2

q2

s2

s2

D

E

F

G

D

E

F

G

A

B

C

p1

q1s1

p2

q2

s2


17 17

Schrittweise Konstruktion von T(S) und D(S)


18 18

Trapezkarte und Suchstruktur zweier Kanten

X

p1


19 19


p1p1

p1


20 20


X

A

X

p1

q1

A

p1


21 21


A

q1

p1

A q1

s1s1

s1 q1

p1


22 22

X


A

p1

A q1

s1

B

B X

Y

Yp2

s1

p1

q1


23 23


A

B

p1

A q1

s1

B

Y

Yp2p2

s1 q1

p2

p1


24 24


A

B

p1

A q1

s1

B

Y

Yp2

CC

XX

q2

s1 q1

p2

p1


25 25


A

B

C X

p1

A q1

s1

B

C

p2

X

q2

q2q2

s2

s1

p2

q1

p1


26 26

A

B

C


p1

A q1

s1

B

C

p2

q2

p2

s2

s2

p1

q1s1

q2

s2

s2

s2


27 27

D

E

F

G

A

B

C


p1

A q1

s1

B

C

p2

q2

s2

s2

p1

q1s1

D

E

F

Gp2

q2

s2


28 28

Beachte:

• T(S) und D(S) werden simultan konstruiert• D(S) ist kein Baum, sondern ein „DAG“, ein „directed

acyclic graph“, ein gerichteter azyklischer Graph• Dieser DAG ist zusammenhängend und hat genau

eine Wurzel• Unterschied zum Baum: innere Knoten können

mehrere Vorgänger haben• Die Blätter von D(S) und die Trapeze von T(S)

referenzieren sich gegenseitig• Wie stets hängt die Tiefe (=Güte) des Baumes von

der Reihenfolge der Bearbeitung der Segmente ab• Idee: Zufällige Permutation der Segmente von S


29 29

Datenstruktur für T(S)

• Möglich wäre eine doppelt verkettete Kantenliste (s. Overlay)• Wegen der einfachen Struktur der Trapeze bietet sich folgende

Alternative an:• Knoten (mit Koordinaten)• Segmente (mit Referenzen auf Knoten)• Trapeze mit Referenzen auf:

– Top

– Bottom

– Leftp

– Rightp

– alle (maximal 4) Nachbarn

• Beachte: Die Geometrie der Trapeze ist nur implizit, kann aber in konstanter Zeit rekonstruiert werden


30 30

Skizze: Konstruktion von T(S) und D(S)

Input: Eine Menge S von n Segmenten

1. Konstruiere ein umschließendes Rechteck R

2. Berechne eine Permutation s1, s2,...,sn von S

3. for i= 1 to n doKonstruiere T(Si) und D(Si) mit Si = {s1, s2,...,si} unter Verwendung von T(Si-1) und D(Si-1)

„Schleifeninvariante“: T(Si-1) ist eine Trapezkarte und D(Si-1) ist eine Suchstruktur für diese Trapezkarte

Der Unterschied zwischen „i-1“ und „i“ betrifft genau die Trapeze in T(Si-1) , die von si geschnitten werden


31 31

Von T(Si-1) und D(Si-1) zu T(Si) und D(Si)

Fall 1: si liegt in genau einem Trapez

Input: Das Segment si, T(Si-1) und D(Si-1)

Idee: Nutze die Suchstruktur D(Si-1), um schnell zu finden

Vorgehen: Modifiziere T(Si-1) und D(Si-1) in der auf den folgenden Folien beschriebenen Weise:


32 32

Einfügen einer Kante I

D(Si-1)

pi

T(Si-1)


33 33


D(Si-1)

pipi

sisi

si

qiqi

pi

qi


34 34


C D

B

A

D(Si-1)

pi

qi

si

AC

BD

pi

qisi

T(Si) D(Si)


35 35

Von T(Si-1) und D(Si-1) zu T(Si) und D(Si) Fall2

Fall 2: si liegt in mehrere Trapezen 1, 2,... n

Input: Das Segment si, T(Si-1) und D(Si-1)

Teilziel: Bestimmung von 1, 2,... n Beobachtungen:• i ist rechter Nachbar von i-1

• Jedes Trapez hat maximal 2 rechte Nachbarn• Der richtige kann mit rightp() rasch identifiziert werden:

– wenn rightp() oberhalb von si, dann wähle den unteren rechten Nachbarn, sonst den oberen

– Der Übergang von i zu i+1 ist also einfach

• Nutze D(Si-1) um 1 schnell zu finden

Modifiziere T(Si-1) und D(Si-1) nun auf die folgende Weise:


36 36

Einfügen einer Kante II

3

D(Si-1)

1 20 3

0

1

2

qi

T(Si-1)

pi


37 37


0

1

2 qi

si

qi

qi

pi

D(Si-1)

1 20


38 38


D(Si-1)

qi

si

si sisi

qi

pi

si si si

sisi


39 39


D(Si-1)

qisi sisiA

B

DE

FB D si

A

C

F

E

Csipi

qi

T(Si)D(Si)

Documents

Institut für Kartographie und Geoinformation Prof. Dr. Lutz Plümer Geoinformation II Vorlesung 8 SS 2000 Punkt-in-Polygon-Verfahren II (Trapezkarte)