uavfpy.planner.coverage.bdc
Module Contents
Functions
|
Convert angle from radians to degrees |
|
Convert angle from degrees to radians |
|
|
|
|
|
|
|
Determine orientation of a set of points |
|
Perform a boustrophedon line sweep over a world graph G. |
|
Get centroid of a cell cell made up of nodes in H |
|
Build the reebgraph on H using the cell information contained in 'cells' |
|
Create a "skelgraph" from a bdc world H and its reeb graph, R. |
|
Get the closest point of a skel graph stored in the rnode of R to the midpoint midp. |
|
this is a helper function for casting the results of polyskel to |
|
This is a helper function for casting the list returned by polyskel to |
|
Get an array of points from H which stores points in posattr from indices in nlist |
|
Get the midpoint of the line which joins two cells, e1 and e2. |
|
dot a vector x with itself to produce a scalar |
|
Alters T in place, replacing its non-unique nodes by iterating on new_node. |
|
Make the "straight skeleton graph" over the world H with |
|
|
|
compute the vector cross product of edges u,`v` and v,`w` on H. |
|
[summary] |
|
Alters H in place to produce split/merge points |
|
Check for intersects a vertical line passing through v on the graph H. |
|
Get line intersect on the line formed by [p1, p2] for the point at pv |
|
Check whether an edge [edge=(e1, e2)] on H intersects with a straight vertical line |
|
|
|
Check the neighbors of v to determine which is the lower neighbor |
|
Compute cross product on ordered nodes vA, v, vB of graph H. |
|
Rotate a graph G. This makes a copy of G and returns it, leaving G untouched. |
|
Create a rotation matrix |
- class uavfpy.planner.coverage.bdc.Event
Bases:
enum.EnumGeneric enumeration.
Derive from this class to define new enumerations.
- CLOSE = 1
- OPEN = 2
- SPLIT = 3
- MERGE = 4
- INFLECTION = 5
- INTERSECT = 6
- uavfpy.planner.coverage.bdc.rad2degree(rad)
Convert angle from radians to degrees
- Parameters
- radint or float
Angle in radians
- Returns
- float
angle in degrees
- uavfpy.planner.coverage.bdc.degree2rad(deg)
Convert angle from degrees to radians
- Parameters
- degint or float
angle in degrees
- Returns
- float
angle in radians
- uavfpy.planner.coverage.bdc.discretize_entire(J: networkx.DiGraph, R: networkx.Graph, gridsz: float)
- uavfpy.planner.coverage.bdc.add_discretized_cells(J: networkx.DiGraph, R: networkx.Graph, theta, gridsz) None
- uavfpy.planner.coverage.bdc.discretize_cell(J: networkx.DiGraph, c, theta, gridsz, diags=True)
- uavfpy.planner.coverage.bdc.iscw(points: numpy.ndarray) bool
Determine orientation of a set of points
- Parameters
- pointsnp.ndarray
An ordered set of points
- Returns
- bool
True if clockwise, False if not clockwise
- uavfpy.planner.coverage.bdc.line_sweep(G: networkx.DiGraph, theta: float = 0, posattr: str = 'points') tuple
Perform a boustrophedon line sweep over a world graph G.
- Parameters
- Gnx.DiGraph
World graph. Contains an outer boundary, which is made up of a clockwise ordering of edges with weight=1, and optionally contains holes, which are counterclockwise orderings of edges with weight=2. Worlds must be non-degenerate planar graphs!
- thetafloat, optional
Angle of the line sweep from x-axis, by default 0
- posattrstr, optional
attribute of points in G, by default ‘points’
- Returns
- tuple
H, which is a graph of the new bdc-composed world rotated to theta J, which is the graph of the new bdc-compoased world rotated back to its original orientation R, which is the reeb graph containing connectvitity information between each cell S, which is the skel graph containing connected straight skeletons of each cell in R.
- uavfpy.planner.coverage.bdc.rg_centroid(H: networkx.DiGraph, cell: set) numpy.ndarray
Get centroid of a cell cell made up of nodes in H
- Parameters
- Hnx.DiGraph
The world graph
- cellset
An ordered or unordered list of nodes in H
- Returns
- np.ndarray
the centroid as an xy point.
- uavfpy.planner.coverage.bdc.build_reebgraph(H: networkx.DiGraph, cells: list) networkx.Graph
Build the reebgraph on H using the cell information contained in ‘cells’
- Parameters
- Hnx.DiGraph
The bdc composed world
- cellslist
each entry in cells is a list of nodes in H which form a closed cell in the bdc composition
- Returns
- nx.Graph
Graph, R which represents connectivity of each cell in H
- uavfpy.planner.coverage.bdc.create_skelgraph(R: networkx.Graph, H: networkx.DiGraph) networkx.Graph
Create a “skelgraph” from a bdc world H and its reeb graph, R. A skelgraph is a graph of the straight skeletons of each cell of a world H, joined by the midpoints of each cell wall on H.
Traversing the skelgraph of H means visiting each cell the boustrophedon decomposition of H.
- Parameters
- Rnx.Graph
The reeb graph of the world
- Hnx.DiGraph
The BDC of the world
- Returns
- nx.Graph
An undirected graph joining the straight skeleton of each cell.
- uavfpy.planner.coverage.bdc.get_closest_on_skel(R: networkx.graph, rnode: int, midp: numpy.array) numpy.array
Get the closest point of a skel graph stored in the rnode of R to the midpoint midp.
- Parameters
- Rnx.graph
Reeb graph containing straight skeleton in key ‘skel_graph’
- rnodeint
node on that reeb graph
- midpnp.array
the point to test
- Returns
- int
a node on skel_graph which is closest to midp
- uavfpy.planner.coverage.bdc.fix_polyskel(skel: list)
this is a helper function for casting the results of polyskel to numpy arrays, rather than Euler3 points
- Parameters
- skellist
results of polyskel function call
- Returns
- list
each element of this list contains origin, height, and leafs. see polyskel documentation for more
- uavfpy.planner.coverage.bdc.traverse_polyskel(R: networkx.Graph, rn: int, skel: list) networkx.Graph
This is a helper function for casting the list returned by polyskel to a networkx Graph.
This function also adds the list from skel to a reebgraph stored in R at node rn.
- Parameters
- Rnx.Graph
Reeb Graph
- rnint
node on the reeb graph
- skellist
list returned by polyskel
- Returns
- nx.Graph
the straight skel graph
- uavfpy.planner.coverage.bdc.get_points_array(H: networkx.Graph, nlist: list = None, posattr: str = 'points') numpy.ndarray
Get an array of points from H which stores points in posattr from indices in nlist
Returns all points in H by default.
- Parameters
- Hnx.Graph
world graph
- nlistlist, optional
subset of nodes on H to get points from, by default None
- posattrstr, optional
attribute that the points are stored under, by default ‘points’
- Returns
- np.ndarray
Mx2 array for M points
Get the midpoint of the line which joins two cells, e1 and e2.
- Parameters
- Hnx.DiGraph
the world graph
- Rnx.Graph
the reeb graph of the world H
- e1int
first shared edge. Node of R
- e2int
second shared edge. Node of R
- Returns
- np.ndarray
the midpoint
- uavfpy.planner.coverage.bdc.dotself(x: numpy.ndarray) float
dot a vector x with itself to produce a scalar
- Parameters
- xnp.ndarray
the vector
- Returns
- float
scalar value |x|^2
- uavfpy.planner.coverage.bdc.remap_nodes_unique(new_node: int, T: networkx.Graph) int
Alters T in place, replacing its non-unique nodes by iterating on new_node. we can run this function on several graphs, thus guaranteeing that their nodes do not collide.
- Parameters
- new_nodeint
starting value for new nodes
- Tnx.Graph
A graph with integer nodes
- Returns
- int
ending value for new nodes
- uavfpy.planner.coverage.bdc.make_skelgraph(H: networkx.DiGraph, R: networkx.Graph)
Make the “straight skeleton graph” over the world H with its reeb-graph R.
- Parameters
- Hnx.DiGraph
The world. Must already be BDC decomposed.
- Rnx.Graph
Reeb graph of the world.
- Returns
- nx.Graph
the “skeleton” graph. This undirected graph is made up of the straight skeleton of each cell, connected by the midpoints of the dividing lines between cells.
- uavfpy.planner.coverage.bdc.cul_de_sac_check(S: networkx.Graph, n)
- uavfpy.planner.coverage.bdc.rcross(H: networkx.DiGraph, u: int, v: int, w: int) float
compute the vector cross product of edges u,`v` and v,`w` on H. This one is more expensive than qcross but returns a numerical value.
- Parameters
- Hnx.DiGraph
Graph
- uint
idx of node
- vint
idx of node
- wint
idx of node
- Returns
- float
cross product
- uavfpy.planner.coverage.bdc.append_cell(H: networkx.DiGraph, v: int, cells: dict) list
[summary]
- Parameters
- Hnx.DiGraph
graph on which to append cells
- vint
vertex from which to start
- cellslist
list of cells.
- Returns
- list
new list of cells
- uavfpy.planner.coverage.bdc.splitmerge_points(H: networkx.DiGraph, v: int) None
Alters H in place to produce split/merge points from an event on node v
- Parameters
- Hnx.DiGraph
Shape graph
- vint
index of the event vertex
- uavfpy.planner.coverage.bdc.get_intersects(H: networkx.DiGraph, v: int) tuple
Check for intersects a vertical line passing through v on the graph H. Think of it like this: We basically draw a line upwards from v until we reach a line on H; then we register a collision, which contains the origin vertex of the collision in ‘vx’, the point of the collision in ‘pt’, the edge with which the line collided in ‘edge’, and the weight of that edge in ‘weight’.
This function returns a maximum of two collisions, one above and one below, which correspond to the closest edge with which the line starting at v collided. If there is no such edge, it returns None, otherwise returns a dict with information about the collision specified above.
- Parameters
- Hnx.DiGraph
graph
- vint
event idx
- Returns
- tuple
collisions above or/and below v on edges of H
- uavfpy.planner.coverage.bdc.intersect_vertical_line(p1: numpy.ndarray, p2: numpy.ndarray, pv: numpy.ndarray) numpy.ndarray
Get line intersect on the line formed by [p1, p2] for the point at pv
- Parameters
- p1np.ndarray
end point of line
- p2np.ndarray
end point of line
- pvnp.ndarray
point of intersect
- Returns
- np.ndarray
line from pv to the point of intersection
- uavfpy.planner.coverage.bdc.check_edge(H: networkx.DiGraph, v: int, edge: tuple) bool
Check whether an edge [edge=(e1, e2)] on H intersects with a straight vertical line at v
- Parameters
- Hnx.DiGraph
graph
- vint
vertex idx
- edgetuple of (int, int)
edge idxs
- Returns
- bool
Whether the x coordinates of the point v are beteen the edge x-coords
- uavfpy.planner.coverage.bdc.check_lu(H: networkx.DiGraph, v: int) int
- uavfpy.planner.coverage.bdc.lower_upper(H: networkx.DiGraph, v: int)
Check the neighbors of v to determine which is the lower neighbor and which is the upper neighbor. If the predecessor is the upper neighbor, also returns True
- Parameters
- Hnx.DiGraph
must contain ‘weight’ as a key.
- vint
The vertex to check
- Returns
- tuple of (int, int, bool)
lower vertex, upper vertex, above
- uavfpy.planner.coverage.bdc.qcross(H, vA, v, vB)
Compute cross product on ordered nodes vA, v, vB of graph H.
- Parameters
- Hnx.DiGraph
The graph for which vA, v, vB are nodes.
- vAint
Node of H.
- vint
Node of H
- vBint
Node of H
- uavfpy.planner.coverage.bdc.rotate_graph(G: networkx.DiGraph, theta: float, posattr: str = 'points') networkx.DiGraph
Rotate a graph G. This makes a copy of G and returns it, leaving G untouched.
- Parameters
- Gnx.DiGraph
input Graph
- thetafloat
rotation angle, radians
- posattrstr, optional
which key the points are stored under, by default ‘points’
- Returns
- nx.DiGraph
the new rotated graph
- uavfpy.planner.coverage.bdc.make_rot_matrix(theta: float) numpy.ndarray
Create a rotation matrix
- Parameters
- thetafloat
Angle
- Returns
- np.ndarray
2x2 Rotation Matrix created from Angle.