GIS Funktionalität I: Distanz- und Bufferanalysen

GIS Funktionalität I:GIS Funktionalität I:

Distanz- Distanz- und Bufferanalysenund Bufferanalysen

InhaltInhalt

11 Einleitung & Fallbeispiel Einleitung & Fallbeispiel

22 Modellierung von GrundlagenModellierung von Grundlagen

33 shortest Path Analysen shortest Path Analysen

44 Distanzanalysen im Netzwerk Distanzanalysen im Netzwerk

55 Buffering Buffering

66 Literatur Literatur

1 Fallbeispiel1 Fallbeispiel

www.jsi.comwww.jsi.com

2 Modellierung von Graphen2 Modellierung von Graphen

- Planarer Graph: kann auf einer Ebene abgebildet - Planarer Graph: kann auf einer Ebene abgebildet werden werden

- Knoten: Punkte- Knoten: Punkte

- Kanten: Linien - Kanten: Linien

- Weg: zusammenhängende Folge von Kanten, die über - Weg: zusammenhängende Folge von Kanten, die über Knoten verbunden sindKnoten verbunden sind

- Für zusammenhängende Graphen gilt: 2 = V – E + P - Für zusammenhängende Graphen gilt: 2 = V – E + P

De Lange (2002: 94)De Lange (2002: 94)


Gewichtung von GraphenGewichtung von Graphen

- sog. Widerstandswerte - sog. Widerstandswerte - Modellierung einseitig - Modellierung einseitig oder beidseitigoder beidseitig- Analytische Darstellung in- Analytische Darstellung in Matrixform Matrixform

gewichteter Graph. Nach Bill gewichteter Graph. Nach Bill (1999:29) (1999:29)


BewertungsmatrixBewertungsmatrix

- Knoten- Kantendarstellung- Knoten- Kantendarstellung

- Anfangsknoten: Zeilen - Anfangsknoten: Zeilen

- Endknoten: Spalten - Endknoten: Spalten

- Widerstandswert 0: keine- Widerstandswert 0: keine

Verbindung Verbindung

A B C D E

A 0 7 0 6 0

B 0 0 0 0 1

C 0 0 0 0 0

D 0 0 5 0 0

E 3 0 1 2 0


Inzidenzmatrix Inzidenzmatrix

- Beziehungen zwischen - Beziehungen zwischen

verschiedenen Elementen desverschiedenen Elementen des

GraphenGraphen

- Anfangsknoten: 1 - Anfangsknoten: 1

- Endknoten: -1 - Endknoten: -1

- Nicht inzidente Knoten: 0- Nicht inzidente Knoten: 0

A B C D E

1 1 -1 0 0 0

2 1 0 0 -1 0

3 0 1 0 0 -1

4 -1 0 0 0 1

5 0 0 -1 0 1

6 0 0 0 -1 1

7 0 0 -1 1 0


Adjazenzmatrix Adjazenzmatrix

- Beziehungen zwischen - Beziehungen zwischen

gleichartigen Elementengleichartigen Elementen

- Hauptdiagonale: Anzahl - Hauptdiagonale: Anzahl derder

Kanten, die von diesemKanten, die von diesem

Knoten abgehenKnoten abgehen

- Endknoten: -1- Endknoten: -1

A B C D E

A 3 -1 0 -1 -1

B -1 2 0 0 -1

C 0 0 2 -1 -1

D -1 0 -1 3 -1

E -1 -1 -1 -1 4

3 shortest Path Analysen3 shortest Path Analysen

- Distanzanalysen zwischen verschiedenen Objekten - Distanzanalysen zwischen verschiedenen Objekten

- Unter Berücksichtigung exogener und endogener Variablen - Unter Berücksichtigung exogener und endogener Variablen

- exogene Variablen können als Widerstandswerte in das - exogene Variablen können als Widerstandswerte in das Modell mit einfließenModell mit einfließen

- Verarbeitung der Informationen durch Algorithmen: - Verarbeitung der Informationen durch Algorithmen:

„ „ Ein Algorithmus ist eine allgemeine Berechnungsvorschrift Ein Algorithmus ist eine allgemeine Berechnungsvorschrift zur Lösung eines Problems, die sich aus mehreren zur Lösung eines Problems, die sich aus mehreren elementaren Schritten zusammensetzt, die in einer festen elementaren Schritten zusammensetzt, die in einer festen Reihenfolge ausgeführt werden.“ Reihenfolge ausgeführt werden.“

De Lange (2002: 81)De Lange (2002: 81)


