ExtremityPathfinder

https://extremitypathfinder.readthedocs.io/en/latest/
Admin
ExtremityPathfinder is a Python package for geometric shortest path computation in 2D multi-polygon...
Tokens:13,419
Snippets:151
Trust Score:9.6
Update:3 months ago
Show doc for...
Tokens:
Raw
### Install Extremity Pathfinder

Source: https://extremitypathfinder.readthedocs.io/en/latest/_sources/0_getting_started.rst.txt

Install the library using pip. This is the standard installation method.

```console
pip install extremitypathfinder
```

--------------------------------

### Install Extremity Pathfinder

Source: https://extremitypathfinder.readthedocs.io/en/latest/0_getting_started.html

Install the package using pip. Use the `[numba]` extra for Numba acceleration.

```bash
pip install extremitypathfinder
```

```bash
pip install extremitypathfinder[numba]
```

--------------------------------

### Install Extremity Pathfinder with Numba

Source: https://extremitypathfinder.readthedocs.io/en/latest/_sources/0_getting_started.rst.txt

Install the library with Numba support for significant speedup. This option has a larger installation footprint and initial compilation time.

```console
pip install extremitypathfinder[numba]
```

--------------------------------

### Basic Pathfinding Example

Source: https://extremitypathfinder.readthedocs.io/en/latest/_sources/0_getting_started.rst.txt

Demonstrates creating a PolygonEnvironment, storing boundary and hole coordinates, and finding the shortest path between two points. Ensure vertex numbering is consistent (counter-clockwise for boundary, clockwise for holes).

```python
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)
```

--------------------------------

### Install and Run Tox for Testing

Source: https://extremitypathfinder.readthedocs.io/en/latest/5_contributing.html

Install the tox testing tool and run all defined test environments. This is used to ensure code quality and test against multiple Python versions.

```bash
pip install tox
tox
```

--------------------------------

### Command Line Pathfinding

Source: https://extremitypathfinder.readthedocs.io/en/latest/1_usage.html

Execute pathfinding from the command line by providing a JSON file path and start/goal coordinates. The start and goal arguments must be passed as two separate float values.

```bash
extremitypathfinder <path2json_file> -s <start> -g <goal>
```

```bash
extremitypathfinder ./example.json -s 2.5 3.2 -g 7.9 6.8
```

--------------------------------

### Initialize PolygonEnvironment

Source: https://extremitypathfinder.readthedocs.io/en/latest/1_usage.html

Create a new instance of the PolygonEnvironment class for fast timezone queries. No specific setup is required before instantiation.

```python
from extremitypathfinder import PolygonEnvironment

environment = PolygonEnvironment()
```

--------------------------------

### Find Shortest Path

Source: https://extremitypathfinder.readthedocs.io/en/latest/1_usage.html

Query the environment to find the shortest path between start and goal coordinates. The visibility graph is pre-computed upon storing the environment. Set verify=False to accept any start and goal points without checking if they lie within the map.

```python
start_coordinates = (4.5, 1.0)
goal_coordinates = (4.0, 8.5)
path, length = environment.find_shortest_path(start_coordinates, goal_coordinates)
```

```python
path, length = environment.find_shortest_path(
    start_coordinates, goal_coordinates, verify=False
)
```

--------------------------------

### Call extremitypathfinder from Command Line

Source: https://extremitypathfinder.readthedocs.io/en/latest/_sources/1_usage.rst.txt

Execute the extremitypathfinder package directly from the command line. Specify the path to a JSON file containing environment data, and provide start and goal coordinates as float values.

```bash
extremitypathfinder ./example.json -s 2.5 3.2 -g 7.9 6.8
```

--------------------------------

### A* Pathfinding with Custom Heuristic

Source: https://extremitypathfinder.readthedocs.io/en/latest/_modules/extremitypathfinder/extremitypathfinder.html

Finds the shortest path between a start and goal node in a graph using the A* algorithm. A custom L2 distance heuristic is used, and the graph is modified in place. Handles cases where no path exists.

