Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Geoinformation III

Quadtrees

Vorlesung 3

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 191

• Rasterstruktur• Raster• Quadtrees• Region quadtree

– Unterteilung– Aufbau

• Unterteilung der Rasterstruktur• Varianten des Quadtrees• Punkte• Punktstruktur

Übersicht I

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 192

• Point quadtree– Knotenstruktur– Aufbau

• Landkarte• Motivation des PM-Quadtrees• Ein Quadtree für Maschen

• PM1 quadtree

• Punkt- in-Landkarte

Übersicht II

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 193

Rasterstruktur

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 194

• zweidimensionales Array– Einträge: Pixel– Adressierung durch Index von Reihe und Spalte

• aber auch:– regelmäßige Tessellation (Landkarte) mit quadratischen Maschen

gleicher Größe• Modellierung von Feldern

– siehe GIS I, Felder und Objekte– sehr effiziente Speicherung– Ausgangspunkt der Bildverarbeitung / Photogrammetrie

Raster

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 195

Quadtrees

• Baum• jeder Knoten hat 0 oder 4 Nachfolger

– Nordwest– Nordost– Südwest– Südost

• Blattknoten sind homogen• Konstruktion eines Quadtrees für ein gegebenes Raster

A 1x

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 196

Region quadtree - Unterteilung

A 6x

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 196

Region quadtree - Unterteilung

A 6x

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 197

Region quadtree - Aufbau

A 34x

inhomogen

inhomogen

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 197

Region quadtree - Aufbau

A 34x

SWSONW

NW NO

SW SO

NO

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 197

Region quadtree - Aufbau

A 34x

SWSONW

NW NO

SW SO

NO

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 197

Region quadtree - Aufbau

A 34x

SWSONW

NW NO

SW SO

NO

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 197

Region quadtree - Aufbau

A 34x

SWSONW

NW NO

SW SO

NO

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 197

Region quadtree - Aufbau

A 34x

SWSONW

NW NO

SW SO

NO

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 197

Region quadtree - Aufbau

A 34x

SWSONW

NW NO

SW SO

NO

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 197

Region quadtree - Aufbau

A 34x

SWSONW

NW NO

SW SO

NO

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 197

Region quadtree - Aufbau

A 34x

SWSONW

NW NO

SW SO

NO

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 197

Region quadtree - Aufbau

A 34x

SWSONW

NW NO

SW SO

NO

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 197

Region quadtree - Aufbau

A 34x

SWSONW

NW NO

SW SO

NO

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 198

Unterteilung der Rasterstruktur

A 1x

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 198

Unterteilung der Rasterstruktur

A 1x

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Varianten des Quadtrees

• für Punkte• für Polygone

9

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1910

Punkte

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1911

Punktstruktur

1

2

3

4

5

6

7

8

9

10

11

12 13

14

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1912

Point quadtree - Knotenstruktur

A 3x

X Y NW NO SW SO Daten

X Y NW NO SW SO Daten

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913

Point quadtree - Aufbau

A 24x

1

1NW NO

SW SO

NW NO SW SO

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913

Point quadtree - Aufbau

A 24x

1

1

2

2

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913

Point quadtree - Aufbau

A 24x

1

1

2

21

2

3

3

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913

Point quadtree - Aufbau

A 24x

1

1

2

21

2

3

31

2

3

4

4

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913

Point quadtree - Aufbau

A 24x

1

1

2

21

2

3

31

2

3

4

4

1

2

4

5

3

5

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1913

Point quadtree - Aufbau

A 24x

1

1

2

21

2

3

31

2

3

4

4

1

2

4

5

3

5

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1914

Landkarte

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1915

• in folgenden Fällen ist leicht zu entscheiden, zu welcher Masche ein Punkt gehört:

A 2x

Motivation des PM-Quadtrees

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1916

Ein Quadtree für Maschen

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1917

1. wie beim Quadtree wird die Ebene in Quadrate zerlegt2. statt der Homogenitätsforderung gilt hier:

