Funktionsweise der Werkzeuge zur Pfadentfernung

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

Das Werkzeug Pfadentfernung ist das primäre Werkzeug für die Kostenentfernungsanalyse, die für sowohl horizontale als auch vertikale Kostenfaktoren sowie die tatsächliche Oberflächenentfernung verantwortlich ist. Das Werkzeug Pfadentfernungs-Zuordnung setzt den gleichen Algorithmus ein, aber gibt ein Raster, das die nächste Quelle für jede Zelle für jede Position bezeichnet, als primäre Ausgabe zurück. Das Werkzeug Pfadentfernungs-Rückverknüpfung identifiziert die Direktionalität des Nachbarn, der die nächste Zelle auf dem günstigsten akkumulativen Kostenpfad zur nächsten Quelle ist.

Berechnung der Pfadentfernung

Die Werkzeuge zur Pfadentfernung erstellen ein Ausgabe-Raster, in dem jeder Zelle die akkumulativen Kosten der nächsten Quellenzelle zugewiesen werden. Der Algorithmus verwendet die Knoten/Link-Zellenrepräsentation. Bei dieser 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 abgeleitet.

Zur Vereinfachung wird anhand der Formeln im folgenden Abschnitt dargestellt, wie Reisekosten zellenübergreifend nur über eine Kostenoberfläche kumuliert werden. Das Modifizieren der Kosten unter Berücksichtigung einer Oberflächenentfernung sowie horizontaler und vertikaler Faktoren wird in einem späteren Abschnitt erläutert.

Knotenreisekosten

Die Kosten, um von einem 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 ihrer vier direkt verbundenen 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
  • Dabei gilt:

    cost1 sind die Kosten, um durch Zelle 1 zu reisen.

    cost2 sind die Kosten, um durch Zelle 2 zu reisen.

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

    Kostenberechnung für benachbarte Zellen

Akkumulative senkrechte Kosten

Die akkumulativen Kosten werden mit der folgenden Formel bestimmt:

 accum_cost = a1 + (cost2 + cost3) / 2
  • Dabei gilt:

    cost2 sind die Kosten, um durch Zelle 2 zu reisen.

    cost3 sind die Kosten, um durch Zelle 3 zu reisen.

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

    Hinweis: unten im Bild sind a2 die Kosten, um von Zelle 2 in Zelle 3 zu reisen.

Kostenberechnung für nicht benachbarte Zellen

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 die Bewegung durch Zelle 1 plus die Kosten für die Bewegung durch Zelle 2, dividiert durch 2:

 a1 = 1.414214(cost1 + cost2) / 2
Kostenberechnung für diagonale Zellen

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

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

Akkumulativen Kosten-Zellenliste

Mit Graphentheorie ein akkumulatives Kostenentfernungs-Raster zu erstellen kann als Versuch angesehen werden, die niedrigste-Kosten-Zelle zu identifizieren und sie 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.

Vergleichen von Pfadentfernung mit Kostenentfernung

Die Verarbeitung bei der Pfadentfernung ist der bei der Kostenentfernung (siehe Wie die Kostenentfernungswerkzeuge funktionieren) ähnlich. Zuerst werden die Quellenzellen identifiziert. Dann werden die Kosten, um zu jedem Nachbarn zu reisen, der an eine Quellenzelle grenzt, bestimmt. Danach wird jede der Nachbarzellen, angefangen bei der kostengünstigsten, aufsteigend aufgelistet. Die Zellenposition mit den geringsten Kosten wird aus der Liste entfernt. Schließlich werden die niedrigsten akkumulativen Kosten zu jeder Nachbarzelle, die aus der Liste entfernt wurde, bestimmt.

Bearbeiten der Liste für akkumulative Kostenwerte (3)

Der Prozess wird wiederholt, bis allen Zellen auf dem Raster akkumulative Kosten zugewiesen wurden. Der Unterschied zwischen den Werkzeugen zur Kostenentfernung und zur Pfadentfernung besteht darin, wie die Kosten, um sich von einer Zelle zur nächsten zu bewegen, berechnet werden.

Pfadentfernungsformel

Aus der Zellenperspektive ist die Zielsetzung der Werkzeuge zur Pfadentfernung, die kostengünstigste Route zu bestimmen, um eine Zelle von der günstigsten Quelle in der Analyseausdehnung zu erreichen. Der kleinste akkumulative Kostenpfad zu einer Quelle, die Quelle mit der kostengünstigsten Route, und die kostengünstigste Route selbst müssen für jede Zelle bestimmt werden.

Pfadentfernung

Die Kosten für die zellenübergreifende Bewegung über die Kostenoberfläche werden anhand der oben erläuterten Formeln bestimmt. Innerhalb der Pfadentfernung können diese Kosten (in den nachfolgenden Gleichungen als Cost_Surface bezeichnet) mithilfe der Oberflächenentfernung (Surface_distance) und der horizontalen und vertikalen Faktoren modifiziert werden. Die Formelwahl zur Berechnung der Gesamtkosten für die Reise von Zelle a zu Zelle b hängt davon ab, ob diese Reise senkrecht oder diagonal ist:

  • Senkrecht:
    Cost_distance = (((Cost_Surface(a) * Horizontal_factor(a)) + (Cost_surface(b) * Horizontal_factor(b)))/2)
                    * Surface_distance(ab) * Vertical_factor(ab)
  • Diagonal:
    Cost_distance = (((Cost_Surface(a) * Horizontal_factor(a)) + (Cost_surface(b) * Horizontal_factor(b)))/2)
                    * 1.414214 * Surface_distance(ab) * Vertical_factor(ab)

Beachten Sie, dass die Division der Reibung der Segmente durch 2 verzögert wird, bis der horizontale Faktor integriert wird.

Wenn keine Kostenoberfläche angegeben ist, werden Kosten von 1 pro Einheitenentfernung verwendet (dies entspricht der Anwendung eines Kostenrasters, bei dem alle Werte 1 entsprechen). Sowohl die horizontalen als auch die vertikalen Faktoren werden auf die Entfernung pro Einheit angewendet. Negative horizontale und vertikale Faktoren sind nicht zulässig. Da beide Faktoren jedoch Multiplikatoren der akkumulativen Kosten jeder Zelle sind, reduziert ein Faktor von kleiner als 1 aber größer als 0, die Gesamtkosten der jeweiligen Zelle. Ein vertikaler Faktor von Null oder Nullwerte für beide Segmente des horizontalen Faktors ergeben einen Kostenwert von 0 für die Zelle.

Akkumulativen Kostenentfernung

Die akkumulativen Kosten, um von Zelle a zu Zelle c durch Zelle b zu reisen, ergeben sich wie folgt:

Accum_cost_distance = a1 + (((Cost_Surface(b) * Horizontal_factor(b)) + (Cost_surface(c) 
                      * Horizontal_factor(c)))/2) * Surface_distance(bc) * Vertical_factor(bc)
  • Dabei gilt:

    a1 sind die Gesamtkosten für die Bewegung von Zelle a zu Zelle b.

Horizontale und vertikale Parameter

Es gibt es mehrere Arten von Parametern, mit denen Sie die horizontalen und vertikalen Reibungsfaktoren steuern können. Für jeden dieser Faktoren gibt es verschiedene Modifikatoren, die für die weitere Kontrolle über die Analyse verwendet werden können.

Fahren Sie für weitere Details zu diesen Parametern mit dem folgenden Abschnitt fort:

Verwandte Themen

9/12/2013