```python
        # apply mapping to start and goal index as well
        start_mapped = utils.find_identical_single(
            start, graph.nodes, self.reprs_n_distances
        )
        if start_mapped != start:
            nx.relabel_nodes(graph, {start: start_mapped}, copy=False)

        goal_mapped = utils.find_identical_single(
            goal, graph.nodes, self.reprs_n_distances
        )
        if goal_mapped != goal_mapped:
            nx.relabel_nodes(graph, {goal: goal_mapped}, copy=False)

        self._idx_start_tmp, self._idx_goal_tmp = (
            start_mapped,
            goal_mapped,
        )  # for plotting

        def l2_distance(n1, n2):
            return utils.get_distance(n1, n2, self.reprs_n_distances)

        try:
            id_path = nx.astar_path(
                graph, start_mapped, goal_mapped, heuristic=l2_distance, weight="weight"
            )
        except nx.exception.NetworkXNoPath:
            return [], None

        # clean up
        # TODO re-use the same graph. need to keep track of all merged edges
        # if start_mapped == start:
        #     graph.remove_node(start)
        # if goal_mapped==goal:
        #     graph.remove_node(goal)
        # nr_edges_after = len(graph.edges)
        # if not nr_edges_after == nr_edges_before:
        #     raise ValueError

        if free_space_after:
            del graph  # free the memory
        else:
            self.temp_graph = graph

        # compute distance
        distance = 0.0
        v1 = id_path[0]
        for v2 in id_path[1:]:
            distance += l2_distance(v1, v2)
            v1 = v2

        # extract the coordinates from the path
        path = [tuple(coords[i]) for i in id_path]
        return path, distance

```

--------------------------------

### Pathfinding Query in Extremity Pathfinder

Source: https://extremitypathfinder.readthedocs.io/en/latest/_modules/extremitypathfinder/extremitypathfinder.html

This function calculates the shortest path between start and goal coordinates within a loaded environment. It verifies if the points are within the map boundaries and constructs a temporary visibility graph to find the path. Returns the path and its length, or ([], None) if no path exists.

```python
def find_path(self, start_coordinates: tuple[float, float], goal_coordinates: tuple[float, float], free_space_after: bool = True, verify: bool = True) -> tuple[list[tuple[float, float]], float | None]:
        """
        Path planning query: finds the shortest path between start and goal coordinates.

        :param start_coordinates: a (x,y) coordinate tuple representing the start node
        :param goal_coordinates:  a (x,y) coordinate tuple representing the goal node
        :param free_space_after: whether the created temporary search graph graph
            should be deleted after the query
        :param verify: whether it should be checked if start and goal points really lie inside the environment.
         if points close to or on polygon edges should be accepted as valid input, set this to ``False``.
        :return: a tuple of shortest path and its length. ([], None) if there is no possible path.
        """
        # path planning query:
        # make sure the map has been loaded and prepared
        if self.boundary_polygon is None:
            raise ValueError("No Polygons have been loaded into the map yet.")

        coords_start = np.array(start_coordinates, dtype=float)
        coords_goal = np.array(goal_coordinates, dtype=float)
        if verify and not self.within_map(coords_start):
            raise ValueError("start point does not lie within the map")
        if verify and not self.within_map(coords_goal):
            raise ValueError("goal point does not lie within the map")

        if np.array_equal(coords_start, coords_goal):
            # start and goal are identical and can be reached instantly
            return [start_coordinates, goal_coordinates], 0.0

        start = self.idx_start
        goal = self.idx_goal
        # temporarily extend data structure
        # Note: start and goal nodes could be identical with one ore more of the vertices
        # BUT: this is an edge case -> compute visibility as usual and later try to merge with the graph
        coords = np.append(self.coords, (coords_start, coords_goal), axis=0)
        self._coords_tmp = coords  # for plotting including the start and goal indices

        # check the goal node first (earlier termination possible)
        origin = goal
        # the visibility of only the graph nodes has to be checked (not all extremities!)
        # IMPORTANT: also check if the start node is visible from the goal node!
        candidate_idxs: Set[int] = set(self.graph.nodes)
        candidate_idxs.add(start)
        repr_n_dists = utils.cmp_reps_n_distances(origin, coords)
        self.reprs_n_distances[origin] = repr_n_dists
        vert_idx2repr, vert_idx2dist = repr_n_dists
        visibles_goal = self.get_visible_idxs(
            origin, candidate_idxs, coords, vert_idx2repr, vert_idx2dist
        )
        if len(visibles_goal) == 0:
            # The goal node does not have any neighbours. Hence there is not possible path to the goal.
            return [], None

        # IMPORTANT geometrical property of this problem: it is always shortest to directly reach a node
        #   instead of visiting other nodes first (there is never an advantage through reduced edge weight)
        # -> when goal is directly reachable, there can be no other shorter path to it. Terminate
        if start in visibles_goal:
            d = vert_idx2dist[start]
            return [start_coordinates, goal_coordinates], d

        # create temporary graph
        # DirectedHeuristicGraph implements __deepcopy__() to not change the original precomputed self.graph
        # but to still not create real copies of vertex instances!
        graph = self.graph.copy()
        # TODO avoid real copy to make make more performant
        # graph = self.graph
        # nr_edges_before = len(graph.edges)

        # add edges: extremity (i) <-> goal
        # Note: also here unnecessary edges in the graph could be deleted
        # optimising the graph here however is more expensive than beneficial,
        # as the graph is only being used for a single query
        for i in visibles_goal:
            graph.add_edge(i, goal, weight=vert_idx2dist[i])

        origin = start
        # the visibility of only the graphs nodes have to be checked
        # the goal node does not have to be considered, because of the earlier check
        repr_n_dists = utils.cmp_reps_n_distances(origin, coords)
        self.reprs_n_distances[origin] = repr_n_dists
        vert_idx2repr, vert_idx2dist = repr_n_dists
        visibles_start = self.get_visible_idxs(
            origin, candidate_idxs, coords, vert_idx2repr, vert_idx2dist
        )

        if len(visibles_start) == 0:
            # The start node does not have any neighbours. Hence there is no possible path to the goal.
            return [], None

        # add edges: start <-> extremity (i)
        for i in visibles_start:
            graph.add_edge(start, i, weight=vert_idx2dist[i])

        # TODO: use Dijkstra or A* to find the shortest path in the temporary graph
        # path = nx.shortest_path(graph, source=start, target=goal, weight='weight')
        # length = nx.shortest_path_length(graph, source=start, target=goal, weight='weight')
        # return path, length
        # For now, return empty path as the actual pathfinding logic is not implemented here.
        return [], None

```

