コスト距離ツールの詳細

すべてのコスト距離ツールが、本質的に同じアルゴリズムを使用して出力を計算します。本質的な違いは、各ツールのプライマリ出力が異なることです。

コスト距離の計算

[コスト距離] ツールは、最も近いソース セルまでの累積コストが各セルに割り当てられた出力ラスタを作成します。このアルゴリズムは、グラフ理論で使用されるノード/リンクのセル表現を活用します。ノード/リンク表現では、各セルの中心がノードと見なされ、各ノードが複数のリンクにより隣接ノードと接続されます。

各リンクには、インピーダンスが関連付けられます。インピーダンスは、リンクの各端点でセルに関連付けられた(コスト サーフェスから)コスト、およびセルの移動方向から得られます。

各セルに割り当てられるコストは、そのセルを移動するための単位距離あたりのコストを表します。最終的なセルごとの値は、セル サイズをコスト値で乗算することで算出されます。たとえば、コスト ラスタのセル サイズが 30 であり、特定のセルのコスト値が 10 の場合、そのセルの最終的なコストは 300 単位になります。

ノード移動コスト

1 つのノードから別のノードへの移動コストは、ノードの空間的な向きによって決まります。セルがどのように連続しているかも移動コストに影響します。

隣接ノード コスト

あるセルから隣接する 4 つのセルの 1 つに移動する場合、隣接ノードへのリンクの移動コストは、セル 1 のコストにセル 2 のコストを加算し、2 で除算した値です。

 a1 = (cost1 + cost2) / 2
  • 以下に、式の各項目を示します。

    cost1: セル 1 のコスト

    cost2: セル 2 のコスト

    a1: セル 1 とセル 2 を結ぶリンクの合計コスト

隣接セルのコストの計算

累積垂直コスト

累積コストは、以下の式で得られます。

 accum_cost = a1 + (cost2 + cost3) / 2
  • 以下に、式の各項目を示します。

    cost2: セル 2 のコスト

    cost3: セル 3 のコスト

    a2: セル 2 からセル 3 への移動コスト

    accum_cost: セル 1 からセル 3 への累積移動コスト

非隣接セルのコストの計算

対角ノード コスト

対角方向の移動の場合は、リンクの移動コストは、セル 1 のコストとセル 2 のコストの合計を 1.414214(√2)で乗算し、2 で除算した値になります。

 a1 = 1.414214 (cost1 + cost2) / 2

対角セルのコストの計算

対角移動の累積コストを求めるときには、以下の式を使用する必要があります。

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

累積コスト セルのリスト

グラフ理論を使用して累積コスト距離ラスタを作成することは、最小のコスト セルを特定して出力リストに追加する試行と見なすことができます。これは、ソース セルから開始される反復プロセスです。その目的は、各セルを出力コスト距離ラスタに即座に割り当てることです。

入力ソースとコスト ラスタ

最初の反復では、ソース セルが識別され、それらに 0 が割り当てられます。これは、そのセル自体に戻るための累積コストが 0 だからです。次に、ソース セルの近傍がすべてアクティブになり、ソース セルのノードと隣接セルのノードを結ぶリンクに、上記の累積コストの式によるコストが割り当てられます。これらの各近傍セルはソースに到達できるので、選択したり、出力累積コスト ラスタに割り当てたりできます。セルが出力ラスタに割り当てられるためには、ソースへの次に最小コスト パスが必要です。

累積コストの値は、最小から最大の順でリストに並べられます。

並べ替えられた累積コスト値のリスト

アクティブな累積コスト セルのリストから最小コスト セルが選択され、そのセル位置の値が出力コスト距離ラスタに割り当てられます。アクティブなセルのリストが、選択したセルの近傍範囲を含むように拡大されます。この理由は、それらのセルはソースに到達する経路があるからです。ソースに到達できるセルのみが、リスト内でアクティブにできます。累積コストの式を使用して、それらのセルへの移動コストが計算されます。

累積コスト値のリストの処理

ここでも、リストで最小コストを持つアクティブなセルが選択され、近傍が展開されます。新しいコストが計算され、新しいコスト セルがアクティブなセルに追加されます。

ソース セルが連続している必要はありません。不連続のソースはすべて、アクティブなセルのリストに同様に寄与します。累積コストが最小のセルのみが、割り当てられるソースには関係なく、選択されて展開されます。

累積コスト値のリストの処理

この割り当てプロセスが続行されます。さらに、出力ラスタに新しいセル位置を追加することにより新しい低コストの経路が作成される場合は、アクティブなリストのセルが更新されます。

累積コスト値のリストの処理

この更新により、出力ラスタにさらに多くのセルが割り当てられるので、アクティブなリストのセルについて新しい経路が発生することがあります。アクティブな累積コストのリストで最小コストを持つセルを出力ラスタに割り当てるときに、累積コストがすべて計算されます。隣接セルが別のセルによりアクティブなリストに追加されている場合でも、新規に割り当てられた出力セルの隣接セルについてもこれらのコストが計算されます。アクティブなリスト上で、場所に対する新しい累積コストが、セルの現在の累積コストよりも大きい場合、その値は無視されます。新しい累積コストの方が小さい場合は、その場所の古い累積コストが、アクティブなリストで新しい値に置き換えられます。低コストで一層望ましいソースへの経路にアクセスできるようになったそのセルは、アクティブな選択リスト内で上位に移動されます。

以下の例では、行 3、列 1 のセル位置を、ラスタ上部のソースに到達するアクティブなリストに入れたときの累積コストは 11.0 です(白の四角で囲んだ値)。ただし、値の小さいソースがこの位置まで展開するので、そのセルはソースに到達する、より低コストの経路にアクセスできます。累積コストが低くなることにより、アクティブなリストでその位置の値が更新され、出力に割り当てられます。

累積コスト値のリストの処理

入力ソース ラスタにゾーン、または不連続のソース セルのセットが複数ある場合は、展開プロセスが継続され、ソースがどれかには関係なく、アクティブなリストから最小コストのセルが割り当てられます。

累積コスト値のリストの処理

複数の展開の先端が出会ったときは、すべての対象のセルにコスト値が割り当てられるまで、最小コストを持つソースへの経路が続行されます。

累積コスト値のリストの処理

複数の展開パターンが出会うときに、ある展開パターンのセルが、別のセットまたは展開パターンでソース セルにさらに低いコストで到達できることがあります。この場合、新しいソースのセルに新しいコスト値が割り当てられます。この動作は前述の行 3、列 1 のセルで示されていますが、以下の例でも行 3、列 6 のセルで示されています。

累積コスト値のリストの処理
累積コスト値のリストの処理

アクティブなリストからセルがすべて選択された結果、累積コスト、または加重距離ラスタが得られます。使用した手順により、セルごとの最小累積コストが確実に得られます。ラスタのエッジに到達するまで、ウィンドウの境界が検出されるまで、または最大距離に到達するまで、すべてのセルについてこのプロセスが継続されます。

NoData の値を持つセルを通過することはできません。NoData セルのグループの裏側にあるセルの最小累積コストは、それらの位置の周囲を移動するコストによって決定されます。入力コスト ラスタのあるセル位置に NoData が割り当てられている場合、コスト距離の出力ラスタのその位置には、NoData が割り当てられます。

コスト距離の出力値
コスト距離の出力値

関連トピック

9/17/2013