Desktop Help 10.0 - How the path distance tools work

All path distance tools use essentially the same algorithm to calculate output. The essential difference is determined by the primary output of each tool.

The Path Distance tool is the primary tool for cost distance analysis accounting for both horizontal and vertical cost factors as well as true surface distance. The Path Distance Allocation tool employs the same algorithm but returns as its primary output a raster denoting the nearest source for each cell for each location. The Path Distance Back Link tool identifies the directionality of the neighbor that is the next cell on the least accumulative cost path to the nearest source.

Calculation of path distance

The path distance tools create an output raster in which each cell is assigned the accumulative cost from the cheapest source cell. The algorithm utilizes the node/link cell representation. In this representation, the center of a cell is considered a node, and each node is connected by links to the nodes adjacent to it.

Every link has an impedance associated with it. The impedance is derived from the costs associated with the cells at each end of the link (from the cost surface) and from the direction of movement.

Node travel costs

The cost to travel between one node and the next is dependent on the spatial orientation of the nodes. How the cells are connected also impacts the travel cost.

Adjacent node cost

When moving from a cell to one of its four directly connected neighbors, the cost to move across the links to the neighboring node is 1 times cell 1, plus cell 2, divided by 2:

 a1 = (cost1 + cost2) / 2

where:
cost1 is the cost to travel through cell 1.
cost2 is the cost to travel through cell 2.
a1 is the cost assigned to the link from cell 1 to cell 2.

Accumulative perpendicular cost

The accumulative cost is determined with the following formula:

 accum_cost = a1 + (cost2 + cost3) / 2

where:
cost2 is the cost to travel through cell 2.
cost3 is the cost to travel through cell 3.
accum_cost is the accumulative cost of moving into cell 3 from cell 1.
Note: In the image below, a2 is the cost of moving from cell 2 to cell 3.

Diagonal node cost

If the movement is diagonal, the cost to travel the link is 1.414214 (the square root of 2) times the cost to travel through cell 1 plus the cost to travel through cell 2, divided by 2:

 a1 = 1.414214(cost1 + cost2) / 2

When determining the accumulative cost for diagonal movement, the following formula is used:

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

Accumulative cost cell list

Creating an accumulative cost-distance raster using graph theory can be viewed as an attempt to identify the lowest-cost cell and add it to an output list. It is an iterative process that begins with the source cells. The goal of each cell is to be assigned quickly to the output cost-distance raster.

Comparing path distance to cost distance

The processing that occurs in path distance is similar to that of cost distance (see How the cost distance tools work). First the source cells are identified. Then the cost to travel to each neighbor that adjoins a source cell is determined. Next, each of the neighbor cells is listed from least costly to most costly. The cell location with the least cost is removed from the list. Finally, the least accumulative cost to each of the neighbors of the cell that was removed from the list is determined.

Processing the accumulative cost values list (3)

The process is repeated until all cells on the raster have been assigned an accumulative cost. The difference between the cost distance and path distance tools is how the cost of moving from one cell to the next is computed.

Path distance formula

From the cell perspective, the objective of the path distance tools is for each cell location in the analysis extent to determine the least costly path to reach the cell from the least costly source. Each cell will need to determine the least accumulative cost path from a source, the source that allows for the least cost path, and the least cost path itself.

Cost distance

The formula used to calculate the total cost of travel from cell a to cell b depends on if the direction of travel of the least cost path takes it to an adjacent cell in a perpendicular or diagonal direction, as identified here:

Perpendicular:

Cost_distance = Cost_Surface * Surface_distance *
                 {[Friction(a) * Horizontal_factor(a) + 
                   Friction(b) * Horizontal_factor(b)] / 2} *
                 Vertical_factor

Diagonal:

Cost_distance = Cost_Surface * Surface_distance * 1.414214 *
                 {[Friction(a) * Horizontal_factor(a) + 
                   Friction(b) * Horizontal_factor(b)] / 2} *
                 Vertical_factor

Note that the division by 2 of the friction of the segments is deferred until the horizontal factor is integrated.

Accumulative cost distance

The accumulative cost to travel from cell a to cell c passing through cell b is as follows:

Accum_cost_distance = a1 + Surface_distance * 
                 {[Friction(b) * Horizontal_factor(b) + 
                   Friction(c) * Horizontal_factor(c)]/2} *
                 Vertical_factor

where:
a1 is the total cost of travel from cell a to cell b.

Horizontal and vertical parameters

There are several different types of parameters you can use to control the horizontal and vertical friction factors. For each of these factors, there are various modifiers that can be used for further control over the analysis.

For more details on these parameters, proceed to the following section:

How the horizontal and vertical factors affect path distance

How the path distance tools work