--------------------------------

### Get Visible Indices

Source: https://extremitypathfinder.readthedocs.io/en/latest/_modules/extremitypathfinder/extremitypathfinder.html

Finds all directly visible candidate indices from a given origin index, excluding points with zero distance. Used for visibility graph construction.

```python
def get_visible_idxs(
        self,
        origin: int,
        candidates: Iterable[int],
        coords: np.ndarray,
        vert_idx2repr: np.ndarray,
        vert_idx2dist: np.ndarray,
    ) -> Set[int]:
        # Note: points with equal coordinates should not be considered visible (will be merged later)
        candidates = {i for i in candidates if not vert_idx2dist[i] == 0.0}
        edge_idxs2check = set(range(self.nr_edges))
        return utils.find_visible(
            origin,
            candidates,
            edge_idxs2check,
            coords,
            vert_idx2repr,
            vert_idx2dist,
            self.edge_vertex_idxs,
            self.vertex_edge_idxs,
            self.extremity_mask,
        )
```

--------------------------------

### Basic Pathfinding with PolygonEnvironment

Source: https://extremitypathfinder.readthedocs.io/en/latest/0_getting_started.html

Demonstrates initializing a PolygonEnvironment, storing boundary and hole coordinates, and finding the shortest path between two points. Ensure vertex numbering is consistent (counter-clockwise for boundary, clockwise for holes).

```python
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)

```

--------------------------------

### Prepare Visibility Graph

Source: https://extremitypathfinder.readthedocs.io/en/latest/_modules/extremitypathfinder/extremitypathfinder.html

Computes and stores an optimized visibility graph for path planning. Ensures idempotency by skipping if already prepared.

```python
def prepare(self):
        """Computes a visibility graph optimized (=reduced) for path planning and stores it

        Computes all directly reachable extremities based on visibility and their distance to each other
        pre-procesing of the map. pre-computation for faster shortest path queries
        optimizes graph further at construction time

        NOTE: initialise the graph with all extremities.
        even if a node has no edges (visibility to other extremities, dangling node), 
        it must still be included!

        .. note::
            Multiple polygon vertices might have identical coords_rel.
            They must be treated as distinct vertices here, since their attached edges determine visibility.
            In the created graph however, these nodes must be merged at the end to avoid ambiguities!

        .. note::
            Pre computing the shortest paths between all directly reachable extremities
            and storing them in the graph would not be an advantage, because then the graph is fully connected.
            A* would visit every node in the graph at least once (-> disadvantage!)
        """
        if self.prepared:  # idempotent
            warnings.warn(
                "called .prepare() on already prepared map. skipping...", stacklevel=1
            )
            return

        self.graph = utils.compute_graph(
            self.nr_edges,
            self.extremity_indices,
            self.reprs_n_distances,
            self.coords,
            self.edge_vertex_idxs,
            self.extremity_mask,
            self.vertex_edge_idxs,
        )
        self.prepared = True
```

