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
export_pickle(path: str = 'environment.pickle')[source]
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.

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
within_map(coords: numpy.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

PlottingEnvironment