logo
  • Versions
    latest 0.3.5 0.3.4 0.3.3 0.3.2 0.3.1 0.3.0 0.2.9 0.2.8 0.2.7 0.2.6 0.2.5 0.2.4 0.2.3 0.2.2 0.2.1 0.2.0
    • Getting started
    • User Guide
    • Reference
    • Classification
      • xrspatial.classify.equal_interval
      • xrspatial.classify.natural_breaks
      • xrspatial.classify.reclassify
      • xrspatial.classify.quantile
    • Focal
      • xrspatial.focal.apply
      • xrspatial.focal.hotspots
      • xrspatial.focal.mean
      • xrspatial.convolution.convolution_2d
      • xrspatial.convolution.annulus_kernel
      • xrspatial.convolution.calc_cellsize
      • xrspatial.convolution.circle_kernel
      • xrspatial.focal.custom_kernel
      • xrspatial.focal.focal_stats
    • Multispectral
      • xrspatial.multispectral.arvi
      • xrspatial.multispectral.ebbi
      • xrspatial.multispectral.evi
      • xrspatial.multispectral.gci
      • xrspatial.multispectral.nbr
      • xrspatial.multispectral.nbr2
      • xrspatial.multispectral.ndmi
      • xrspatial.multispectral.ndvi
      • xrspatial.multispectral.savi
      • xrspatial.multispectral.sipi
      • xrspatial.multispectral.true_color
    • Pathfinding
      • xrspatial.pathfinding.a_star_search
    • Proximity
      • xrspatial.proximity.allocation
      • xrspatial.proximity.direction
      • xrspatial.proximity.euclidean_distance
      • xrspatial.proximity.great_circle_distance
      • xrspatial.proximity.manhattan_distance
      • xrspatial.proximity.proximity
    • Surface
      • xrspatial.aspect.aspect
      • xrspatial.curvature.curvature
      • xrspatial.hillshade.hillshade
      • xrspatial.slope.slope
      • xrspatial.terrain.generate_terrain
      • xrspatial.viewshed.viewshed
      • xrspatial.perlin.perlin
      • xrspatial.bump.bump
    • Zonal
      • xrspatial.zonal.apply
      • xrspatial.zonal.crop
      • xrspatial.zonal.regions
      • xrspatial.zonal.trim
      • xrspatial.zonal.get_full_extent
      • xrspatial.zonal.stats
      • xrspatial.zonal.suggest_zonal_canvas
      • xrspatial.zonal.crosstab
    • Local
      • xrspatial.local.cell_stats
      • xrspatial.local.combine
      • xrspatial.local.lesser_frequency
      • xrspatial.local.equal_frequency
      • xrspatial.local.greater_frequency
      • xrspatial.local.lowest_position
      • xrspatial.local.highest_position
      • xrspatial.local.popularity
      • xrspatial.local.rank

    xrspatial.pathfinding.a_star_search#

    xrspatial.pathfinding.a_star_search(surface: xarray.core.dataarray.DataArray, start: Union[tuple, list, numpy.array], goal: Union[tuple, list, numpy.array], barriers: list = [], x: Optional[str] = 'x', y: Optional[str] = 'y', connectivity: int = 8, snap_start: bool = False, snap_goal: bool = False) → xarray.core.dataarray.DataArray[source]#

    Calculate distance from a starting point to a goal through a surface graph. Starting location and goal location should be within the graph.

    A* is a modification of Dijkstra’s Algorithm that is optimized for a single destination. Dijkstra’s Algorithm can find paths to all locations; A* finds paths to one location, or the closest of several locations. It prioritizes paths that seem to be leading closer to a goal.

    The output is an equal sized Xarray.DataArray with NaNs for non-path pixels, and the value of the path pixels being the current cost up to that point.

    Parameters
    • surface (xr.DataArray) – 2D array of values to bin.

    • start (array-like object of 2 numeric elements) – (y, x) or (lat, lon) coordinates of the starting point.

    • goal (array like object of 2 numeric elements) – (y, x) or (lat, lon) coordinates of the goal location.

    • barriers (array like object, default=[]) – List of values inside the surface which are barriers (cannot cross).

    • x (str, default='x') – Name of the x coordinate in input surface raster.

    • y (str, default='x') – Name of the y coordinate in input surface raster.

    • connectivity (int, default=8) –

    • snap_start (bool, default=False) – Snap the start location to the nearest valid value before beginning pathfinding.

    • snap_goal (bool, default=False) – Snap the goal location to the nearest valid value before beginning pathfinding.

    Returns

    path_agg – 2D array of pathfinding values. All other input attributes are preserved.

    Return type

    xr.DataArray of the same type as surface.

    References

    • Red Blob Games: https://www.redblobgames.com/pathfinding/a-star/implementation.html # noqa

    • Nicholas Swift: https://medium.com/@nicholas.w.swift/easy-a-star-pathfinding-7e6689c7f7b2 # noqa

    Examples

    … sourcecode:: python

    >>> import numpy as np
    >>> import xarray as xr
    >>> from xrspatial import a_star_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]
    ... ]), dims=['lat', 'lon'])
    >>> height, width = agg.shape
    >>> _lon = np.linspace(0, width - 1, width)
    >>> _lat = np.linspace(height - 1, 0, height)
    >>> agg['lon'] = _lon
    >>> agg['lat'] = _lat
    
    >>> barriers = [0]  # set pixels with value 0 as barriers
    >>> start = (3, 0)
    >>> goal = (0, 1)
    >>> path_agg = a_star_search(agg, start, goal, barriers, 'lon', 'lat')
    >>> print(path_agg)
    <xarray.DataArray (lat: 5, lon: 4)>
    array([[       nan,        nan,        nan,        nan],
           [0.        ,        nan,        nan,        nan],
           [       nan, 1.41421356,        nan,        nan],
           [       nan,        nan, 2.82842712,        nan],
           [       nan, 4.24264069,        nan,        nan]])
    Coordinates:
      * lon      (lon) float64 0.0 1.0 2.0 3.0
      * lat      (lat) float64 4.0 3.0 2.0 1.0 0.0
    

    previous

    Pathfinding

    next

    Proximity

    © Copyright 2020-2022, makepath.

    Created using Sphinx 4.5.0.