extremitypathfinder
Python package for fast geometric shortest path computation in 2D multi-polygon or grid environments based on visibility graphs.
from extremitypathfinder import PolygonEnvironment
# a complete example: cf. Getting Started
environment = PolygonEnvironment(boundary_coordinates, list_of_holes)
path, length = environment.find_shortest_path(start_coordinates, goal_coordinates)
Features
Exact shortest paths: the Euclidean shortest path between any two points of the free space, not an approximation on a grid or mesh.
Fast repeated queries: the visibility graph of an environment is computed once, each query then only connects its start and goal to it. Only the protruding corners (“extremities”) become graph nodes, which keeps the graph small.
Polygon environments: a boundary polygon with holes, or holes only (unbounded environments). Polygons may touch and overlap each other. Touching obstacles form a wall that paths cannot pass. The polygons are used directly: no triangulation or navigation mesh is needed.
Grids: convert a grid with blocked cells into a polygon environment.
Few dependencies: NumPy and NetworkX. Optional Numba acceleration.
Extras: input validation, plotting (Matplotlib), caching environments with pickle, and a command line interface.
Where to start
New to the package? Getting started shows the installation and a first example, Usage explains all features.
Upgrading from version 2.x? Follow the upgrade guide.
Curious how it works? About gives an illustrated overview, the engineering design describes the architecture and the algorithms.
Comparing packages? Alternatives lists similar packages and how they differ.
Looking for a specific function? See the API reference.
Want to contribute? Read the contribution guidelines.
User Guide
Development