Institut für Kartographie und Geoinformation Prof. Dr. Lutz Plümer Geoinformation III Vorlesung 3 WS 01/02 Punkt-in-Polygon-Verfahren III (R/R + -Baum)

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

Geoinformation IIIVorlesung 3

WS 01/02

Punkt-in-Polygon-Verfahren III(R/R+-Baum)

Lutz Plümer - Geoinformation III - 5. Semester - WS 01/02 - Vorlesung 3 Lutz Plümer - Geoinformation III - 5. Semester - WS 01/02 - Vorlesung 3

2 2

Übersicht I

• Zur Erinnerung• Zerlegung der Maschen in Streifen• Suchstruktur• Einfügen einer Kante II• Zur Effizienz• Effizienz II:• Sonderfallbetrachtung• Punkt-in-Polygon-Suche II• MBR – minimum bounding rectangle• Idee• Neues laufendes Beispiel• Rechtecke


3 3

Übersicht II

• Rechtecke mit R-Baum• R-Baum• R-Baum als B-Baum• Der R-Baum als solcher• Einfügen in einen R-Baum• Strategien zum Spalten eines Knotens• Suchen eines Knotens• Nachteil des R-Baums• Alternative: Der R+-Baum• R+-Baum• Suche im R+-Baum


4 4

Zur Erinnerung:


5 5

Zerlegung der Maschen in Streifen

R


6 6

D

E

F

G

A

B

C

Suchstruktur

p1

A q1

s1

B

C

p2

q2

s2

s2

p1

q1s1

D

E

F

Gp2

q2

s2


7 7

Suchstruktur

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


8 8

Einfügen einer Kante II

D(Si-1)

qisi sisiA

B

DE

FB D si

A

C

F

E

Csipi

qi

T(Si)D(Si)


9 9

Zur Effizienz

Der oben beschriebene Algorithmus hat folgende

Erwartungswerte (gemittelt über alle Permutationen der Segmentmenge S):

Konstruktion von D(S): O(n log n)

Speicherplatz von D(S): O(n)

Punkt-in-Polygon-Suche mittels D(S): O(log n)


10 10

Effizienz II:

• Der Erwartungswert bezieht sich auf die Menge aller Permutationen

• Pech bei der Permutation kann zum Worst – Case O(n) für die Suche und entsprechender Tiefe der Suchstruktur führen

• Abhilfe durch Stop-Loss-Punkt setzen:– Brich ab, falls D(S) zu tief wird, und fange neu an mit einer neuen

Permutation

• Differenz zum Worst-Case O(n) für die Suche und O(n2) für die Konstruktion kann beliebig klein gemacht werden, ohne daß man von der O(n log n) – Laufzeit für die Konstruktion von D(S) sehr stark abweicht


11 11

Sonderfallbetrachtung

Was macht man, wenn 2 Knoten die gleichen x-Koordinaten haben?• Beobachtung: die vertikalen Extensionen müssen eigentlich nicht

vertikal, sondern nur parallel sein• Wichtig sind nur die topologischen Invarianten links / rechts an

den x-Knoten und oben / unten an den y-Knoten• Abhilfe durch

Transformation (x,y) (x + * y, y) für „geeignet kleines“ Epsilon• Diese Transformation wird aber in Wirklichkeit gar nicht

durchgeführt, sondern:– (x,y) liegt rechts von (x‘,y‘) falls x > x‘ oder x = x‘ und y > y‘

• Oben / Unten – Vergleich an y-Knoten für Segmente „in the same spirit“ (als Übung)


12 12

Punkt-in-Polygon-Suche II

• Bisher:– Zerlegung der Maschen in Streifen– Konstruktion einer Suchstruktur

• Alternatives Vorgehen:• Approximation der Maschen durch umschließende

achsenparallele Rechtecke – Minimal Bounding Rectangle (MBR)– Verwaltung der Rechtecke

• R-Baum• R+-Baum


13 13

B-Baum

Ein kleiner Exkurs:

Der B-Baum wurde nach seinem Entwickler R. Bayer benannt.

Die Suche eines Elementes in einem B-Baum unterscheidet