Dijkstra Algorithmus Dijkstra Algorithmus

- Kürzeste Wege von einem festgelegten - Kürzeste Wege von einem festgelegten

Startknoten zu allen anderen Knoten Startknoten zu allen anderen Knoten

- Teilmengen:- Teilmengen:

1)1) Menge der Knoten T, die schon zur Menge der Knoten T, die schon zur RouteRoute

dazugehören dazugehören

2)2) Menge der von Kandidaten K, die Menge der von Kandidaten K, die einemeinem

Knoten der Route benachbart sind, Knoten der Route benachbart sind, aber aber

noch nicht zur Route hinzugehören. noch nicht zur Route hinzugehören.

3)3) Menge der unberücksichtigten Knoten Menge der unberücksichtigten Knoten

www.irf.dewww.irf.de


Dijkstra AlgorithmusDijkstra Algorithmus

GG Graph Graph

SS Startknoten Startknoten

ZZ ZielknotenZielknoten

[v1…v2][v1…v2] Menge aller Verbindungsknoten inkl. ZMenge aller Verbindungsknoten inkl. Z

Distanz (u,v)Distanz (u,v) Kantenlängen zwischen den Knoten u Kantenlängen zwischen den Knoten u und vund v

Q_SucheQ_Suche Liste über die noch nicht untersuchten Knoten Liste über die noch nicht untersuchten Knoten

Q_Distanz[v]Q_Distanz[v] Liste der bisher gefundenen Distanzen Liste der bisher gefundenen Distanzen von S zu vvon S zu v

Q_Vorgänger[v]Q_Vorgänger[v] Liste über den Vorgängerknoten für Liste über den Vorgängerknoten für jeden jeden erledigten Knoten v erledigten Knoten v


Dijkstra Algorithmus – Dijkstra Algorithmus – Initialisierung Initialisierung

Q_Suche Q_Suche = S + [v1…vn] – Z; = S + [v1…vn] – Z; Q_ErledigtQ_Erledigt = leer;= leer;

Für jeden Knoten vFür jeden Knoten v Q_Distanz[v] = unendlich; Q_Distanz[v] = unendlich; Q_Vorgänger[v] = leer; Q_Vorgänger[v] = leer;

Q_Distanz[S] = 0; Q_Distanz[S] = 0; Q_Vorgänger[S] = leer;Q_Vorgänger[S] = leer;

a b

c

ZS

1

1

1

2 2

Zeit Q_Distanz Q_Vorgänger Q_Suche Q_Erledigt

S a b c Z S a b c Z

0 0 - - - - 0 - - - - S, a, b, c -

www.irf.dewww.irf.de


Dijkstra Algorithmus – SucheDijkstra Algorithmus – Suche

Solange (Q_Suche != leer)Solange (Q_Suche != leer)

Sortiere Q_Suche nach Q_Distanz[v], v ist Knoten aus Sortiere Q_Suche nach Q_Distanz[v], v ist Knoten aus Q_Suche;Q_Suche;

Extrahiere Knoten u aus Q_Suche mit Q_Distanz = Extrahiere Knoten u aus Q_Suche mit Q_Distanz = minimal;minimal;

Streiche u aus Q_Suche;Streiche u aus Q_Suche;

Addiere u zu Q_Erledigt;Addiere u zu Q_Erledigt;Zeit Q_Distanz Q_Vorgänger Q_Suche Q_Erledigt

S a b c Z S a b c Z

0 0 - - - - 0 - - - - S, a, b, c -

1 0 1 - 2 - 0 S - S - a, b, c S

2 0 1 2 2 - 0 S a S - b, c S, a

3 shortest Path Analysen3 shortest Path AnalysenDijkstra Algorithmus – SucheDijkstra Algorithmus – Suche

Für jeden Knoten v, der Nachbar von u istFür jeden Knoten v, der Nachbar von u ist

Wenn (Q_Distanz[v] > Q_Distanz[u] + Distanz(u,v))Wenn (Q_Distanz[v] > Q_Distanz[u] + Distanz(u,v))

Q_Distanz[v] = Q_Distanz[u] + Distanz(u,v);Q_Distanz[v] = Q_Distanz[u] + Distanz(u,v);

Q_Vorgänger[v] = u;Q_Vorgänger[v] = u;

Zeit Q_Distanz Q_Vorgänger Q_Suche Q_Erledigt

S a b c Z S a b c Z

0 0 - - - - 0 - - - - S, a, b, c -

1 0 1 - 2 - 0 S - S - a, b, c S

