Funktionsweise der Kostenentfernungs-Werkzeuge

Alle Kostenentfernungswerkzeuge berechnen im Grunde die Ausgabe mithilfe des gleichen Algorithmus. Der wesentliche Unterschied wird von der primären Ausgabe jedes Werkzeugs bestimmt.

Berechnung der Kostenentfernung

Das Werkzeug Cost Distance erstellt ein Ausgabe-Raster, in dem jeder Zelle die akkumulativen Kosten der nächsten Quellenzelle zugewiesen werden. Der Algorithmus verwendet den Knoten/Link, den die Zellenrepräsentation in der Graphentheorie verwendet hat. Im Knoten-/Link-Repräsentation wird jeder Mittelpunkt einer Zelle als ein Knoten angesehen und jeder Knoten wird über mehrere Links mit seinen benachbarten Knoten verbunden.

Jeder Link ist mit einer Impedanz verknüpft. Die Impedanz wird von den Kosten der Zellen an jedem Ende des Links (von der Kostenoberfläche) und von der Richtung der Bewegung durch die Zellen abgeleitet.

Die jeder Zelle zugewiesenen Kostenwerte stellen die Kosten pro Einheitenentfernung für die Bewegung durch die Zelle dar. Der endgültige Wert pro Zelle ist die mit dem Kostenwert multiplizierte Zellengröße. Wenn das Kosten-Raster z. B. eine Zellengröße von 30 hat und eine bestimmte Zelle über den Kostenwert 10 verfügt, betragen die abschließenden Kosten für diese Zelle 300 Einheiten.

Knotenreisekosten

Die Kosten, um zwischen einen Knoten zum nächsten zu reisen, sind von der räumlichen Ausrichtung der Knoten abhängig. Die Verbindung der Zellen wirkt sich auch auf die Reisekosten aus.

Benachbarte Knotenkosten

Bei der Bewegung von einer Zelle zu einem seiner vier direkt verbundener Nachbarn betragen die Kosten für die Bewegung über die Links zum benachbarten Knoten 1-mal Zelle 1, plus Zelle 2, dividiert durch 2:

 a1 = (cost1 + cost2) / 2

• Bedingung:

  cost1 – die Kosten für Zelle 1

  cost2 – die Kosten für Zelle 2

  a1 – die Gesamtkosten für den Link von Zelle 1 zu Zelle 2

Akkumulative senkrechte Kosten

Die akkumulativen Kosten werden mit der folgenden Formel bestimmt:

 accum_cost = a1 + (cost2 + cost3) / 2

• Bedingung:

  cost2 – die Kosten für Zelle 2

  cost3 – die Kosten für Zelle 3

  a2 – die Gesamtkosten für die Bewegung von Zelle 2 zu Zelle 3

  accum_cost – die akkumulativen Kosten für die Bewegung von Zelle 1 zu Zelle 3

Diagonale Knotenkosten

Wenn die Bewegung diagonal erfolgt, sind die Kosten, um über den Link zu reisen, 1,414214 (oder die Quadratwurzel von 2) Mal die Kosten für Zelle 1 plus die Kosten für Zelle 2, dividiert durch 2:

 a1 = 1.414214 (cost3 + cost2) / 2

Wenn Sie die akkumulativen Kosten für diagonale Bewegung bestimmen, muss die folgende Formel verwendet werden:

 accum_cost = a1 + 1.414214(cost2 + cost3) / 2

Akkumulativen Kosten-Zellenliste

Mit Graphentheorie ein akkumulatives Kostenentfernungs-Raster zu erstellen kann als Versuch angezeigt werden, die niedrigste-Kosten-Zelle zu identifizieren und es einer Ausgabeliste hinzuzufügen. Es handelt sich hierbei um einen iterativen Prozess, der mit den Quellenzellen beginnt. Das Ziel jeder Zelle sollte dem Ausgabe-Kostenentfernungs-Raster schnell zugewiesen werden.

In der ersten Iteration werden die Quellenzellen identifiziert und erhalten den Wert 0, da es für die Rückkehr zur eigenen Zelle keine akkumulativen Kosten gibt. Danach werden die Nachbarn aller Quellenzellen aktiviert und die Links zwischen den Quellenzellenknoten und den Knoten der benachbarten Zellen werden mithilfe der oben erwähnten akkumulativen Kosten-Formeln zugewiesen. Jede dieser benachbarten Zellen kann eine Quelle erreichen; infolgedessen können sie ausgewählt oder für das akkumulative Ausgabe-Kosten-Raster eingeteilt werden. Eine Zelle muss die kostengünstigste Route zu einer Quelle haben, die zum Ausgabe-Raster zugewiesen werden soll.

Die akkumulativen Kostenwerte werden in einer Liste von den niedrigsten akkumulativen Kosten aufwärts angeordnet.

