Bases: object
A class for finding the minimum cost path through a given n-d costs array.
Given an n-d costs array, this class can be used to find the minimum-cost path through that array from any set of points to any other set of points. Basic usage is to initialize the class and call find_costs() with a one or more starting indices (and an optional list of end indices). After that, call traceback() one or more times to find the path from any given end-position to the closest starting index. New paths through the same costs array can be found by calling find_costs() repeatedly.
The cost of a path is calculated simply as the sum of the values of the costs array at each point on the path. The class MCP_Geometric, on the other hand, accounts for the fact that diagonal vs. axial moves are of different lengths, and weights the path cost accordingly.
Array elements with infinite or negative costs will simply be ignored, as will paths whose cumulative cost overflows to infinite.
Parameters: | costs : ndarray offsets : iterable, optional
fully_connected : bool, optional
|
---|
Attributes
offsets |
See class documentation.
Find the minimum-cost path from the given starting points.
This method finds the minimum-cost path to the specified ending indices from any one of the specified starting indices. If no end positions are given, then the minimum-cost path to every position in the costs array will be found.
Parameters: | starts : iterable
ends : iterable, optional
find_all_ends : bool, optional
|
---|---|
Returns: | cumulative_costs : ndarray
traceback : ndarray
|
Trace a minimum cost path through the pre-calculated traceback array.
This convenience function reconstructs the the minimum cost path to a given end position from one of the starting indices provided to find_costs(), which must have been called previously. This function can be called as many times as desired after find_costs() has been run.
Parameters: | end : iterable
|
---|---|
Returns: | traceback : list of n-d tuples
|
Bases: skimage.graph._mcp.MCP
Find distance-weighted minimum cost paths through an n-d costs array.
See the documentation for MCP for full details. This class differs from MCP in that the cost of a path is not simply the sum of the costs along that path.
This class instead assumes that the costs array contains at each position the “cost” of a unit distance of travel through that position. For example, a move (in 2-d) from (1, 1) to (1, 2) is assumed to originate in the center of the pixel (1, 1) and terminate in the center of (1, 2). The entire move is of distance 1, half through (1, 1) and half through (1, 2); thus the cost of that move is (1/2)*costs[1,1] + (1/2)*costs[1,2].
On the other hand, a move from (1, 1) to (2, 2) is along the diagonal and is sqrt(2) in length. Half of this move is within the pixel (1, 1) and the other half in (2, 2), so the cost of this move is calculated as (sqrt(2)/2)*costs[1,1] + (sqrt(2)/2)*costs[2,2].
These calculations don’t make a lot of sense with offsets of magnitude greater than 1.
See class documentation.
skimage.graph.route_through_array(array, ...) | Simple example of how to use the MCP and MCP_Geometric classes. |
skimage.graph.shortest_path(arr[, reach, ...]) | Find the shortest path through an n-d array from one side to another. |
Simple example of how to use the MCP and MCP_Geometric classes.
See the MCP and MCP_Geometric class documentation for explanation of the path-finding algorithm.
Parameters: | array : ndarray
start : iterable
end : iterable
fully_connected : bool (optional)
geometric : bool (optional)
|
---|---|
Returns: | path : list
cost : float
|
See also
Examples
>>> import numpy as np
>>> from skimage.graph import route_through_array
>>>
>>> image = np.array([[1, 3], [10, 12]])
>>> image
array([[ 1, 3],
[10, 12]])
>>> # Forbid diagonal steps
>>> route_through_array(image, [0, 0], [1, 1], fully_connected=False)
([(0, 0), (0, 1), (1, 1)], 9.5)
>>> # Now allow diagonal steps: the path goes directly from start to end
>>> route_through_array(image, [0, 0], [1, 1])
([(0, 0), (1, 1)], 9.1923881554251192)
>>> # Cost is the sum of array values along the path (16 = 1 + 3 + 12)
>>> route_through_array(image, [0, 0], [1, 1], fully_connected=False,
... geometric=False)
([(0, 0), (0, 1), (1, 1)], 16.0)
>>> # Larger array where we display the path that is selected
>>> image = np.arange((36)).reshape((6, 6))
>>> image
array([[ 0, 1, 2, 3, 4, 5],
[ 6, 7, 8, 9, 10, 11],
[12, 13, 14, 15, 16, 17],
[18, 19, 20, 21, 22, 23],
[24, 25, 26, 27, 28, 29],
[30, 31, 32, 33, 34, 35]])
>>> # Find the path with lowest cost
>>> indices, weight = route_through_array(image, (0, 0), (5, 5))
>>> indices = np.array(indices).T
>>> path = np.zeros_like(image)
>>> path[indices[0], indices[1]] = 1
>>> path
array([[1, 1, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 1]])
Find the shortest path through an n-d array from one side to another.
Parameters: | arr : ndarray of float64 reach : int, optional
axis : int, optional
output_indexlist: bool, optional :
|
---|---|
Returns: | p : iterable of int
cost : float
|