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
-
__init__
¶ Initialize self. See help(type(self)) for accurate signature.
-
all_extremities
¶
-
all_vertices
¶
-
find_shortest_path
(start_coordinates: Tuple[Union[float, int], Union[float, int]], goal_coordinates: Tuple[Union[float, int], Union[float, int]], free_space_after: bool = True, verify: bool = True) → Tuple[List[Tuple[float, float]], Optional[float]][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.
-
get_visible_idxs
(origin: int, candidates: Iterable[int], coords: numpy.ndarray, vert_idx2repr: numpy.ndarray, vert_idx2dist: numpy.ndarray) → Set[int][source]¶
-
nr_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!).
-
prepared
= False¶
-
store
(boundary_coordinates: Union[numpy.ndarray, List[Tuple[Union[float, int], Union[float, int]]]], list_of_hole_coordinates: Union[numpy.ndarray, List[Tuple[Union[float, int], Union[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.
- given as numpy or python array of coordinate tuples:
-
store_grid_world
(size_x: int, size_y: int, obstacle_iter: Iterable[Tuple[Union[float, int], Union[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
-
temp_graph
= None¶
-