sich nur wenig von der Suche in anderen Such-Bäumen.

Das Einfügen und Entfernen von Elementen ist jedoch an

vielen Stellen anders als in Binär-Such-Bäumen.


14 14

B-Baum

• Eigenschaften eines B-Baumes der Ordnung n:– Ein B-Baum ist nicht binär– Ein B-Baum ist ausgeglichen– Alle Blätter haben das gleiche Niveau– Jeder Knoten enthält höchstens 2n Elemente– Jeder innere Knoten außer der Wurzel enthält mindestens n

Elemente– Jeder innere Knoten hat m+1 Nachfolgeknoten, wobei m die Anzahl

der Schlüssel des inneren Knotens ist– Die m Schlüssel eines inneren Knotens werden in aufsteigender

Reihenfolge gespeichert: x1 < x2 < ... < xn

– Für jeden i-ten Teilbaum Si eines Knotens gilt:Die Schlüssel seiner Knoten sind grösser als xi und kleiner als xi+1 (ganz links und ganz rechts analog)

– Bei einigen Varianten des B-Baums stehen alle Informationen in den Blättern


15 15

B-Baum der Ordnung 2 (n=2)

2 9 12

13 15 171 233

29 48

19

10 37 567


16 16

Einfügen

• Einfügen eines Elements mit dem Wert 18 (Idealfall)

2 9 12

13 15 171 3

19

107 23

29 48

37 56

18 < 19 linker Ast


17 17

Einfügen

• Einfügen eines Elements mit dem Wert 18

2 9 12

13 15 171 3

19

107 23

29 48

37 56

18 > 12 rechter Ast


18 18

Einfügen


2 9 12

13 15 171 3

19

107 23

29 48

37 56

18 > 12 rechter Ast


19 19

Einfügen


2 9 12

13 15 171 3

19

107 23

29 48

37 56

18 > 17 Einfügen


20 20

Einfügen


2 9 12

13 15 171 3

19

107 23

29 48

37 56

18 > 17 Einfügen


21 21

Einfügen


2 9 12

13 15 17 181 3

19

107 23

29 48

37 56

18 > 17 Einfügen


22 22

Einfügen

• Einfügen eines Elements mit dem Wert 14 (Problemfall)

2 9 12

13 15 17 181 3

19

107 23

29 48

37 56

14 < 19 linker Ast


23 23

Einfügen


2 9 12

13 15 17 181 3

19

107 23

29 48

37 56

14 > 12 rechter Ast


24 24

Einfügen


2 9 12

13 15 17 181 3

19

107 23

29 48

37 56

14 > 12 rechter Ast

Problem: Speicher voll

Lösung: Knoten sprengen


25 25

Einfügen


2 9 12

13 15 17 181 3

19

107 23

29 48

37 56

Lösung: Knoten sprengen


26 26

Einfügen


2 9 12

13 14 15 171 3 107

19

23

29 48

37 5618

Setze das mittlere Element um

eine Position nach oben


27 27

Einfügen


2 9 12 15

13 14 171 3 107

19

23

29 48

37 5618

Bilde zwei neue Zweige


28 28

Einfügen


13 14 17

2 9 12 15

1 3 107

19

23

29 48

37 5618



29 29

Einfügen


13 14 17

2 9 12 15

1 3 107

19

23

29 48

37 5618



30 30

Einfügen


13 14 17

2 9 12 15

1 3 107

19

23

29 48

37 5618



31 31

Einfügen



13 14

2 9 12 15

1 3 107

19

23

29 48

37 5617 18


32 32

Einfügen



13 14

2 9 12 15

1 3 107

19

23

29 48

37 5617 18


33 33

Entfernen

Das Löschen in einem B-Baum gestaltet sich sehr einfach.

Wir unterscheiden hier folgende Fälle:

1. Löschen in einem Blatt: Einfaches Löschen

2. Löschen in einem inneren Knoten: Beachte: die Anzahl der Schlüssel der inneren Knoten muss mindestens n sein Wie bei AVL-Bäumen den Eintrag ersetzen durch den Rechtesten Eintrag im linken Unterbaum oder den Linkesten im Rechten.


34 34

Entfernen

