ladybug_geometry_polyskel.polygraph module

Implementation of a Directed Graph data structure.

class ladybug_geometry_polyskel.polygraph.PolygonDirectedGraph(tol)

Bases: object

A directed graph data structure for point relationships.

The PolygonDirectedGraph effectively represents the network of a straight skeleton and assists with finding the shortest pathways through it. It also helps differentiate interior from exterior parts of the graph. Typically, interior pathways are bi-directional in the graph while exterior pathways are uni-directional.

Parameters:

tolerance – Tolerance for point equivalence. (Default: 1e-5). This is used for hashing points within the network.

Properties:

• node_count: Integer for the 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.

• connection_segments: List of LineSegment2D for the node connections

• outer_root_node: A node for the outer root key

• hole_root_nodes: A list of nodes for the hole root keys

• is_intersect_topology: A boolean for whether the graph self-intersects

add_adj(node, adj_val_lst)

Adds nodes to node.adj_lst.

This method will ensure no repetitions will occur in adj_lst.

Parameters:

• node – _Node to add adjacencies to.

• adj_val_lst – List of Point2D objects to add as adjacent nodes.

add_node(val, adj_lst, exterior=None)

Add a node into the PolygonDirectedGraph.

This method consumes a Point2D, 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 adjacent to the node.

• exterior – Optional boolean for exterior attribute.

Returns:

The hashed key from the existing or new node.

adj_matrix()

Gets an adjacency matrix of the directed graph where:

• 1 = adjacency from row node to col node.

• 0 = no adjacency.

Returns:

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

adj_matrix_labels()

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

exterior_cycle(cycle_root)

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.

exterior_cycles()

Get a list of lists where each sub-list is an exterior cycle of Nodes.

classmethod from_point_array(point_array, tol, loop=True)

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)

Generate a directed graph from a polygon.

Parameters:

polygon – A Polygon2D object.

insert_node(base_node, new_val, next_node, exterior=None)

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

Parameters:

• base_node – _Node object to the left.

• new_val – A Point2D object for the new node in the middle.

• next_node – _Node object to the right.

• exterior – Optional boolean for exterior attribute.

Returns:

key of new_val node.

intersect_graph_with_segment(segment)

Update graph with intersection of partial segment crossing through polygon.

Parameters:

segment – LineSegment2D to intersect with the graph. The LineSegment2D does not need to be contained within polygon and will be intersected infinitely.

static is_edge_bidirect(node1, node2)

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.

min_cycle(base_node, goal_node, ccw_only=False)

Identify the shortest interior cycle between two exterior nodes.

Parameters:

• base_node – The first exterior node of the edge.

• goal_node – The end exterior node of the cycle that, together with the base_node, constitutes an exterior edge.

• ccw_only – A boolean to note whether the search should be limited to the counter-clockwise direction only. (Default: False).

Returns:

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

static next_exterior_node(node)

Get the next exterior node adjacent to consumed node.

If there are adjacent nodes that are labeled as exterior, with True or False defining the _Node.exterior property, the first of such nodes in the adjacency list will be returned as the next one. Otherwise, the bi-directionality will be used to determine whether the next node is exterior.

Parameters:

node – A _Node object for which the next node will be returned.

Returns:

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

static next_exterior_node_no_backtrack(node, previous_node, explored_nodes)

Get the next exterior node adjacent to the input node.

This method is similar to the next_exterior_node method but it includes extra checks to handle intersections with 3 or more segments in the graph exterior cycles. In these cases a set of previously explored_nodes is used to ensure that no back-tracking happens over the search of the network, which can lead to infinite looping through the graph. Furthermore, the previous_node is used to select the pathway with the smallest angle difference with the previous direction. This leads the result towards minimal polygons with fewer self-intersecting loops.

Parameters:

• node – A _Node object for which the next node will be returned.

• previous_node – A _Node object for the node that came before the current one in the loop. This will be used in the event that multiple exterior nodes are found connecting to the input node. In this case, the exterior node with the smallest angle difference with the previous direction will be returned. This leads the result towards minimal polygons and away from self-intersecting exterior loops like a bowtie.

Returns:

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

node(key)

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)

Check if a node is in the graph. True if node in directed graph else False.

polygon_exists(polygon)

Check if polygon is in the directed graph.

Parameters:

• polygons – A Polygon2D object.

• dg – A PolygonDirectedGraph.

Returns:

True if exists, else False.

pt_exists(pt)

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

remove_adj(node, adj_key_lst)

Removes nodes in node.adj_lst.

Parameters:

• node – _Node to remove adjacencies to.

• adj_val_lst – List of adjacency keys to remove as adjacent nodes.

property connection_segments

Get a list of LineSegment2D for the node connections in the graph.

property hole_root_nodes

Get a list of nodes for the roots of the holes.

property node_count

property nodes

Get an iterable of pt nodes

property ordered_nodes

Get an iterable of pt nodes in order of addition

property outer_root_node

Get the node of the outer boundary root.

ladybug_geometry_polyskel.polygraph.skeleton_as_cycle_polygons(boundary, holes=None, tolerance=1e-05)

Compute the straight skeleton of a shape as a list of cycle polygons.

Parameters:

• boundary – A ladybug-geometry Polygon2D for the boundary around the shape for which the straight skeleton will be computed.

• holes – An optional list of ladybug-geometry Polygon2D for the holes within the shape for which a straight skeleton will be computed. If None, it will be assumed that no holes exist in the shape. (Default: None).

• tolerance – Tolerance for point equivalence. (Default: 1e-5).

Returns:

A list of Polygon2D that represent the straight skeleton of the input shape. There will be one Polygon2D for each edge of the shape (including both the boundary and the holes). Together, the Polygon2Ds will fill the entire input shape. There may be some overlap in between the output polygons if the straight skeleton did not have the correct topology.

ladybug_geometry_polyskel.polygraph.skeleton_as_directed_graph(boundary, holes=None, tolerance=1e-05)

Compute the straight skeleton of a shape as a PolygonDirectedGraph.

Parameters:

• boundary – A ladybug-geometry Polygon2D for the boundary around the shape for which the straight skeleton will be computed.

• holes – An optional list of ladybug-geometry Polygon2D for the holes within the shape for which a straight skeleton will be computed. If None, it will be assumed that no holes exist in the shape. (Default: None).

• tolerance – Tolerance for point equivalence. (Default: 1e-5).

Returns:

A PolygonDirectedGraph object that represents the network and boundary of the straight skeleton. All interior connections in the graph are assumed to be bi-directional. The edges (including the boundary and holes) are uni-directional with the outer boundary being counterclockwise and the holes being clockwise. In other words, the fill of the shape is always to the left of each exterior edge. The nodes at the boundary and the holes have the exterior property set to True.