2 0 1 2 2 - 0 S a S - b, c S, a

3 0 1 2 2 3 0 S a S b c S, a, b

4 0 1 2 2 3 0 S a S b - S, a, b, c


Dijkstra Algorithmus – Dijkstra Algorithmus – AusgabeAusgabe

Gebe aus: Z; Gebe aus: Z;

U = Z; U = Z;

Solange (u != leer) Solange (u != leer)

u = Q_Vorgänger[u];u = Q_Vorgänger[u];

Gebe aus: u; Gebe aus: u;

a b

c

ZS

1

1

1

2 2

www.hunter-gis.com


Floyd AlgorithmusFloyd Algorithmus

- Berechnet kürzesten Weg von jedem Knoten aus - Berechnet kürzesten Weg von jedem Knoten aus

- Sonderfall Warshall Algorithmus: arbeitet ohne - Sonderfall Warshall Algorithmus: arbeitet ohne

Widerstandswerte Widerstandswerte

4 Distanzanalysen im Netzwerk4 Distanzanalysen im Netzwerk

Einzugsgebiete Einzugsgebiete

- - Berechnung von maximalBerechnung von maximal

zulässigen Distanzen entlangzulässigen Distanzen entlang

vorgegebener Routen vorgegebener Routen


RundreiseproblemRundreiseproblem

- Berechnung durch den „Banch - Berechnung durch den „Banch and Bound“ Algorithmusand Bound“ Algorithmus

- Problematik: Planung der - Problematik: Planung der Route, so dass jeder Punkt nur Route, so dass jeder Punkt nur einmal erreicht wird einmal erreicht wird (ausgenommen Startpunkt) (ausgenommen Startpunkt)

- Weg soll minimiert werden - Weg soll minimiert werden

Depot (1)4

2

3

13

1220

11

3010


1 2 3 4

1 20 10 13

2 20 11 12

3 10 11 30

4 13 12 30

Rundreiseproblem

W1

= W1(E(1,2), E(2,3), E(3,4), E(4,1)) = E(1,2) + E(2,3) + E(3,4) + E(4,1)

= 20 + 11 + 30 + 13 = 74

De Lange (2002: 98)De Lange (2002: 98)

5 Buffering 5 Buffering

- Buffer sind im Durchmesser - Buffer sind im Durchmesser fest definierte Flächen, die fest definierte Flächen, die um Punkte, Linien oder um Punkte, Linien oder Polygone gelegt werdenPolygone gelegt werden

- Unterschiedliche Modellierung - Unterschiedliche Modellierung im im

Raster- und Vektorenmodellen Raster- und Vektorenmodellen

www.providenceplan.org

5 Buffering5 Buffering

Zonengenerierung im Vektormodell Zonengenerierung im Vektormodell

- Unterscheidung in kreisförmige und rechteckige Buffer - Unterscheidung in kreisförmige und rechteckige Buffer - Bei Linienpuffer: Parallelengenerierung- Bei Linienpuffer: Parallelengenerierung- Modellierung von Linien- und Flächenbuffer sind gleichzusetzen - Modellierung von Linien- und Flächenbuffer sind gleichzusetzen

Bill (1999: 33)Bill (1999: 33)


Zonengenerierung im VektormodellZonengenerierung im Vektormodell

www.rockynet.com






Zonengenerierung im RasterdatenformatZonengenerierung im Rasterdatenformat

- Klassifizierung: Raster innerhalb der Buffer-- Klassifizierung: Raster innerhalb der Buffer-

zone werden mit den selben Attributeigenschaften zone werden mit den selben Attributeigenschaften belegtbelegt

- Abstandstransformation: Raster werden je nach - Abstandstransformation: Raster werden je nach AbstandAbstand

zum Objekt mit unterschiedlichen Attributen zum Objekt mit unterschiedlichen Attributen versehen versehen


* * * * * * * * * * *

* * * * * * * * * * *

* * * * 0 0 0 * * * *

* * * 0 * * * 0 * * *

* * * 0 * * * * * * *

* * * * 0 0 0 * * * *

* * * * * * * 0 * * *

* * * 0 * * * 0 * * *

* * * * 0 0 0 * * * *

* * * * * * * * * * *

* * * * * * * * * * *

* * * * * * * * * * *

Originalmatrix Originalmatrix Abstandstransformation Abstandstransformation

3 3 2 2 2 2 2 2 2 3 3

3 2 2 1 1 1 1 1 2 2 3

3 2 1 1 0 0 0 1 1 2 3

