Die bisherigen Kostenentfernungswerkzeuge werden durch die Werkzeuge "Entfernungsakkumulation" und "Entfernungsallokation" ersetzt. Mit diesen neuen Werkzeugen wird die Kostenentfernung in alle Richtungen gemessen, indem eine kontinuierliche akkumulative Oberfläche rekonstruiert, und nicht nach Routen durch ein Netzwerk aus Zellenmittelpunkten gesucht wird. Ausgabe-Oberflächen der akkumulativen Kosten können aus Eingabekostenoberflächen (Reibung) und anderen Parametern erstellt werden. Wie bei anderen Oberflächen werden die Ergebnisse besser verständlich, wenn Konturlinien (Linien der gleichen akkumulativen Kosten) hinzugefügt und die Ergebnisse in 3D und zusammen mit Allokationsabflussgebieten visualisiert werden. In der Regel sollen durch die Konstruktion dieser Oberfläche die kostengünstigsten Routen dargestellt werden. Dabei handelt es sich um Routen des steilsten Gefälles.
Oberfläche der akkumulativen Kosten
Mit dem von diesen Werkzeugen verwendeten Algorithmus wird aus der Neigung eine Oberfläche rekonstruiert.
Oberflächenrekonstruktionsansatz
Mit den Werkzeugen Entfernungsakkumulation und Entfernungsallokation ist die Suche nach den geringsten akkumulativen Kosten kein Netzwerkproblem mehr. Beim Ausgabe-Raster für akkumulative Kosten handelt es sich um eine Oberfläche mit einer unbekannten Form. Sie möchten in den einzelnen Zellen des Untersuchungsgebiets die Form ermitteln, von der nur die Neigung gegeben ist. Bei diesem Ansatz werden Konzepte aus der Differenzialgeometrie verwendet, um die tatsächlichen Entfernungen und Kosten in alle Richtungen zu berechnen.
Mit der Oberfläche der akkumulativen Kosten werden drei wichtige Fragen beantwortet:
- Wo steigen die Kosten in Abhängigkeit von der Entfernung rasch an?
- Welche Quellenzellen liegen am nächsten zu einer gegebenen Nicht-Quellenzelle?
- Welche Route sollte von einer Nicht-Quellenzelle zur nächstgelegenen Quellenzelle verwendet werden?
Wenn Sie 3D-Ansichten und Konturlinien für die Ausgabe-Oberfläche verwenden, finden Sie die Antworten auf diese Fragen. Präzisere Antworten erhalten Sie mit den Werkzeugen Entfernungsallokation und Optimaler Pfad als Linie.
In den folgenden Unterabschnitten wird die Beziehung zwischen einer einfachen Eingabekostenoberfläche (Reibung) und der Ausgabe-Oberfläche der akkumulativen Kosten beschrieben.
Einfache Eingabekostenoberfläche (Reibung)
Betrachten wir ein einfaches Kosten-Raster (Reibung) mit einem zentralen Abschnitt mit Kosten = 3, einem mittleren Abschnitt mit Kosten = 2 und einem äußeren Abschnitt mit Kosten = 1.
Mit der 3D-Interpretation lässt sich die Beziehung zwischen dem Kosten-Raster (Reibung) und der Ausgabe-Oberfläche der akkumulativen Kosten erkennen. Die Höhe h der Oberfläche bei Zelle c ist die Summe der Neigungen aus dem Eingabe-Kosten-Raster multipliziert mit den Entfernungen, über die diese Neigungen aktiv sind (h = 3 * d1 + 2 * d2 + 1 * d3).
In einer Draufsicht auf dieselbe Ausgabe-Oberfläche wird mit Konturlinien dargestellt, wie sich die akkumulativen Kosten ändern. Die Neigungs- und Ausrichtungswerte an der Zellenposition c sind ebenfalls dargestellt. Die Ausrichtung (Richtung des steilsten Gefälles) steht immer im rechten Winkel zur Konturlinie.
Einbinden der geringsten akkumulativen Kosten
Im Folgenden ist ein etwas komplizierterer Fall dargestellt. Die akkumulativen Kosten (Höhe) bei einer Nicht-Quellenzelle stammen von der Quelle, die bei dieser Zelle mit den geringsten Kosten ankommt.
Das Kosten-Raster weist zwei Werte auf: 1 in Hellgrau und 3 in Dunkelgrau. S1 und S2 sind die Quellpunkte. Nicht-Quellenzelle D liegt in Bezug auf die akkumulativen Kosten näher bei S1.
Durch Hinzufügen von Konturlinien zur Oberfläche der akkumulativen Kosten können Sie visualisieren, wie schnell sich Kosten mit zunehmender Entfernung von der Quellen ändern. Sie beginnen bei der Nicht-Quellenposition und kehren im rechten Winkel zu den Konturlinien zur nächstgelegenen Quellenzelle zurück. Die Route führt aufgrund der hohen Kosten in der Nähe der geometrisch nächstgelegenen Quelle nicht zu dieser Quelle zurück.
Im Folgenden ist eine 3D-Ansicht mit derselben Oberfläche der geringsten akkumulativen Kosten dargestellt. Die Oberfläche ist um die kostspielige Quelle herum wesentlich steiler (Kosten akkumulieren schneller). Diese Quelle besitzt die Oberfläche mit den geringsten Kosten ganz in der Nähe. In allen anderen Zellen im Untersuchungsgebiet ist die Quelle links der Besitzer der Oberfläche.
Allokationsregionen als Abflussgebiete
Wenn die Eingabekostenoberfläche (Reibung) und die Ausgabe-Oberfläche der akkumulativen Kosten komplexer werden, können Sie immer noch Konturlinien, Neigung und Ausrichtung verwenden, um sich einen Überblick über das Verhalten der Oberflächen der akkumulativen Kosten zu verschaffen. Darüber hinaus dienen die Allokationsregionen in der Nähe von Quellen als Abflussgebiete auf der Ausgabe-Oberfläche der akkumulativen Kosten. Alle kostengünstigsten Routen in einer Allokationsregion führen zur gleichen Quelle. In den folgenden Beispielen werden Allokationsabflussgebiete mit Konturlinien und einer 3D-Ansicht kombiniert.
Kompliziertere Oberflächen der akkumulativen Kosten wie diese Fahrzeit-Oberfläche können mithilfe von Konturlinien (in diesem Fall mithilfe von Isochronen) in 2D und 3D präzise visualisiert werden.
In der folgenden Abbildung ist eine 3D-Ansicht derselben Oberfläche dargestellt. Die Klippen im Hintergrund sind Barrieren, die durch das Vorhandensein eines Flusses verursacht werden.
Die kostengünstigsten Routen führen wie in der folgenden Abbildung auf der Oberfläche der akkumulativen Kosten nach unten in Richtung der Quelle, die die Allokationszone (Abflussgebiet) definiert:
Der Algorithmus zur Oberflächenrekonstruktion ist eine Erweiterung des Netzwerkalgorithmus.
Wenn Sie eine Oberfläche der akkumulativen Kosten allein mit der Kenntnis des Wertes für die steilste Neigung für die einzelnen Zellen ermitteln möchten, können Sie auch den Algorithmus zur Oberflächenrekonstruktion verwenden. Dieser Algorithmus ähnelt dem von bisherigen Kostenentfernungswerkzeugen verwendeten Algorithmus für die kürzeste Route. Er enthält jedoch einen zusätzlichen Schritt zum Bereitstellen einer Näherung der akkumulativen Kosten, die keiner der acht Netzwerkrichtungen folgt. Dieser Schritt wird als Eikonal-Schritt bezeichnet. Es folgt eine kurze Beschreibung. Ausführlichere Informationen hierzu finden Sie in Sethian, 1999.
Zur Betrachtung dieses Schrittes im Zusammenhang sind im Folgenden die akkumulativen Kosten z5 für die mittlere Zelle dargestellt. Angenommen, alle benachbarten akkumulativen Kosten zi sind bekannt. Darüber hinaus ist aus dem Eingabe-Kosten-Raster auch der Neigungswert S bei der mittleren Zelle bekannt.
Eine Näherung für z5 kann beispielsweise wie in der folgenden Abbildung entlang der Diagonalen zwischen z3 und z5 verlaufen, wobei z5 = z3 + 1,4 * Zellengröße * S gilt. In diesem Fall wird S, also der Wert aus dem Eingabe-Kosten-Raster, als die Neigung des Dreiecks abc interpretiert. Bei all diesen Näherungen im Netzwerk wird nur die Neigung bei z5 verwendet, um sich den akkumulativen Kosten bei z5 zu nähern. Dies ist ein Unterschied zum bisherigen Netzwerkalgorithmus, bei dem ein Durchschnitt von Kosten aus Zellenpaaren verwendet wird.
Es können acht Netzwerknäherungen berechnet werden, darunter vier, bei denen wie in der Sequenz der folgenden drei Abbildungen Paare vorhandener Höhen verwendet werden. In diesem Fall wird der Wert des Eingabe-Kosten-Rasters an der Position von Zelle z5 als die Magnitude S des Gradienten der Ebene interpretiert, die durch die beiden bekannten Punkte und die unbekannte Höhe z5 verläuft. Aus dieser Beziehung lässt sich z5 ermitteln. Dieser Schritt ist der Eikonal-Schritt.
Die Magnitude des Gradienten der Ebene wird berechnet.
Die Richtung des Gradienten wird berechnet.
Mit dem Eikonal-Schritt werden auch die Ausrichtungsinformationen bei z5 ermittelt. Dies wird als Gegenrichtung bezeichnet.
Es gibt nun zwölf Näherungswerte für die Höhe bei der mittleren Zelle. Deren Minimum wird ausgewählt und als akkumulativer Kostenwert z5 für die mittlere Zelle gespeichert. Wenn Sie ein Gegenrichtungs-Raster angefordert haben, wird die Ausrichtung des Gradienten (wie im vorherigen Abschnitt beschrieben) an der entsprechenden Position im Ausgabe-Gegenrichtungs-Raster gespeichert.
Dieser Vorgang wird für eine Zelle jedes Mal wiederholt, wenn ein neuer Höhenwert für einen ihrer Nachbarn abgerufen wird. Schließlich ändern sich die Höhenwerte nicht mehr, und der Algorithmus wird beendet. Die Anfangshöhen werden von den Quellen bereitgestellt: Sie sind entweder null oder entsprechen dem Wert der initialen Akkumulation pro Quelle. Die Werte der anderen Anfangshöhen werden auf unendlich festgelegt. Ausführliche Informationen hierzu finden Sie in Sethian (1999). Die Esri-Implementierung davon ist eine Kombination der in Sethian (1999) und Zhao (2004) beschriebenen Techniken.
Zusammenfassend lässt sich sagen, dass mit diesen Schritten beginnend mit der Neigung der einzelnen Zellen sowohl die Höhe der Oberfläche der akkumulativen Kosten als auch die Richtung des steilsten Gefälles rekonstruiert werden.
Kostengünstigste Pfade
Die kostengünstigsten Routen führen über die Oberfläche der akkumulativen Kosten die steilste Richtung nach unten. Diese Richtung ist für eine Zelle in Abbildung 8 dargestellt. Diese Richtung wird für die einzelnen Zellen im Ausgabe-Gegenrichtungs-Raster gespeichert. Sie können das Werkzeug Optimaler Pfad als Linie mit dem Gegenrichtungs-Raster als Eingabe verwenden, um diese Routen beginnend bei einer beliebigen Nicht-Quellenzelle darzustellen.
In den folgenden Abbildungen ist eine geschwungene kostengünstigste Route dargestellt, die bei der blauen Nicht-Quellenzelle d rechts oben beginnt und zur unteren Quellenzelle s führt. Obwohl d näher an der oberen Quelle liegt, ist es aufgrund der hohen Kosten in der Nähe dieser Quelle kostengünstiger, der geschwungenen Route zu s zu folgen.
Ziel d wird durch das blaue Quadrat dargestellt. Die Route verläuft durch ein kostengünstigeres Gebiet zu der Quelle, die am kostengünstigsten erreicht werden kann. Dabei wird um die kostspielige Quelle ein Bogen gemacht.
Auch wenn die Bezeichnung nicht schlüssig erscheint, werden die Eingabepositionen für die Konstruktion der kostengünstigsten Route als Ziele bezeichnet. Die Quellen wurden für die Konstruktion der Oberfläche verwendet und sind die Positionen, an denen die kostengünstigsten Routen enden.
Anhand der Allokationszonen um die Quellen wird noch deutlicher, dass die kostengünstigste Route vom Ziel zur unteren Quelle und nicht zur oberen Quelle verläuft. Als Nächstes wird das ausgewählte Gebiet vergrößert, um darzustellen, wie die Zellenwerte im Gegenrichtungs-Raster interpretiert werden.
Das Linienraster, das die Mittelpunkte der Gegenrichtungszellen verbindet, ist in Dunkelgrau dargestellt. Die Zellengrenzen sind in Hellgrau und die Zellenwerte als Azimut-Pfeile dargestellt. Wenn die kostengünstigste Route Linienrasterlinien kreuzt, wird der Azimut in der in Gegenrichtung nächstgelegenen Zelle in Verlaufsrichtung zur Aktualisierung der Richtung verwendet. Am oberen Routenstützpunkt neben Zelle a wird der in a gespeicherte Wert der Gegenrichtung verwendet, um der Linie, die diesen Stützpunkt verlässt, eine Richtung zu geben. Die nächste zu kreuzende Linienrasterlinie liegt Zelle b am nächsten, sodass dieser Azimut beim Verlassen des zweiten Stützpunktes verwendet wird usw.
Zusammenfassend lässt sich sagen, dass die kostengünstigsten Routen in Zellenmittelpunkten beginnen und enden. Andere Routenstützpunkte können an beliebigen Stellen im Linienraster aus horizontalen und vertikalen Linien liegen, die durch die Zellenmittelpunkte verlaufen.
Berechnung der tatsächlichen Neigung
Die im vorherigen Abschnitt beschriebenen Neigungswerte stammen nicht unbedingt aus dem Eingabekostenraster (Reibung). Es gibt verschiedene andere Eingaben, die zusammen die vom Algorithmus zur Oberflächenrekonstruktion verwendete tatsächliche Neigung bestimmen. Eine ausführliche Beschreibung dieser Eingaben sowie eine Erläuterung dazu, wie wichtig es ist, die Bewegungsrichtung durch eine Zelle und die Verlaufsrichtung von oder zu einer Quelle zu berücksichtigen, finden Sie in anderen Artikeln. Hier wird beschrieben, wie die Eingaben vom Algorithmus zur Oberflächenrekonstruktion verwendet werden. Folgende Eingaben werden verwendet:
- Die Eingabe-Kosten (Reibung) C
- Die Eingabe-Oberfläche S
- Der Quellkostenmultiplikator M
- Die Funktion HF für den horizontalen Faktor
- Die Funktion VF für den vertikalen Faktor
Die vom Algorithmus zur Oberflächenrekonstruktion verwendete tatsächliche Neigung weist die folgende allgemeine Form auf:
Tatsächliche Neigung = C * S * M * HF * VF
Dieser Wert wird dann mit der Zellengröße oder sqrt(2) * Zellengröße multipliziert und mit einer vorhandenen Höhe addiert, um eine der Schätzwerte der Netzwerkrichtungshöhe zu erhalten. Um eine Höhenschätzung für den Eikonal-Schritt zu erhalten, wird eine kompliziertere Funktion der tatsächlichen Neigung verwendet.
Die tatsächliche Neigung muss Einheiten für die akkumulativen Kosten geteilt durch die lineare Entfernung, also für ein Verhältnis, aufweisen. Wenn Ihre Oberfläche der akkumulativen Kosten beispielsweise die Reisezeit in Stunden angeben soll und die Zellengröße für die Analyse in Meter angegeben ist, muss die tatsächliche Neigung Einheiten für Stunden/Meter aufweisen.
Da die tatsächliche Neigung ein Produkt aus verschiedenen Termen ist, müssen Sie sicherstellen, dass die Einheiten für die einzelnen Terme zusammen die richtigen Einheiten für die tatsächliche Neigung ergeben. Wenn Sie also beispielsweise nur ein einfaches Eingabe-Kosten-Raster (Reibung) verwenden, um die Reisezeit unabhängig von der Richtung zu beschreiben, müssen die Zellenwerte des Eingabe-Kosten-Rasters (Reibung) Einheiten für Stunden/Meter aufweisen. Wenn Sie alternativ auch die Wanderfunktion von Tobler als Funktion für den vertikalen Faktor verwenden, weist diese Wanderfunktion Einheiten für Stunden/Meter auf, und die Kostenoberfläche (Reibung) muss, sofern vorhanden, als einheitenlose Gewichtung interpretiert werden. Dann müssen Sie sicherstellten, dass die Zellenwerte für die Kosten (Reibung) auf diese Weise interpretiert werden. Anders ausgedrückt: Ihre vertikale Funktion und die Kosten (Reibung) können nicht beide Verhältnisse angeben.
Die Eingabe-Oberfläche (S) wird nicht direkt festgelegt. Hierbei handelt es sich um eine einheitenlose Gewichtung, mit der die Zellengröße gestreckt wird, um die tatsächliche 3D-Oberflächenentfernung zwischen Zellenmittelpunkten zu beschreiben. Der Algorithmus zur Oberflächenrekonstruktion in Abbildung 2 berechnet eine Höhe z5 für die mittlere Zelle, indem er mehrere Näherungen für diese Höhe berechnet und dazu die Neigung aus dem Eingabe-Kosten-Raster (Reibung) bei der mittleren Zelle und die als bekannt vorausgesetzten Höhen für die Nachbarzellen verwendet.
Barrieren sind über Kanten verbunden.
Barrieren in den Werkzeugen Entfernungsakkumulation und Entfernungsallokation sind Eingabezellen, die nicht durchlaufen werden können. Während der Berechnung werden sie als NoData-Zellen dargestellt. Sie werden entweder explizit als Werkzeugparameter oder implizit als NoData-Werte in einer der anderen Raster-Eingaben (z. B. im Kosten-Raster (Reibung)) dargestellt. Im ersten Fall werden sie gerastert und im Kosten-Raster in NoData konvertiert. Da der Algorithmus zur Oberflächenrekonstruktion die Höhenschätzung für eine Barrierenzelle nicht senken kann, wird stattdessen nach einem Weg darum herum gesucht.
Der Algorithmus zur Oberflächenrekonstruktion verwendet zur Ermittlung der Höhenschätzung alle acht Nachbarn einer Zelle. Durch über Ecken verbundene Barrierennachbarn wird nicht verhindert, dass zur Ermittlung der Höhenschätzung ein diagonaler Nachbar verwendet wird. In der folgenden Abbildung kann eine Höhenschätzung für z5 aus z3 ermittelt werden, auch wenn es sich bei den Zellen z2 und z6 um Barrieren handelt.
Wenn z2 und z6 Teil eines linearen Barrieren-Features, z. B. eines Kanals oder Flusses, sein sollen, macht dieses Verhalten den Zweck der Barriere zunichte. Um dies zu verhindern, werden beim Algorithmus zur Oberflächenrekonstruktion die Verbindung von Barrierenzellen gegenüber der Verbindung von Nicht-Barrierenzellen bevorzugt. Das bedeutet, dass zusätzliche NoData-Zellen in das Kosten-Raster eingefügt werden, um sicherzustellen, dass alle vorhandenen Barrierenzellen eine Kante gemeinsam haben. In der obigen Abbildung wird entweder Zelle z5 oder Zelle z3 ebenfalls eine Barrierenzelle.
Wenn Sie in Ihrer Analyse Barrieren verwenden, sollten Sie dieses Verhalten berücksichtigen und die Zellengröße für die Analyse entsprechend anpassen, sodass die gewünschte Konnektivität in der Nähe von Barrieren erhalten bleibt. Mit dem Werkzeug Focal Statistics können Sie Raster-Versionen von linearen Features verstärken, um sie entweder als Barrieren oder als lineare Netzwerk zu verwenden, die nicht durch benachbarte Barrierenzellen unterbrochen werden sollten.
Referenzen
Douglas, D. "Least-cost Path in GIS Using an Accumulated Cost Surface and Slopelines", Cartographica: The International Journal for Geographic Information and Geovisualization, 1994, Bd. 31, Nr. 3, DOI: 10.3138/D327-0323-2JUT-016M
Goodchild, M.F. "An evaluation of lattice solutions to the problem of corridor location", Environment and Planning A: Economy and Space, 1977, Bd. 9, S. 727–738
Sethian, J.A. Level Set Methods and Fast Marching Methods (Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science) 2. Ausgabe, Cambridge University Press, 2. Ausgabe (1. Juni 1999)
Warntz, W. "Transportation, Social Physics, and the Law Of Refraction", The Professional Geographer, 1957, Bd. 9, Nr. 4, S. 2–7.
Zhao, H. "A fast sweeping method for Eikonal equations", Mathematics of Computation, 2004, Bd. 74, Nr. 250, S. 603–627