• Entfernen des Elements mit dem Wert 48

2 9 12

13 15 171 3

19

107 23

29 48

27 31 37 49 60


35 35

Entfernen


2 9 12

13 15 171 3

19

107 23

29

27 31 37 49 60

Keine n Elemente im Knoten


36 36

Entfernen


2 9 12

13 15 171 3

19

107 23

29

27 31 37 49 60

Keine n Elemente ersetzen durch den

Rechtesten Eintrag im linken Unterbaum


37 37

Entfernen


2 9 12

13 15 171 3

19

107 23

29 37

27 31 49 60

Keine n Elemente ersetzen durch den

Rechtesten Eintrag im linken Unterbaum


38 38

Punkt-in-Polygon-Suche II

• Approximation der Maschen durch umschließende achsenparallele Rechtecke – Minimal Bounding Rectangle (MBR)– Verwaltung der Rechtecke

• R-Baum• R+-Baum


39 39

MBR – minimum bounding rectangle

Außen

x

y


40 40

Idee

• In welcher Masche M liegt der Punkt P?• Nutze die Bounding Boxes als Filter• Verwende effizientes Verfahren, um alle Rechtecke

R1, ... Rn zu finden, die P enthalten

– Jedem Rechteck Ri entspricht eine Masche Mi

• Prüfe, ob P in einer der Maschen M1, ... Mn vorkommt

• Verwende dazu das Standardverfahren• Problem: Zugriffsstruktur für Rechtecke• Rechtecke sind einfacher zu handhaben als Maschen

im allgemeinen


41 41

Neues laufendes Beispiel

• Nur die Rechtecke interessieren uns hier, nicht die zugrundeliegenden Maschen


42 42

Rechtecke

B

D

G

J F

CI

E H

A


43 43

E H

Rechtecke mit R-Baum

A

B

D

G

J F

CI

3 4

1 2

A I E H

5

B C D

6

J F G

6

4

21

35


44 44


A

I

3

A I

3


45 45


A

I

3

A I

3

E H

4

4

E H


46 46

E H


A

B

D

G

J F

CI

3 4

1 2

A I E H

5

B C D

6

J F G

6

4

21

35


47 47

R-Baum

1 2

B

D

G

J F

CI

12

E H

A


48 48

E H

R-Baum

3

1 2

A

B

D

G

J F

CI3

A I

21


49 49

E H

R-Baum

3 4

1 2

A

B

D

G

J F

CI3

4

A I E H

21


50 50

E H

R-Baum

A

B

D

G

J F

CI

4

3 4

1 2

A I E H

5

5

B C D

21

3


51 51

E H

R-Baum

A

B

D

G

J F

CI

3 4

1 2

A I E H

65

B C D

5

6

J F G

4

21

3


52 52

E H

R-Baum

A

B

D

G

J F

CI

3 4

1 2

A I E H

5

B C D

6

J F G

6

4

21

35


53 53

R-Baum als B-Baum

• Ein R-Baum ist ein B-Baum mit zusätzlichen Eigenschaften

• B-Baum (zur Erinnerung)

– Ein B-Baum ist (wie der AVL-Baum) ausgeglichen– Besonders gut für Hintergrundspeicher (Festplatte), innere

Knoten entsprechen „Kacheln“ des Sekundärspeichers– Alle Informationen stehen in den Blättern– Alle Blätter haben das gleiche Niveau– Alle inneren Knoten außer der Wurzel sind mindestens zur

Hälfte gefüllt– Teilung beim Überlauf eines inneren Knoten – Verteilung auf Nachbarn beim Unterlauf


54 54

Der R-Baum als solcher

• Ein Blattknoten ist ein Paar (R,O), R ist das kleinste Rechteck, welches das Objekt O umschließt

• Jeder innere Knoten hat n Paare (R,P)– P zeigt auf einen Teilbaum– R ist das kleinste umschließende Rechteck dieses Teilbaums

Beachte• Rechtecke können sich überlappen• Struktur des R-Baums hängt von Reihenfolge des Einfügens

ab• Jedes Paar (R,O) kommt genau einmal vor• R kann mehrere umschließenden Rechtecke schneiden