--------------------------------

### Speed Benchmark Results

Source: https://extremitypathfinder.readthedocs.io/en/latest/7_performance.html

These results show the average environment preparation time and query execution time, averaged over 1,000 runs on a MacBook Pro.

```text
speed_benchmarks.py::test_env_preparation_speed PASSED                   [ 50%]
avg. environment preparation time 7.4e-03 s/run, 1.4e+02 runs/s
averaged over 1,000 runs

speed_benchmarks.py::test_query_speed PASSED                             [100%]
avg. query time 7.1e-04 s/run, 1.4e+03 runs/s
averaged over 1,000 runs

```

--------------------------------

### Speed Benchmark Results

Source: https://extremitypathfinder.readthedocs.io/en/latest/_sources/7_performance.rst.txt

Displays the results of speed benchmarks for environment preparation and query execution. Shows average time per run and runs per second.

```text
speed_benchmarks.py::test_env_preparation_speed PASSED                   [ 50%]
avg. environment preparation time 7.4e-03 s/run, 1.4e+02 runs/s
averaged over 1,000 runs

speed_benchmarks.py::test_query_speed PASSED                             [100%]
avg. query time 7.1e-04 s/run, 1.4e+03 runs/s
averaged over 1,000 runs
```

--------------------------------

### Initialize PlottingEnvironment

Source: https://extremitypathfinder.readthedocs.io/en/latest/1_usage.html

Create an instance of PlottingEnvironment to automatically generate plots for pathfinding steps. Specify the directory for saving plots.

```python
from extremitypathfinder.plotting import PlottingEnvironment

environment = PlottingEnvironment(plotting_dir="path/to/plots")
environment.store(boundary_coordinates, list_of_holes, validate=True)
path, distance = environment.find_shortest_path(start, end)
```

--------------------------------

### prepare

Source: https://extremitypathfinder.readthedocs.io/en/latest/4_api.html

Computes a visibility graph optimized for path planning and stores it. This method pre-processes the map to determine directly reachable extremities and their distances, optimizing for faster shortest path queries.

```APIDOC
## prepare

### Description
Computes a visibility graph optimized (=reduced) for path planning and stores it. Computes all directly reachable extremities based on visibility and their distance to each other as a pre-processing step for faster shortest path queries. The graph is further optimized at construction time.

NOTE: The graph must be initialized with all extremities. Even dangling nodes (without edges) must be included.

Note: Multiple polygon vertices might have identical coords_rel. They must be treated as distinct vertices initially, but merged at the end to avoid ambiguities.

Note: Pre-computing shortest paths between all directly reachable extremities and storing them would result in a fully connected graph, which is disadvantageous for A* search as it would visit every node at least once.

### Method
`prepare()`
```

--------------------------------

### Cache and Load Environment using Pickle

Source: https://extremitypathfinder.readthedocs.io/en/latest/1_usage.html

Export the current environment to a pickle file for caching and later use. Load the environment from a pickle file using the load_pickle function.

```python
environment.export_pickle(path="./pickle_file.pickle")

from extremitypathfinder.extremitypathfinder import load_pickle

environment = load_pickle(path="./pickle_file.pickle")
```

--------------------------------

### PlottingEnvironment

Source: https://extremitypathfinder.readthedocs.io/en/latest/_sources/4_api.rst.txt

The PlottingEnvironment class provides methods for storing data, preparing it for pathfinding, and finding the shortest path.

```APIDOC
## PlottingEnvironment

### Description
Provides methods for storing data, preparing it for pathfinding, and finding the shortest path.

### Methods
- **store**
- **prepare**
- **find_shortest_path**
```

--------------------------------

### Commit and Push Changes

Source: https://extremitypathfinder.readthedocs.io/en/latest/5_contributing.html

Stage all changes, commit them with a descriptive message, and push the branch to your GitHub fork.

```bash
git add .
git commit -m "Your detailed description of your changes."
git push origin name-of-your-bugfix-or-feature
```

