ladybug_geometry.network module

A 2D Directed Graph Network data structure used for splitting polygons.

A directed graph (or digraph) is a graph made up of a set of vertices (aka. nodes) connected by directed edges, often into a network where each node can have multiple connections.

This class is used in all operations where a polygon or face is split using line segments or polylines.

The overall strategies used in this module are inspired by operations performed by NetworkX but were constructed from scratch without working from any particular module or class in the package More information on NetworkX can be found here: https://github.com/networkx/networkx

class ladybug_geometry.network.DirectedGraphNetwork(tolerance)

Bases: object

A 2D Directed Graph Network data structure used for splitting polygons.

A directed graph (or digraph) is a graph made up of a set of vertices (aka. nodes) connected by directed edges, often into a network where each node can have multiple connections. This class contains for finding the shortest pathways through the graph. 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 – The tolerance used to determine point equivalence throughout the graph. 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.

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 whether the Node is exterior.

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

all_min_cycles()

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

The combination of all min cycles should account for the full area of the input shape if the DirectedGraphNetwork was made using any of the class methods that work from polygons. If the DirectedGraphNetwork was made using the from_shape_to_split method, the resulting cycles here represent the input shape split with the split_segments.

exterior_cycle(cycle_root)

Compute 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.

Exterior cycles refer to the cycles of both the boundary and the holes of the DirectedGraphNetwork was created using the from_shape_to_split class method.

classmethod from_point_array(point_array, tolerance, loop=True)

Create a DirectedGraphNetwork for a 1-dimensional array of points.

Parameters

• point_array – Array of Point2D objects.

• tolerance – The tolerance used to determine point equivalence throughout the graph. This is used for hashing points within the network.

• loop – Optional boolean, which will ensure that the input point_array is connected into a loop. (Default: True).

classmethod from_polygon(polygon, tolerance)

Create a DirectedGraphNetwork from a polygon.

Parameters

• polygon – A Polygon2D object.

• tolerance – The tolerance used to determine point equivalence throughout the graph. This is used for hashing points within the network.

Returns

A PolygonDirectedGraph object that represents the polygon. The edges are uni-directional and counterclockwise. The nodes have the exterior property set to True.

classmethod from_shape_to_split(boundary, holes, split_segments, tolerance)

Get a DirectedGraphNetwork for a shape to be split with segments.

The shape is composed of a boundary with optional holes and the split_segments are an array of any line segments to be used to split the shape.

Parameters

• boundary – A Polygon2D for the boundary around the shape.

• holes – An optional list of Polygon2D for the holes within the shape. If None, it will be assumed that no holes exist in the shape.

• split_segments – An array of LineSegment2D to be used to split the shape.

• tolerance – The tolerance used to determine point equivalence throughout the graph. This is used for hashing points within the network.

Returns

A PolygonDirectedGraph object that represents the network formed by the boundary, holes, and split segments. Portions of the split_segments that are outside of the boundary are excluded from the graph. All interior connections between the split_segments in the graph are bi-directional. The exterior 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.

classmethod from_shape_with_holes(boundary, holes, tolerance)

Create a DirectedGraphNetwork for a shape with holes.

Parameters

• boundary – A Polygon2D for the boundary around the shape.

• holes – An optional list of Polygon2D for the holes within the shape. If None, it will be assumed that no holes exist in the shape.

• tolerance – The tolerance used to determine point equivalence throughout the graph. This is used for hashing points within the network.

Returns

A PolygonDirectedGraph object that represents the boundary with holes. 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 edge. The nodes have the exterior property set to True.

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.

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 a polygon is in the directed graph.

Parameters

polygons – A Polygon2D object.

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.

hole_root_keys

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

outer_root_key

property outer_root_node

Get the node of the outer boundary root.

class ladybug_geometry.network.Node(pt, key, order, adj_lst, exterior=None)

Bases: object

A Node within in DirectedGraphNetwork, optionally connected to other Nodes.

Parameters

• pt – A Point2D object for the node

• key – String representation of the Point2D object which accounts for tolerance.

• order – Integer for the order of the Node (based on directed graph propagation).

• adj_lst – List of Node objects that are adjacent to this node.

• exterior – Optional boolean to indicate if the Node is on the exterior of the graph. If None, this value can be computed later based on the position within the overall graph.

Properties:

• pt

• key

• adj_lst

• exterior

• adj_count

property adj_count

Number of adjacent nodes

adj_lst

exterior

key

pt

ladybug_geometry.network.coordinates_hash(point, tolerance)

Convert XY coordinates of a Point2D into a string useful for hashing.

Points that are co-located within the tolerance will receive the same string value from this function, which helps convert line segments that contain duplicated vertex references them into a singular network object where co-located vertices are referenced only once.

Parameters

• point – A Point2D object.

• tolerance – floating point precision tolerance.

Returns

A string of rounded coordinates.