3 2 1 0 1 1 1 0 1 2 3

3 2 1 0 1 1 1 1 1 2 3

3 2 1 1 0 0 0 1 1 2 3

3 2 1 1 1 1 1 0 1 2 3

3 2 1 0 1 1 1 0 1 2 3

3 2 1 1 0 0 0 1 1 2 3

3 2 2 1 1 1 1 1 2 2 3

3 3 2 2 2 2 2 2 2 3 3

4 3 3 3 3 3 3 3 3 3 4


euklidische Distanz euklidische Distanz Manhattandistanz Manhattandistanz

3 3 2 2 2 2 2 2 2 3 3

3 2 2 1 1 1 1 1 2 2 3

3 2 1 1 0 0 0 1 1 2 3

3 2 1 0 1 1 1 0 1 2 3

3 2 1 0 1 1 1 1 1 2 3

3 2 1 1 0 0 0 1 1 2 3

3 2 1 1 1 1 1 0 1 2 3

3 2 1 0 1 1 1 0 1 2 3

3 2 1 1 0 0 0 1 1 2 3

3 2 2 1 1 1 1 1 2 2 3

3 3 2 2 2 2 2 2 2 3 3

4 3 3 3 3 3 3 3 3 3 4

6 5 4 3 2 2 2 3 4 5 6

5 4 3 2 1 1 1 2 3 4 5

4 3 2 1 0 0 0 1 2 3 4

3 2 1 0 1 1 1 0 1 2 3

3 2 1 0 1 1 1 1 2 3 4

4 3 2 1 0 0 0 1 2 3 4

4 3 2 1 1 1 1 0 1 2 3

3 2 1 0 1 1 1 0 1 2 3

4 3 2 1 0 0 0 1 2 3 4

5 4 3 2 1 1 1 2 3 4 5

6 5 4 3 2 2 2 3 4 5 6

7 6 5 4 3 3 3 3 3 6 7


ReklassifizierungReklassifizierung

- Vermeidung von Redundanzen - Vermeidung von Redundanzen

- Zusammenfassung von Rasterzellen mit- Zusammenfassung von Rasterzellen mit

unterschiedlichen Attributen zu einheitlichen unterschiedlichen Attributen zu einheitlichen Klassen Klassen

6 Literatur6 Literatur ► Bill R. (1999): Grundlagen der Geo-Informationssysteme. Band 1. Bill R. (1999): Grundlagen der Geo-Informationssysteme. Band 1.

Heidelberg. Heidelberg. ► Bill R. (1999): Grundlagen der Geo-Informationssysteme. Band 2. Bill R. (1999): Grundlagen der Geo-Informationssysteme. Band 2.

Heidelberg. Heidelberg. ► Castle(1993): Profiting from a Geographic Information System. Castle(1993): Profiting from a Geographic Information System.

Fort Collins. Fort Collins. ► De Lange N. (2002): Geoinformatik in Theorie und Praxis. De Lange N. (2002): Geoinformatik in Theorie und Praxis. Berlin. Berlin. ► Heywood I., S. Cornelius & Carver S. (2002): An Introduction To Heywood I., S. Cornelius & Carver S. (2002): An Introduction To

Geographical Geographical Information Systems. Harlow. Information Systems. Harlow.

► Laurini R. & D. Thompson (1992): Fundamentals of Spatial Laurini R. & D. Thompson (1992): Fundamentals of Spatial Informations Systems. London. Informations Systems. London.

► Longley P.A., M.F. Goodchild, D.J. Maguire & D.W. RhindLongley P.A., M.F. Goodchild, D.J. Maguire & D.W. Rhind(2001): Geographic Information Systems and Science. Chichster. (2001): Geographic Information Systems and Science. Chichster.

► YeungYeung (2002):(2002): Concepts and techniques of Geographic Concepts and techniques of Geographic Information System. New Jersey. Information System. New Jersey.

► Freund E. (2004): Institut für Roboterforschung. www.irf.de. Freund E. (2004): Institut für Roboterforschung. www.irf.de. ► JSI Research & Training Institute, Inc. JSI Research & Training Institute, Inc. (2004): www.jsi.com.(2004): www.jsi.com.► Lange W. & D Exner (2004): Institut für Medieninformatik und Lange W. & D Exner (2004): Institut für Medieninformatik und

technische Informatik. FH Flensburg. www.iti.fh-flensburg.de.technische Informatik. FH Flensburg. www.iti.fh-flensburg.de.

Documents

GIS Funktionalität I: Distanz- und Bufferanalysen