--------------------------------

### PolygonEnvironment Initialization and Storage

Source: https://extremitypathfinder.readthedocs.io/en/latest/4_api.html

Saves the passed input polygons in the environment. Polygons must meet specific formatting requirements. Use `store_grid_world` to convert grid-based obstacles into a polygon environment.

```python
store(_boundary_coordinates : ndarray | List[Tuple[float | int, float | int]]_, _list_of_hole_coordinates : ndarray | List[Tuple[float | int, float | int]]_, _validate : bool = False_)
```

```python
store_grid_world(_size_x : int_, _size_y : int_, _obstacle_iter : Iterable[Tuple[float | int, float | int]]_, _simplify : bool = True_, _validate : bool = False_)
```

--------------------------------

### PolygonEnvironment.store

Source: https://extremitypathfinder.readthedocs.io/en/latest/_modules/extremitypathfinder/extremitypathfinder.html

Saves the provided boundary and hole polygons to the environment. This method prepares the environment for pathfinding queries by processing the input polygons and compiling necessary data structures. It includes validation options to ensure the input polygons meet specific geometric requirements.

```APIDOC
## PolygonEnvironment.store

### Description
Saves the passed input polygons in the environment. This method processes the boundary and hole coordinates, compiles internal data structures, and prepares the environment for pathfinding. It can optionally validate the input polygons against a set of requirements.

### Method
`store(boundary_coordinates: InputCoordList, list_of_hole_coordinates: InputCoordList, validate: bool = False)`

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
None

### Parameters
*   **boundary_coordinates** (InputCoordList) - Required - Array of coordinates defining the outer boundary polygon in counter-clockwise order.
*   **list_of_hole_coordinates** (InputCoordList) - Required - Array of arrays, where each inner array contains coordinates defining a hole polygon in clockwise order.
*   **validate** (bool) - Optional - If True, the input polygons will be validated against requirements such as minimum vertices, no self-intersections, and correct edge numbering conventions. Defaults to False.

### Request Example
```python
# Example usage (assuming environment is an instance of PolygonEnvironment)
boundary = [(0, 0), (10, 0), (10, 10), (0, 10)]
holes = [[(2, 2), (8, 2), (8, 8), (2, 8)]]
environment.store(boundary, holes, validate=True)
```

### Response
None. This method modifies the internal state of the `PolygonEnvironment` object.

#### Success Response (200)
N/A

#### Response Example
N/A

### Raises
*   **AssertionError**: Raised if `validate` is True and the input polygons do not meet the specified requirements (e.g., incorrect vertex order, self-intersections, insufficient vertices).
```

--------------------------------

### Run Specific Tox Test Environments

Source: https://extremitypathfinder.readthedocs.io/en/latest/5_contributing.html

During development, you can run specific tox environments, such as the codestyle check, to quickly verify your changes.

```bash
tox -e codestyle
```

--------------------------------

### Create a New Branch for Local Development

Source: https://extremitypathfinder.readthedocs.io/en/latest/5_contributing.html

Before making changes, create a new branch for your bug fix or feature development using Git.

```bash
git checkout -b name-of-your-bugfix-or-feature
```

--------------------------------

### Store Environment with Polygons

Source: https://extremitypathfinder.readthedocs.io/en/latest/1_usage.html

Store boundary and hole coordinates to define the environment. Ensure coordinates follow specific numbering conventions (counter-clockwise for boundary, clockwise for holes) and geometric rules. Set validate=False to skip data validation.

```python
# 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)
```

--------------------------------

### Find Shortest Path

Source: https://extremitypathfinder.readthedocs.io/en/latest/_modules/extremitypathfinder/extremitypathfinder.html

Computes the shortest path and its length between two specified coordinate points. Supports optional verification and free space checks.

```python
def find_shortest_path(
        self,
        start_coordinates: InputCoord,
        goal_coordinates: InputCoord,
        free_space_after: bool = True,
        verify: bool = True,
    ) -> Tuple[Path, Length]:
        """computes the shortest path and its length between start and goal node

        
```

--------------------------------

### Store Grid World

Source: https://extremitypathfinder.readthedocs.io/en/latest/1_usage.html

Convert and store a grid world into the environment. Define grid dimensions and an iterator of obstacle coordinates. Set simplify=False and validate=False to control simplification and validation.

