Metadata-Version: 2.4
Name: extremitypathfinder
Version: 3.0.0
Summary: python package for fast shortest path computation on 2D polygon or grid maps
Keywords: path-planning,path-finding,shortest-path,visibility,graph,polygon,grid,map,robotics,navigation,offline
Author: Jannik Kissinger
Author-email: Jannik Kissinger <github@michelfe.it>
License-Expression: MIT AND BSD-3-Clause
License-File: LICENSE
License-File: LICENSES/networkx.txt
Classifier: Development Status :: 5 - Production/Stable
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Information Technology
Classifier: Intended Audience :: Science/Research
Classifier: Natural Language :: English
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Classifier: Programming Language :: Python :: 3.15
Classifier: Topic :: Scientific/Engineering
Classifier: Topic :: Scientific/Engineering :: Artificial Intelligence
Classifier: Topic :: Education
Classifier: Topic :: Games/Entertainment
Requires-Dist: networkx>=3,<4
Requires-Dist: numpy>=2.3.3,<3
Requires-Dist: numba>=0.63,<1 ; extra == 'numba'
Requires-Dist: scipy>=1.16.1,<2 ; extra == 'numba'
Requires-Python: >=3.12, <4
Project-URL: Homepage, https://extremitypathfinder.readthedocs.io/en/latest/
Project-URL: Documentation, https://extremitypathfinder.readthedocs.io/en/latest/
Project-URL: Repository, https://github.com/jannikmi/extremitypathfinder
Provides-Extra: numba
Description-Content-Type: text/x-rst

===================
extremitypathfinder
===================

..
    Note: can't include the badges file from the docs here, as it won't render on PyPI -> sync manually


.. image:: https://github.com/jannikmi/extremitypathfinder/actions/workflows/build.yml/badge.svg?branch=master
    :target: https://github.com/jannikmi/extremitypathfinder/actions?query=branch%3Amaster

.. image:: https://readthedocs.org/projects/extremitypathfinder/badge/?version=latest
    :alt: documentation status
    :target: https://extremitypathfinder.readthedocs.io/en/latest/?badge=latest

.. image:: https://img.shields.io/pypi/wheel/extremitypathfinder.svg
    :target: https://pypi.python.org/pypi/extremitypathfinder

.. image:: https://img.shields.io/badge/pre--commit-enabled-brightgreen?logo=pre-commit&logoColor=white
   :target: https://github.com/pre-commit/pre-commit
   :alt: pre-commit

.. image:: https://pepy.tech/badge/extremitypathfinder
    :alt: Total PyPI downloads
    :target: https://pepy.tech/project/extremitypathfinder

.. image:: https://img.shields.io/pypi/v/extremitypathfinder.svg
    :alt: latest version on PyPI
    :target: https://pypi.python.org/pypi/extremitypathfinder

.. image:: https://img.shields.io/badge/code%20style-black-000000.svg
    :target: https://github.com/psf/black

python package for fast geometric shortest path computation in 2D multi-polygon or grid environments based on visibility graphs.


.. image:: ./docs/_static/title_demo_plot.png


Supported versions
------------------

Python >=3.12,<4 is accepted; CI currently tests CPython 3.12–3.15.
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 <https://numpy.org/neps/nep-0029-deprecation_policy>`__,
now superseded by `SPEC 0 <https://scientific-python.org/specs/spec-0000/>`__.
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 declared dependency minimums are the same for all Python versions.
On Python 3.15 they provide no wheels, so CI tests the oldest releases that do instead:
NumPy 2.5.2, SciPy 1.18.1 and Numba 0.68.0.
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:

.. code-block:: console

    pip install "extremitypathfinder[numba]"


.. code-block:: python

    from extremitypathfinder import 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 = PolygonEnvironment(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)


Grids with blocked cells (obstacles) can be converted into polygon environments as well.
Coordinates refer to the corners of the grid cells, i.e. cell ``(x, y)`` spans ``[x, x+1] x [y, y+1]``:

.. code-block:: python

    size_x, size_y = 5, 3
    obstacle_iter = [(2, 1), (3, 1)]  # blocked grid cells (x, y)
    environment = PolygonEnvironment.from_grid(size_x, size_y, obstacle_iter)
    path, length = environment.find_shortest_path((0.5, 0.5), (4.5, 2.5))


For more refer to the `documentation <https://extremitypathfinder.readthedocs.io/en/latest/>`__.
Upgrading from version 2.x? See the `upgrade guide <https://extremitypathfinder.readthedocs.io/en/latest/2_upgrading.html>`__.


Also see:
`GitHub <https://github.com/jannikmi/extremitypathfinder>`__,
`PyPI <https://pypi.python.org/pypi/extremitypathfinder/>`__
