How the path distance tools work

Available with Spatial Analyst license.

While Euclidean distance is the straight line—as the crow flies (distance between locations)—the path distance tools explore the movement of a traveler over a landscape. The path distance tools are generally used to create the least-cost path between a source and a destination, while accounting for the surface distance and the horizontal and vertical factors.

Some example problems solved by path distance analysis

• Determine the best hiking trail to reach a distant location.
• Calculate the actual cost and distance for a proposed road adjusting for the uphill and downhill changes in the landscape.
• Determine the route a ship should take accounting for the ocean currents and the wind.

The general formula for path distance analysis

The cost to move from one cell to another is influenced by the following:

1. The surface characteristics (the cost surface).
2. The characteristics of the mover. This could include the mode of travel, such as moving by foot or riding an ATV.
3. The characteristics of the movement when moving from one cell to another, such as moving uphill or downhill.

The general cost distance formula is the following:

Cost = Cost of travel  *  Characteristics  *  Movement characteristics
       over surface       of the mover        on the surface

The path distance tools incorporate the surface characteristics through the cost surface, which is discussed below. See How the source characteristics affect cost distance analysis to learn how to control the characteristics of the mover within the path distance tools. The surface raster and the horizontal and vertical factors within the path distance tools allow you to define the movement characteristics from cell to cell.

Calculation of path distance

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.

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 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.

To simplify the discussion, the formulas in the following section identify how travel cost is accumulated between cells over a cost surface; how to modify the cost to account for surface distance and horizontal and vertical factors will be addressed in a subsequent section.

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—The cost to travel through cell 1.

  cost2—The cost to travel through cell 2.

  a1—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—The cost to travel through cell 2.

  cost3—The cost to travel through cell 3.

  accum_cost—The accumulative cost of moving into cell 3 from cell 1.

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 this active list. The least accumulative cost to each of the neighbors of the cell that was removed are determined and those locations are added to the active list. Then, the next cell location with the least cost in the active list is removed.

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.

Path distance

The cost to move between cells over the cost surface is determined by the formulas discussed above. In Path Distance, these costs (identified as Cost_Surface in the equations below) can be modified by the surface distance (Surface_distance) and the horizontal and vertical factors. The formula used to calculate the total cost of travel from cell a to cell b depends on if that travel is perpendicular or diagonal:

• Perpendicular

  Cost_distance = (((Cost_surface(a) * HF(a)) + (Cost_surface(b) * HF(b)))/2)
                  * Surface_distance(ab) * VF(ab)

• Diagonal

  Cost_distance = (((Cost_surface(a) * HF(a)) + (Cost_surface(b) * HF(b)))/2)
                  * 1.414214 * Surface_distance(ab) * VF(ab)

• Where

  Cost_surface(a)—The cost of travel for cell a

  Cost_surface(b)—The cost of travel for cell b

  HF(a)—The Horizontal factor for cell a

  HF(b)—The Horizontal factor for cell b

  Surface_distance(ab)—The surface distance from a to b

  VF(ab)—The Vertical factor from a to b

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

If no cost surface is specified, then a cost of 1 per-unit distance will be used (the same as applying a cost raster with values of all 1s). Both the horizontal and vertical factors are applied to per-unit distance. Negative horizontal and vertical factors are not allowed. However, since both factors are multipliers to the accumulative cost for each cell, a factor of less than 1 but greater than 0 reduces the total cost for that cell. A vertical factor of zero, or zeros for both segments of the horizontal factors, result in a zero cost for the cell.

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 + (((Cost_surface(b) * HF(b)) + (Cost_surface(c) * HF(c)))/2)
                      * Surface_distance(bc) * VF(bc)

• Where

  a1—The total cost of travel from cell a to cell b

  Cost_surface(b)—The cost of travel for cell b

  Cost_surface(c)—The cost of travel for cell c

  HF(b)—The Horizontal factor for cell b

  HF(c)—The Horizontal factor for cell c

  Surface_distance(bc)—The surface distance from b to c

  VF(bc)—The Vertical factor from b to c

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, see following section:

• How the horizontal and vertical factors affect path distance