1. Jedes Blatt des Quadtrees repräsentiert ein Quadrat, das höchstens einen Knoten enthält.

2. Ein Blatt, das einen Knoten enthält, darf nur Kanten enthalten, die zu diesem Knoten inzident sind

3. Ein Blatt, das keinen Punkt enthält, darf höchstens einen Teil einer Kante enthalten

3. sind diese Bedingungen nicht erfüllt, wird das zugeordnete Quadrat in 4 gleich große Quadrate geteilt

PM1 quadtree

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1918

PM1 quadtree

A 12x

1. Jedes Blatt des Quadtrees repräsentiert ein Quadrat, das höchstens einen Knoten enthält.

2. Ein Blatt, das einen Knoten enthält, darf nur Kanten enthalten, die zu diesem Knoten inzident sind

3. Ein Blatt, das keinen Punkt enthält, darf höchstens einen Teil einer Kante enthalten.

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1918

PM1 quadtree

A 12x

1. Jedes Blatt des Quadtrees repräsentiert ein Quadrat, das höchstens einen Knoten enthält.

2. Ein Blatt, das einen Knoten enthält, darf nur Kanten enthalten, die zu diesem Knoten inzident sind

3. Ein Blatt, das keinen Punkt enthält, darf höchstens einen Teil einer Kante enthalten.

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1918

PM1 quadtree

A 12x

1. Jedes Blatt des Quadtrees repräsentiert ein Quadrat, das höchstens einen Knoten enthält.

2. Ein Blatt, das einen Knoten enthält, darf nur Kanten enthalten, die zu diesem Knoten inzident sind

3. Ein Blatt, das keinen Punkt enthält, darf höchstens einen Teil einer Kante enthalten.

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1918

PM1 quadtree

A 12x

1. Jedes Blatt des Quadtrees repräsentiert ein Quadrat, das höchstens einen Knoten enthält.

2. Ein Blatt, das einen Knoten enthält, darf nur Kanten enthalten, die zu diesem Knoten inzident sind

3. Ein Blatt, das keinen Punkt enthält, darf höchstens einen Teil einer Kante enthalten.

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1918

PM1 quadtree

A 12x

1. Jedes Blatt des Quadtrees repräsentiert ein Quadrat, das höchstens einen Knoten enthält.

2. Ein Blatt, das einen Knoten enthält, darf nur Kanten enthalten, die zu diesem Knoten inzident sind

3. Ein Blatt, das keinen Punkt enthält, darf höchstens einen Teil einer Kante enthalten.

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1918

PM1 quadtree

A 12x

1. Jedes Blatt des Quadtrees repräsentiert ein Quadrat, das höchstens einen Knoten enthält.

2. Ein Blatt, das einen Knoten enthält, darf nur Kanten enthalten, die zu diesem Knoten inzident sind

3. Ein Blatt, das keinen Punkt enthält, darf höchstens einen Teil einer Kante enthalten.

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1918

PM1 quadtree

A 12x

1. Jedes Blatt des Quadtrees repräsentiert ein Quadrat, das höchstens einen Knoten enthält.

2. Ein Blatt, das einen Knoten enthält, darf nur Kanten enthalten, die zu diesem Knoten inzident sind

3. Ein Blatt, das keinen Punkt enthält, darf höchstens einen Teil einer Kante enthalten.

Geoinformation31 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1919

Punkt- in-Landkarte

Sie haben drei Verfahren kennengelernt:• Zerlegung der Maschen in Streifen (Trapeze)• Bounding Boxes• PM-Quadree

– Zerlegung der Ebene in Quadrate

• Grundsätzlicher Unterschied– Zerlegung des Objekts und Aufbau einer Zugriffsstruktur für das

Objekt• Trapezverfahren

– Zerlegung des Raumes (der Ebene) und Schaffung einer Zugriffsstruktur für den Raum• PM-Quadtree