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 StrandHolm, Magnus StrandHolm Vinther, and Peyman Afshani. “Pathfinding in Twodimensional Worlds”

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

all_edges
¶

all_extremities
¶

all_vertices
¶

boundary_polygon
= None¶

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 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
.
Returns: a tuple of shortest path and its length. ([], None) if there is no possible path.

graph
= None¶

holes
= None¶

polygons
¶

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
Note
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!
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 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
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 gridlike into a polygon environment and save it
Prerequisites: grid world must not have single nonobstacle 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¶

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