```python
size_x, size_y = 19, 10
obstacle_iter = [  # (x,y),
    # obstacles changing boundary
    (0, 1),
    (1, 1),
    (2, 1),
    (3, 1),
    (17, 9),
    (17, 8),
    (17, 7),
    (17, 5),
    (17, 4),
    (17, 3),
    (17, 2),
    (17, 1),
    (17, 0),
    # hole 1
    (5, 5),
    (5, 6),
    (6, 6),
    (6, 7),
    (7, 7),
    # hole 2
    (7, 5),
]
environment.store_grid_world(
    size_x, size_y, obstacle_iter, simplify=False, validate=False
)
```

--------------------------------

### Export Map to Pickle

Source: https://extremitypathfinder.readthedocs.io/en/latest/_modules/extremitypathfinder/extremitypathfinder.html

Saves the current map class instance to a pickle file for later use. Useful for persisting map data.

```python
def export_pickle(self, path: str = DEFAULT_PICKLE_NAME):
        print("storing map class in:", path)
        with open(path, "wb") as f:
            pickle.dump(self, f)
        print("done.\n")
```

--------------------------------

### PolygonEnvironment Class

Source: https://extremitypathfinder.readthedocs.io/en/latest/4_api.html

The PolygonEnvironment class allows for the use of polygons to represent 2D environments for pathfinding. It maintains a prepared environment for efficient path queries using an optimized visibility graph.

```APIDOC
## Class: PolygonEnvironment

### Description
Class allowing to use polygons to represent “2D environments” and use them for path finding. Keeps a “loaded” and prepared environment for consecutive path queries. Internally uses a visibility graph optimised for shortest path finding.

### Attributes
* **prepared**: bool = False
* **holes**: List[ndarray]
* **extremity_indices**: ndarray
* **reprs_n_distances**: Dict[int, ndarray]
* **graph**: Graph
* **temp_graph**: Graph | None = None
* **boundary_polygon**: ndarray
* **coords**: ndarray
* **edge_vertex_idxs**: ndarray
* **extremity_mask**: ndarray
* **vertex_edge_idxs**: ndarray

### Properties
* **nr_edges**: int
* **all_extremities**: List[Tuple]
* **all_vertices**: List[Tuple]

### Methods
#### `store(_boundary_coordinates : ndarray | List[Tuple[float | int, float | int]]_, _list_of_hole_coordinates : ndarray | List[Tuple[float | int, float | int]]_, _validate : bool = False_)`
Saves the passed input polygons in the environment.

**Note**: The passed polygons must meet these requirements:
  * Given as numpy or python array of coordinate tuples: `[(x1,y1), (x2,y2,)...]`
  * No repetition of the first point at the end
  * At least 3 vertices (no single points or lines allowed)
  * No consequent vertices with identical coordinates in the polygons (same coordinates allowed)
  * No self intersections
  * Edge numbering has to follow these conventions: boundary polygon counter clockwise, holes clockwise.

**Parameters**:
  * **boundary_coordinates** – array of coordinates with counter clockwise edge numbering
  * **list_of_hole_coordinates** – array of coordinates with clockwise edge numbering
  * **validate** – whether the requirements of the data should be tested

**Raises**:
  * **AssertionError** – when validate=True and the input is invalid.

#### `store_grid_world(_size_x : int_, _size_y : int_, _obstacle_iter : Iterable[Tuple[float | int, float | int]]_, _simplify : bool = True_, _validate : bool = False_)`
Convert a grid-like into a polygon environment and save it.

**Prerequisites**: grid world must not have single non-obstacle cells which are surrounded by obstacles (“white cells in black surrounding” = useless for path planning).

**Parameters**:
  * **size_x** – the horizontal grid world size
  * **size_y** – the vertical grid world size
  * **obstacle_iter** – an iterable of coordinate pairs (x,y) representing blocked grid cells (obstacles)
  * **validate** – whether the input should be validated
  * **simplify** – whether the polygons should be simplified or not. reduces edge amount, allow diagonal edges.

#### `export_pickle(_path : str = 'environment.pickle'_)`
Exports the environment to a pickle file.

#### `prepare()`
Prepares the environment for pathfinding queries.

#### `within_map(_coords : ndarray_)`
Checks if the given coordinates are within the map boundaries.

#### `get_visible_idxs(_idx : int_)`
Returns the indices of vertices visible from the given vertex index.

#### `find_shortest_path(_start_coords : Tuple[float, float], _end_coords : Tuple[float, float])`
Finds the shortest path between two sets of coordinates within the environment.
```