55 55

Einfügen in einen R-Baum

• Ausgangspunkt: Einfügen eines neuen Knotens in einen B-Baum

• Problem hier: an welche Stelle wird (R,O) eingefügt?– Durchlaufe den R-Baum mit der Wurzel als Ausgangspunkt– Wähle an jedem inneren Knoten den Teilbaum, der

durch Einfügen von R minimal vergrößert würde– Füge (R,O) schließlich als Blatt ein– Beim Überlauf verfahre wie beim B-Baum

• Besonderheit gegenüber B-Baum:– Es gibt keine lineare Ordnung zwischen den Einträgen der

Knoten– Verschiedene Stragegien zum Spalten eines Knotens


56 56

Strategien zum Spalten eines Knotens

Minimierung derGesamtfläche

Minimierung desDurchschnitts


57 57

E H

Suchen eines Knotens

A

B

D

G

J F

CI

3 4

1 2

A I E H

5

B C D

6

J F G

6

4

21

35

In welchem R liegt Q?


58 58

E H


A

B

D

G

J F

CI

3 4

1 2

A I E H

5

B C D

6

J F G

6

4

21

35


59 59

E H


A

B

D

G

J F

CI

3 4

1 2

A I E H

5

B C D

6

J F G

6

4

21

35


60 60

E H


A

B

D

G

J F

CI

3 4

1 2

A I E H

5

B C D

6

J F G

6

4

21

35


61 61

E H


A

B

D

G

J F

CI

3 4

1 2

A I E H

5

B C D

6

J F G

6

4

21

35


62 62

E H


A

B

D

G

J F

CI

3 4

1 2

A I E H

5

B C D

6

J F G

6

4

21

35


63 63

Nachteil des R-Baums

• Um das richtige Blatt zu finden, sind meist mehrere Durchläufe erforderlich

• Dies gilt insbesondere dann, wenn die Suche erfolglos ist

• Abhilfe: R+-Baum


64 64

Alternative: Der R+-Baum

• Alle inneren Rechtecke sind disjunkt• Ein Objekt / umschließendes Rechteck kann in

mehreren Blättern vorkommen• Jedes Blatt repräsentiert den Teil von (R,O), der von

dem Vaterknoten umschlossen wird


65 65

R+-Baum

E H

A

B

D

G

J F

CI

12

3

4

5

6

7

8

9

2 31

4 5

A E D E H

6 7

B D I B C D

8 9

E G F J


66 66

R+-Baum

1 2

E H

A

B

D

G

J F

CI

12


67 67

R+-Baum

21 3

E H

A

B

D

G

J F

CI

12

3


68 68

R+-Baum

2 31

4

A E

E H

A

B

D

G

J F

CI

12

4

3


69 69

R+-Baum

2 31

4 5

A E D E H

E H

A

B

D

G

J F

CI

12

4

5

3


70 70

R+-Baum

6

2 31

4 5

A E D E H

E H

A

B

D

G

J F

CI

12

4

5

6

B D I

3


71 71

R+-Baum

76

2 31

4 5

A E D E H

E H

A

B

D

G

J F

CI

12

4

5

6

B D I

7

B C D

3


72 72

R+-Baum

8E H

A

B

D

G

J F

CI

12

3

4

5

6

7

2 31

4 5

A E D E H

6 7

B D I B C D

8

E G


73 73

R+-Baum

9E H

A

B

D

G

J F

CI

12

3

4

5

6

7

2 31

4 5

A E D E H

6 7

B D I B C D

88

E G

9

F J


74 74

R+-Baum

E H

A

B

D

G

J F

CI

12

3

4

5

6

7

8

9

2 31

4 5

A E D E H

6 7

B D I B C D

8 9

E G F J


75 75

Suche im R+-Baum

E H

A

B

D

G

J F

CI

12

3

4

5

6

7

8

9

2 31

4 5

A E D E H

6 7

B D I B C D

8 9

E G F J

Documents

Institut für Kartographie und Geoinformation Prof. Dr. Lutz Plümer Geoinformation III Vorlesung 3 WS 01/02 Punkt-in-Polygon-Verfahren III (R/R + -Baum)