python package for fast geometric shortest path computation in 2D multi-polygon or grid environments based on visibility graphs.
Python >=3.12,<4 is accepted; CI currently tests CPython 3.12–3.14. Dependencies are NetworkX 3.x and NumPy >=2.3.3,<3. Python <3.12 and NumPy <2.3.3 are no longer supported.
The Python and NumPy floors stay within the September 2026 downstream support
window in NEP 29,
now superseded by SPEC 0.
Both policies exclude Python 3.11 by this date. This compatibility window is
narrower than CPython's security support lifetime. Review the floors for future
releases; SPEC 0 recommends dropping Python 3.12 in October 2026.
The dependency minimums are shared across all tested Python versions.
These recommendations do not promise upstream bug fixes for every included
NumPy release.
CI runs the full suite with minimum and latest compatible dependencies,
both with and without the numba extra, on every supported Python version.
The optional numba extra installs Numba >=0.63,<1 and SciPy >=1.16.1,<2.
SciPy supplies the compiled
linear algebra routines. Pip selects compatible versions; Numba may constrain
NumPy more tightly than the ordinary installation.
Acceleration depends on Numba/llvmlite platform support and adds installation
size and initial compilation time. Standard, GIL-enabled CPython is tested;
free-threaded builds and alternative interpreters are not covered by CI.
Quick Guide:
Install the package with the optional Numba extra for a significant speedup:
pip install "extremitypathfinder[numba]"from extremitypathfinder import PolygonEnvironment
environment = PolygonEnvironment()
# counter clockwise vertex numbering!
boundary_coordinates = [(0.0, 0.0), (10.0, 0.0), (9.0, 5.0), (10.0, 10.0), (0.0, 10.0)]
# clockwise numbering!
list_of_holes = [
[
(3.0, 7.0),
(5.0, 9.0),
(4.5, 7.0),
(5.0, 4.0),
],
]
environment.store(boundary_coordinates, list_of_holes, validate=False)
start_coordinates = (4.5, 1.0)
goal_coordinates = (4.0, 8.5)
path, length = environment.find_shortest_path(start_coordinates, goal_coordinates)For more refer to the documentation.