--------------------------------

### PolygonEnvironment Pickle Export

Source: https://extremitypathfinder.readthedocs.io/en/latest/4_api.html

Exports the current environment to a pickle file for later use. Defaults to 'environment.pickle'.

```python
export_pickle(_path : str = 'environment.pickle'_)
```

--------------------------------

### PolygonEnvironment Class Definition

Source: https://extremitypathfinder.readthedocs.io/en/latest/_modules/extremitypathfinder/extremitypathfinder.html

Defines the PolygonEnvironment class for pathfinding in 2D polygon environments. It initializes internal data structures and prepares the environment for path queries.

```python
import pickle
import warnings
from typing import Dict, Iterable, List, Optional, Set, Tuple

import networkx as nx
import numpy as np

from extremitypathfinder import configs
from extremitypathfinder import types as t
from extremitypathfinder import utils
from extremitypathfinder.configs import DEFAULT_PICKLE_NAME
from extremitypathfinder.types import (
    InputCoord,
    InputCoordList,
    Length,
    ObstacleIterator,
    Path,
)




[docs]
class PolygonEnvironment:
    """Class allowing to use polygons to represent "2D environments" and use them for path finding.

    Keeps a "loaded" and prepared environment for consecutive path queries.
    Internally uses a visibility graph optimised for shortest path finding.
    General approach and some optimisations theoretically described in:
    [1] Vinther, Anders Strand-Holm, Magnus Strand-Holm Vinther, and Peyman Afshani.
    "Pathfinding in Two-dimensional Worlds
    <https://www.cs.au.dk/~gerth/advising/thesis/anders-strand-holm-vinther_magnus-strand-holm-vinther.pdf>"

    TODO document parameters
    """

    nr_edges: int
    prepared: bool = False
    holes: List[np.ndarray]
    extremity_indices: np.ndarray
    reprs_n_distances: Dict[int, np.ndarray]
    graph: t.Graph
    # TODO
    temp_graph: Optional[t.Graph] = (
        None  # for storing and plotting the graph during a query
    )
    boundary_polygon: np.ndarray
    coords: np.ndarray
    edge_vertex_idxs: np.ndarray
    extremity_mask: np.ndarray
    vertex_edge_idxs: np.ndarray

    @property
    def nr_edges(self) -> int:
        return self.nr_vertices

    @property
    def all_extremities(self) -> List[Tuple]:
        coords = self.coords
        return [tuple(coords[i]) for i in self.extremity_indices]

    @property
    def all_vertices(self) -> List[Tuple]:
        coords = self.coords
        return [tuple(coords[i]) for i in range(self.nr_vertices)]




[docs]
    def store(
        self,
        boundary_coordinates: InputCoordList,
        list_of_hole_coordinates: InputCoordList,
        validate: bool = False,
    ):
        """saves the passed input polygons in the environment

        .. note:: the passed polygons must meet these requirements:

            * given as numpy or python array of coordinate tuples: ``[(x1,y1), (x2,y2,)...]``
            * no repetition of the first point at the end
            * at least 3 vertices (no single points or lines allowed)
            * no consequent vertices with identical coordinates in the polygons (same coordinates allowed)
            * no self intersections
            * edge numbering has to follow these conventions: boundary polygon counter clockwise, holes clockwise

        :param boundary_coordinates: array of coordinates with counter clockwise edge numbering
        :param list_of_hole_coordinates: array of coordinates with clockwise edge numbering
        :param validate: whether the requirements of the data should be tested

        :raises AssertionError: when validate=True and the input is invalid.
        """
        self.prepared = False
        # loading the map
        boundary_coordinates = np.array(boundary_coordinates, dtype=configs.DTYPE_FLOAT)
        list_of_hole_coordinates = [
            np.array(hole_coords, dtype=configs.DTYPE_FLOAT)
            for hole_coords in list_of_hole_coordinates
        ]
        if validate:
            utils.check_data_requirements(
                boundary_coordinates, list_of_hole_coordinates
            )

        # Note: independent copy!
        self.holes = list_of_hole_coordinates
        self.boundary_polygon = boundary_coordinates

        # TODO redundant data. refactor all functions to only use one format
        (
            self.coords,
            self.extremity_indices,
            self.extremity_mask,
            self.vertex_edge_idxs,
            self.edge_vertex_idxs,
        ) = utils.compile_polygon_datastructs(
            boundary_coordinates, list_of_hole_coordinates
        )

        nr_total_pts = self.edge_vertex_idxs.shape[0]
        self.nr_vertices = nr_total_pts
        self.reprs_n_distances = utils.cmp_reps_n_distance_dict(
            self.coords, self.extremity_indices
        )

        # start and goal points will be stored after all polygon coordinates
        self.idx_start = nr_total_pts
        self.idx_goal = nr_total_pts + 1

        self.prepare()





[docs]
    def store_grid_world(
        self,
        size_x: int,
        size_y: int,
        obstacle_iter: ObstacleIterator,
        simplify: bool = True,
        validate: bool = False,
    ):
        """Convert a grid-like into a polygon environment and save it

```

