xrspatial.pathfinding.multi_stop_search#

xrspatial.pathfinding.multi_stop_search(surface: DataArray, waypoints: list, barriers: list | None = None, x: str = 'x', y: str = 'y', connectivity: int = 8, snap: bool = False, friction: DataArray | None = None, search_radius: int | None = None, optimize_order: bool = False) → DataArray[source]#

Find the least-cost path visiting a sequence of waypoints in order.

Wraps a_star_search() to route through N waypoints, stitching segments into a single cumulative-cost surface. When optimize_order=True, the interior waypoints are reordered to minimize total travel cost (TSP), keeping the first and last waypoints fixed.

Dask-backed surfaces are routed sparsely and the segments are stitched lazily, so the full grid is never materialized in memory; peak memory scales with the chunk size and the explored corridor.

Parameters:

surface (xr.DataArray or xr.Dataset) – 2-D elevation / cost surface. A Dataset routes each data variable through the same waypoints independently and returns a Dataset of the per-variable results.
waypoints (list of array-like) – Sequence of (y, x) coordinate pairs to visit. Must contain at least two points.
barriers (list, optional) – Surface values that are impassable. Default is no barriers. Cells whose value is NaN are always impassable, regardless of this list.
x (str, default 'x' / 'y') – Coordinate dimension names.
y (str, default 'x' / 'y') – Coordinate dimension names.
connectivity (int, default=8) – 4 or 8 connectivity.
snap (bool, default=False) – Snap each waypoint to the nearest valid pixel. Not supported with dask-backed arrays.
friction (xr.DataArray, optional) – Friction surface (same shape as surface).
search_radius (int, optional) – Passed to each a_star_search() call.
optimize_order (bool, default=False) – Reorder interior waypoints to minimize total cost. Uses exact Held-Karp when N <= 12, nearest-neighbor + 2-opt otherwise.

Returns:

Cumulative path cost surface, backed by the same array type as surface (numpy, cupy, dask, or dask+cupy). Input attributes are preserved, with waypoint_order, segment_costs, and total_cost added. A Dataset input returns a Dataset of per-variable results.

Return type:

xr.DataArray or xr.Dataset

Raises:

ValueError – If the surface is not 2-D, fewer than two waypoints are given, waypoints fall outside the surface bounds, or a segment is unreachable.
TypeError – If barriers contains non-numeric values or search_radius is not an integer.

Examples

>>> import numpy as np
>>> import xarray as xr
>>> from xrspatial import multi_stop_search
>>> agg = xr.DataArray(np.array([
...     [0, 1, 0, 0],
...     [1, 1, 0, 0],
...     [0, 1, 2, 2],
...     [1, 0, 2, 0],
...     [0, 2, 2, 2]
... ], dtype=np.float64), dims=['lat', 'lon'])
>>> height, width = agg.shape
>>> agg['lon'] = np.linspace(0, width - 1, width)
>>> agg['lat'] = np.linspace(height - 1, 0, height)

>>> # visit 3 waypoints; pixels with value 0 are barriers
>>> waypoints = [(3, 0), (1, 2), (0, 1)]
>>> path_agg = multi_stop_search(
...     agg, waypoints, barriers=[0], x='lon', y='lat')
>>> path_agg.attrs['waypoint_order']
[(3, 0), (1, 2), (0, 1)]
>>> path_agg.attrs['segment_costs']
[2.8284271247461903, 1.4142135623730951]
>>> path_agg.attrs['total_cost']
4.242640687119286