Implementation of a Directed Graph.

Bases: `object`

A directed graph for point and edge adjacency relationships.

This class assumes that exterior edges are naked (unidirectional), oriented counter-clockwise, and interior edges are bidirectional.

Parameters

tol – floating point precision used for hashing points.

Properties:
• outer_root_key: Root key for outside exterior boundary (i.e not holes).

• hole_root_keys: List of root keys for inside exterior boundary (holes).

• num_nodes: Number of nodes in graph.

• nodes: An iterable of nodes in graph.

• ordered_nodes: An iterable of nodes in graph in order they were added.

• exterior_cycles: A list of unidirectional edge arrays.

This method will ensure no repetitions will occur in adj_lst.

Parameters

Consumes a polygon point, and computes its key value, and adds it in the graph if it doesn’t exist. If it does exist it appends adj_lst to existing pt.

Parameters
• val – A Point2D object

• adj_lst – A list of Point2D objects

Returns

The hashed key from the existing or new node.

Gets an adjacency matrix of the directed graph where:

• 1 = adjacency from row node to col node.

Returns

N x N square matrix where N is number of nodes.

Returns a dictionary where label key corresponds to index in adj_matrix and value is node key

static exterior_cycle(cycle_root)[source]

Computes exterior boundary from a given node.

This method assumes that exterior edges are naked (unidirectional) and interior edges are bidirectional.

Parameters

cycle_root – Starting _Node in exterior cycle.

Returns

List of nodes on exterior if a cycle exists, else None.

classmethod from_point_array(point_array, tol, loop=True)[source]

Generate a directed graph from a 1-dimensional array of points.

Parameters
• point_array – Array of Point2D objects.

• loop – Optional parameter to connect 1d array

• tol – Tolerance for point equivalence.

classmethod from_polygon(polygon, tol)[source]

Generate a directed graph from a polygon.

Parameters

polygon – A Polygon2D object.

insert_node(node, new_val, next_node, exterior=None)[source]

Insert node in the middle of an edge defined by node and next_node.

Parameters
• node – _Node to left.

• new_val – Value for middle node.

• next_node – _Node to right.

• exterior – Optional boolean for exterior attribute.

Returns

key of new_val node.

intersect_graph_with_segment(segment)[source]

Update graph with intersection of partial segment that crosses through polygon.

Parameters
• segment – LineSegment2D to intersect. Does not need to be contained within

• polygon.

static is_edge_bidirect(node1, node2)[source]

Are two nodes bidirectional.

Parameters
• node1 – _Node object

• node2 – _Node object

Returns

True if node1 and node2 are in each other’s adjacency list, else False.

static min_ccw_cycle(curr_node, next_node, recurse_limit=3000, print_recurse=False)[source]

Recursively identify most counter-clockwise adjacent node and get closed loop.

Parameters
• curr_node – The first node, for first edge.

• next_node – The node next to ref_node that constitutes a polygon edge.

• recurse_limit – optional parameter to limit the number of while loop cycles. Default: 3000.

• print_recurse – optional boolean to print cycle loop cycles, for debugging. Default: False.

Returns

A list of nodes that form a polygon if the cycle exists, else None.

static next_exterior_node(node)[source]

Retrieves the first exterior node adjacent to consumed node. They define an exterior or naked edge.

Parameters

node – _Node

Returns

Next node that defines exterior edge, or None if all adjacencies are bidirectional.

static next_unidirect_node(node)[source]

Retrieves the first unidirectional point adjacent to consumed point. They define an exterior or naked edge.

Parameters

node – _Node

Returns

Next node that defines unidirectional edge, or None if all adjacencies are bidirectional.

node(key)[source]

Retrieves the node based on passed value.

Parameters

val – The key for a node in the directed graph.

Returns

The node for the passed key.

node_exists(key)[source]

True if node in directed graph else False

polygon_exists(polygon)[source]

Check if polygon is in directed graph.

Parameters
• polygons – A Polygon2D object.

• dg – A PolygonDirectedGraph.

Returns

True if exists, else False.

pt_exists(pt)[source]

True if a point (as Point2D) in directed graph exists as node else False.

Parameters
• node – _Node to remove adjacencies to.

property exterior_cycles

Computes all exterior boundaries.

Returns

List of boundaries as list of nodes. The first polygon will be the outer exterior edge (in counter-clockwise order), and subsequent edges will be the edges of the holes in the graph (in clockwise order).

property nodes

Get an iterable of pt nodes

property num_nodes
property ordered_nodes

Get an iterable of pt nodes in order of addition