--------------------------------

### find_shortest_path

Source: https://extremitypathfinder.readthedocs.io/en/latest/4_api.html

Computes the shortest path and its length between two specified coordinates within the environment.

```APIDOC
## find_shortest_path

### Description
Computes the shortest path and its length between start and goal node.

### Method
`find_shortest_path(_start_coordinates: Tuple[float | int, float | int], _goal_coordinates: Tuple[float | int, float | int], _free_space_after: bool = True, _verify: bool = True) -> Tuple[List[Tuple[float, float]], float | None]`

### Parameters
#### Path Parameters
- **start_coordinates** (Tuple[float | int, float | int]) - Description: a (x,y) coordinate tuple representing the start node
- **goal_coordinates** (Tuple[float | int, float | int]) - Description: a (x,y) coordinate tuple representing the goal node
- **free_space_after** (bool) - Optional - Description: whether the created temporary search graph graph should be deleted after the query. Defaults to True.
- **verify** (bool) - Optional - Description: whether it should be checked if start and goal points really lie inside the environment. if points close to or on polygon edges should be accepted as valid input, set this to `False`. Defaults to True.

### Returns
- Tuple[List[Tuple[float, float]], float | None] - a tuple of shortest path and its length. ([], None) if there is no possible path.
```

--------------------------------

### export_pickle

Source: https://extremitypathfinder.readthedocs.io/en/latest/_modules/extremitypathfinder/extremitypathfinder.html

Exports the current map object to a pickle file for later use. This allows for saving and loading the pre-processed map state.

```APIDOC
## export_pickle

### Description
Exports the current map object to a pickle file.

### Method
`export_pickle(self, path: str = DEFAULT_PICKLE_NAME)`

### Parameters
* **path** (str) - Optional - The file path where the pickle file will be saved. Defaults to `DEFAULT_PICKLE_NAME`.
```

--------------------------------

### get_visible_idxs

Source: https://extremitypathfinder.readthedocs.io/en/latest/4_api.html

Retrieves the indices of candidate points that are visible from a given origin point.

```APIDOC
## get_visible_idxs

### Description
Retrieves the indices of candidate points that are visible from a given origin point.

### Method
`get_visible_idxs(_origin: int, _candidates: Iterable[int], _coords: ndarray, _vert_idx2repr: ndarray, _vert_idx2dist: ndarray) -> Set[int]`
```

--------------------------------

### Check if Coordinates are Within Map Boundaries

Source: https://extremitypathfinder.readthedocs.io/en/latest/_modules/extremitypathfinder/extremitypathfinder.html

Verifies if a given coordinate point is inside the map's boundary polygon and outside any defined holes. Returns a boolean indicating validity.

```python
def within_map(self, coords: np.ndarray) -> bool:
        """checks if the given coordinates lie within the boundary polygon and outside of all holes

        :param coords: numerical tuple representing coordinates
        :return: whether the given coordinate is a valid query point
        """
        return utils.is_within_map(coords, self.boundary_polygon, self.holes)
```

--------------------------------

### within_map

Source: https://extremitypathfinder.readthedocs.io/en/latest/4_api.html

Checks if a given coordinate lies within the boundary polygon and outside of any holes.

```APIDOC
## within_map

### Description
Checks if the given coordinates lie within the boundary polygon and outside of all holes.

### Method
`within_map(_coords: ndarray) -> bool`

### Parameters
#### Path Parameters
- **coords** (ndarray) - Description: numerical tuple representing coordinates

### Returns
- bool - whether the given coordinate is a valid query point
```
Tokens:
Raw