-
Notifications
You must be signed in to change notification settings - Fork 0
tree.py
This module contains functions to parse the original data, apply a safety margin onto the restricted region (R), find valid connections between waypoints that don't pass through R, and generate a dictionary based tree that can be used by the A* algorithm to find the most efficient route around R.
Two waypoints/nodes are classified as either start or target. The start node will be the drone's current position at the time the message regarding R is received via QR code. This message will also contain something along the lines of "rejoin the route at waypoint X," which is the target.
Currently, the data is in a .csv for testing purposes, however this will likely need to be updated to take the data as given by the QR code and parsing it to create the valid dictionary that is used everywhere else, with the general structure of {'waypoint_name': (x, y, type_of_node)}. An example for the format of the .csv used currently is available here.
The modules csv and itertools are built-ins.
sympy is required so that Polygon and Segment objects can be created and used to check for valid connections between nodes that don't pass through R.
Parses the given .csv file so the data is more easily accessible later on. Skips the headers on the first line and reads through line by line, adding to nodes: dict as it goes.
filename <str>: Input .csv file with the header "waypoint_name, x_position, y_position, type". See an example.
A dictionary that stores each 'waypoint_name' as the key and a tuple (x_pos: float, y_pos: float, classification: string) as the value.
Applies a safety margin to nodes so connections can be made without being on the border of the restricted region, while preserving the name associated with each waypoint so that the valid connections can be organised by name later on.
Currently, this function does not check that the region scaled by margin is not too big such that start or target end up inside of this new region. This will need to be addressed as this may cause unintended behaviour when it comes to finding the optimal route around R.
nodes <dict>: A dictionary of nodes that has the form {'waypoint_name': (x, y, classification)}. This is currently generated by the parse_data() function.
margin <float>: Factor to scale the restricted region by to provide a safety margin so the drone doesn't accidentally enter the restricted region. The default value for this is 1.3 right now but this will likely have to be updated according to real-world tests.
A dictionary containing each waypoint name and its corresponding safe waypoint. Also returns the restricted_region polygon for later use since the original restricted_region is the one that needs to be checked for intersection between the lines drawn between any two nodes (with the safety margin applied). Returns the safe_region as well in case valid paths need to avoid being too close to the restricted_region as per the safety margin.
Finds all connections between any two nodes in the given data that don't intersect R. Also has the option to set intersect_safe to True, which will ensure that the paths drawn between nodes always respect the safety_margin, so no path goes too close to R.
safe_waypoints <dict>: A dictionary of waypoints and their names that has the safety margin applied. This comes from create_safe_waypoints().
restricted_region <sympy.Polygon>: The region bounded by the 'obstacle' waypoints that must be avoided. This was also created in create_safe_waypoints() and so is reused here.
safe_region <sympy.Polygon>: The safe region created by scaling the restricted region. The same one that is returned by create_safe_waypoints().
intersect_safe <bool>: Whether to maintain safety margin on paths between nodes. If True, paths are allowed to be closer to the restricted region than the safe waypoints are. If False, The valid paths must also respect the safety margin.
A list containing every two points that can be connected without intersecting the restricted region. Each pair of points is a tuple containing the names of the parent and child waypoint that can be connected. Also returns a version with just the coordinates for easier use later on.
Generate the final tree to be used by the pathfinding algorithm.
connections_coords <list[tuples]>: A list of tuples with node coordinates.
connections_names <list[tuples]>: Currently a list of tuples with node names (parent, child). Used for debugging/visualization purposes.
A dictionary containing each node and all nodes that can be reached through that node. Returns two dicts, one using node names for readability/debugging, and one using coordinates for later use. Both dictionaries are undirected.
Important: The coordinates version, tree_coords is the final version of the tree/graph generated by this script. Any other calculations of distance, cost, etc. should be done in the pathfinding algorithm itself.
None for now.