API documentation
PolygonEnvironment
- class extremitypathfinder.PolygonEnvironment[source]
Bases:
object
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”
TODO document parameters
- 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
- property nr_edges: int
- property all_extremities: List[Tuple]
- property all_vertices: List[Tuple]
- store(boundary_coordinates: ndarray | List[Tuple[float | int, float | int]], list_of_hole_coordinates: ndarray | List[Tuple[float | int, float | int]], validate: bool = False)[source]
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)[source]
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
- prepare()[source]
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!).
- within_map(coords: ndarray) bool [source]
checks if the given coordinates lie within the boundary polygon and outside of all holes
- Parameters:
coords – numerical tuple representing coordinates
- Returns:
whether the given coordinate is a valid query point
- get_visible_idxs(origin: int, candidates: Iterable[int], coords: ndarray, vert_idx2repr: ndarray, vert_idx2dist: ndarray) Set[int] [source]
- 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] [source]
computes the shortest path and its length between start and goal node
- Parameters:
start_coordinates – a (x,y) coordinate tuple representing the start node
goal_coordinates – a (x,y) coordinate tuple representing the goal node
free_space_after – whether the created temporary search graph graph should be deleted after the query
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
.
- Returns:
a tuple of shortest path and its length. ([], None) if there is no possible path.