API documentation


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


Initialize self. See help(type(self)) for accurate signature.

boundary_polygon = None
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

  • 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 self.temp_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.

a tuple of shortest path and its length. ([], None) if there is no possible path.

graph = None
holes = None

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


Multiple polygon vertices might have identical coordinates. 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!


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 star would visit every node in the graph at least once (-> disadvantage!).

prepared = False
store(boundary_coordinates: Union[numpy.ndarray, List[T]], list_of_hole_coordinates: Union[numpy.ndarray, List[T]], validate: bool = False)[source]

saves the passed input polygons in the environment


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
  • 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

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)

  • 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
translate(new_origin: extremitypathfinder.helper_classes.Vertex)[source]

shifts the coordinate system to a new origin

computing the angle representations, shifted coordinates and distances for all vertices respective to the query point (lazy!)

Parameters:new_origin – the origin of the coordinate system to be shifted to
within_map(coords: Tuple[Union[float, int], Union[float, int]])[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