Create a new instance of the PolygonEnvironment class to allow fast consequent timezone queries:
from extremitypathfinder import PolygonEnvironment environment = PolygonEnvironment()
Required data format: Ensure that all the following conditions on the polygons are fulfilled:
- numpy or python array of coordinate tuples:
- the first point is NOT repeated at the end
- must at least contain 3 vertices
- no consequent vertices with identical coordinates in the polygons (same coordinates in general are allowed)
- a polygon must NOT have self intersections
- different polygons may intersect each other
- edge numbering has to follow this convention (for easier computations):
- outer boundary polygon: counter clockwise
- holes: clockwise
# counter clockwise vertex numbering! boundary_coordinates = [(0.0, 0.0), (10.0, 0.0), (9.0, 5.0), (10.0, 10.0), (0.0, 10.0)] # clockwise numbering! list_of_holes = [ [ (3.0, 7.0), (5.0, 9.0), (4.5, 7.0), (5.0, 4.0), ], ] environment.store(boundary_coordinates, list_of_holes, validate=False)
validate=True in order to check the condition on the data.
TypeError if the input has the wrong type and
ValueError if the input is invalid.
If two Polygons have vertices with identical coordinates (this is allowed), paths through these vertices are theoretically possible! When the paths should be blocked, use a single polygon with multiple identical vertices instead (also allowed).
start_coordinates = (4.5, 1.0) goal_coordinates = (4.0, 8.5) path, length = environment.find_shortest_path(start_coordinates, goal_coordinates)
If any start and goal point should be accepted without checking if they lie within the map, set
This is required if points lie really close to polygon edges and
“point in polygon” algorithms might return an unexpected result due to rounding errors.
path, length = environment.find_shortest_path( start_coordinates, goal_coordinates, verify=False )
Converting and storing a grid world¶
size_x, size_y = 19, 10 obstacle_iter = [ # (x,y), # obstacles changing boundary (0, 1), (1, 1), (2, 1), (3, 1), (17, 9), (17, 8), (17, 7), (17, 5), (17, 4), (17, 3), (17, 2), (17, 1), (17, 0), # hole 1 (5, 5), (5, 6), (6, 6), (6, 7), (7, 7), # hole 2 (7, 5), ] environment.store_grid_world( size_x, size_y, obstacle_iter, simplify=False, validate=False )
Note: As mentioned in
[1, Ch. III 6.3]
in “chessboard-like grid worlds” (many small obstacles have a lot of extremities!)
it can be better to use A* right away (implemented in
Cache and import the environment¶
environment.export_pickle(path="./pickle_file.pickle") from extremitypathfinder.extremitypathfinder import load_pickle environment = load_pickle(path="./pickle_file.pickle")
PlottingEnvironment automatically generates plots for every step in the path finding process:
from extremitypathfinder.plotting import PlottingEnvironment environment = PlottingEnvironment(plotting_dir="path/to/plots") environment.store(boundary_coordinates, list_of_holes, validate=True) environment.prepare() path, distance = environment.find_shortest_path(start, end)
Other functions in
plotting.py can be utilised to plot specific parts of an environment (extremities, edges, …)
Calling extremitypathfinder from the command line¶
A command line script is being installed as part of this package.
Command Line Syntax:
extremitypathfinder <path2json_file> -s <start> -g <goal>
<goal> arguments must be passed as two separate float values.
extremitypathfinder ./example.json -s 2.5 3.2 -g 7.9 6.8
[(2.5, 3.2), (5.0, 4.0), (7.9, 6.8)] 6.656009823830612
Please note that this might be significantly slower than using the package directly from within python.