Die Zelle mit den niedrigsten Kosten wird aus der aktiven Liste der akkumulativen Zellenkosten ausgewählt und dem Ausgabe-Kostenentfernungs-Raster wird der Wert für diese Zellenposition zugewiesen. Die Liste der aktiven Zellen blendet die Nachbarn von der ausgewählten Zelle ein, da jene Zellen jetzt eine Möglichkeit haben, eine Quelle zu erreichen. Nur jene Zellen, die möglicherweise eine Quelle erreichen können, können in der Liste aktiv sein. Die Kosten, um sich in diese Zellen zu bewegen, werden mit den akkumulativen Kosten-Formeln berechnet.

Wieder wird die aktive Zelle auf der Liste mit den niedrigsten Kosten ausgewählt, die Nachbarschaft wird erweitert, die neuen Kosten werden berechnet und der aktiven Liste werden die neuen Kostenzellen hinzugefügt.

Quellzellen müssen nicht verbunden werden. Alle nicht verbundenen Quellen erhalten in der List den gleichen Wert. Nur die Zelle mit den niedrigsten akkumulativen Kosten wird ausgewählt und erweitert, unabhängig von der Quelle, der diese Zelle zugewiesen wird.

Dieser Zuweisungsprozess wird fortgesetzt. Furthermore, cells on the active list are updated if a new, cheaper route is created by the addition of new cell locations to the output raster.

Diese Aktualisierung kann bei Zuweisung neuer Pfade für Zellen auf der aktiven Liste auftreten, da dem Ausgabe-Raster mehr Zellen zugeordnet werden. Wenn dem Ausgabe-Raster die Zelle mit dem niedrigsten Wert auf der aktiven akkumulativen Kosten-Liste zugeordnet wird, werden alle akkumulativen Kosten berechnet. Diese Kosten werden auch für die benachbarten Zellen der neu zugewiesenen Ausgabezelle berechnet, auch wenn die benachbarten Zellen auf der aktiven Liste auf einer anderen Zelle aufgeführt sind. Wenn die neuen akkumulativen Kosten für die Positionen auf der aktiven Liste höher als die aktuellen Kosten der Zellen sind, wird der Wert ignoriert. Wenn die akkumulativen Kosten geringer sind, werden die alten akkumulativen Kosten für die Position auf der aktiven Liste durch den neuen Wert ersetzt. Diese Zelle, die jetzt Zugriff auf einen günstigeren und erwünschteren Pfad zu einer Quelle hat, wird in der aktiven gewählten Liste nach oben bewegt.

Unten im Beispiel hatte die Zellenposition bei Zeile 3, Spalte 1 (vom Feld hervorgehoben), akkumulative Kosten von 11, als es auf der aktiven Liste abgelegt wurde, um die Quelle am oberen Rand des Rasters zu erreichen. Da die niedrigere Quelle jedoch zu dieser Position erweitert wurde, hatte die Zelle Zugriff auf einen günstigeren akkumulativen Kostenpfad, um eine Quelle zu erreichen. Der Wert für die Position wurde auf der aktiven Liste aktualisiert und wurde wegen dieser niedrigeren akkumulativen Kosten der Ausgabe zugeordnet.

Wenn es mehrere Zonen oder getrennte Sätze von Quellenzellen auf dem Eingabequellen-Raster gibt, fährt der Prozess fort und ordnet die günstigste Kostenzelle aus der aktiven Liste zu unabhängig von der Quelle zu.

Wenn sich die Fronten treffen, wird die kostengünstigste Route zurück zur Quelle fortgesetzt, bis alle freigegebenen Zellen einen Kostenwert erhalten haben.

Wenn sich zwei Fronten treffen, ist es möglich, dass Zellen von einem Zunahmemuster in der Lage sind, in einem anderen Satz oder einem Zunahmemuster günstiger eine Quellenzelle zu erreichen; in diesem Fall werden sie zur neuen Quelle zugewiesen. Dieses Verhalten entstand zuvor bei Zelle in Zeile 3, Spalte 1, jedoch auch unten von der Zelle in Zeile 3, Spalte 6.

Wenn alle Zellen aus der aktiven Liste ausgewählt wurden, entsteht das akkumulative Kosten-Raster oder gewichtete Entfernungs-Raster. Das verwendete Verfahren stellt sicher, dass die niedrigsten akkumulativen Kosten für jede Zelle verwendet werden. Dieser Prozess fährt für alle Zellen bis zum Rand des Rasters, zum Fensterrand oder zur maximalen Entfernung fort.

Die Reise durch Zellen mit NoData-Wert ist nicht möglich. Die niedrigsten akkumulativen Kosten für Zellen auf der anderen Seite einer Gruppe von NoData-Zellen werden von den Kosten für die Reise um diese Zellen bestimmt. Wenn einer Zellenposition auf dem Eingabe-Kosten-Raster NoData zugewiesen wird, wird der Zellenposition auf dem Kostenentfernungs-Ausgabe-Raster NoData zugewiesen.

Kostenentfernungs-Ausgabewerte