ladybug_geometry_polyskel.polygraph module

Implementation of a Directed Graph.

class ladybug_geometry_polyskel.polygraph.PolygonDirectedGraph(tol)[source]

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.


tol – floating point precision used for hashing points.

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

add_adj(node, adj_val_lst)[source]

Adds nodes to node.adj_lst.

This method will ensure no repetitions will occur in adj_lst.

  • 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)[source]

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.

  • val – A Point2D object

  • adj_lst – A list of Point2D objects


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.

  • 0 = no adjacency.


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.


cycle_root – Starting _Node in exterior cycle.


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.

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


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.

  • node – _Node to left.

  • new_val – Value for middle node.

  • next_node – _Node to right.

  • exterior – Optional boolean for exterior attribute.


key of new_val node.


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

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

  • polygon.

static is_edge_bidirect(node1, node2)[source]

Are two nodes bidirectional.

  • node1 – _Node object

  • node2 – _Node object


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.

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


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.


node – _Node


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.


node – _Node


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


Retrieves the node based on passed value.


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


The node for the passed key.


True if node in directed graph else False


Check if polygon is in directed graph.

  • polygons – A Polygon2D object.

  • dg – A PolygonDirectedGraph.


True if exists, else False.


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

remove_adj(node, adj_key_lst)[source]

Removes nodes in node.adj_lst.

  • node – _Node to remove adjacencies to.

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

property exterior_cycles

Computes all exterior boundaries.


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