geom2d.planargraph

Simple planar graph data structure.

class geom2d.planargraph.Graph(edges: Iterable[TLine] | None = None)

Simple connected undirected 2D planar graph.

add_edge(edge: Sequence[Sequence[float]]) → None

Add an edge to this graph.

Parameters:

edge – A line segment that defines a graph edge. An edge being a 2-tuple of endpoints of the form: ((x1, y1), (x2, y2)).

add_poly(vertices: Sequence[TPoint], close_poly: bool = True) → None

Add polygon edges to this graph.

Parameters:

  • vertices – A list of polyline/polygon vertices as 2-tuples (x, y).

  • close_poly – If True a closing segment will be automatically added if absent. Default is True.

boundary_polygon() → list[P]

A polygon defining the outer edges of this segment graph.

bounding_box() → Box

Get the bounding rectangle for this graph.

Returns:

A tuple containing two points ((x0, y0), (x1, y1)) specifying bottom left and top right corners.

cull_open_edges() → None

Remove edges that have one or two disconnected endpoints.

edges: set[Line]

Set of graph edges

get_face_polygons() → list[list[P]]

Graph face polygons.

Returns:

A list of face polygons.

nodemap: dict[P, GraphNode]

Map of vertex points to graph nodes.

nodes() → Iterable[GraphNode]

Graph nodes.

order() → int

Number of graph nodes (vertices.).

peel_boundary_polygon(boundary_polygon: Sequence[P]) → list

Similar to convex hull peeling but with non-convex boundary polygons.

Parameters:

boundary_polygon – The initial graph polygon hull to peel.

Returns:

A list of peeled inner polygons. Possibly empty.

remove_edge(edge: Sequence[Sequence[float]]) → None

Remove and unlink the specified edge from the graph.

Parameters:

edge – A line segment that defines a graph edge connecting two nodes. An edge being a 2-tuple of endpoints of the form: ((x1, y1), (x2, y2)).

size() → int

Number of edges.

vertices() → Iterable[P]

Graph edge vertices (node points).

class geom2d.planargraph.GraphNode(vertex: P, edge_nodes: Iterable[GraphNode] | None = None)

Graph node.

A node has a vertex and a list of outgoing nodes that define the outgoing edges that connect to other nodes in the graph.

add_edge_node(edge_node: GraphNode) → None

Add an outgoing edge node.

Parameters:

edge_node – Endpoint of outgoing edge.

ccw_edge_node(ref_node: GraphNode, skip_spikes: bool = True) → GraphNode

The most CCW edge node.

Starting at the reference edge defined by ref_node->this_node.

Parameters:

  • ref_node – The reference edge node.

  • skip_spikes – Skip over edges that connect to nodes of order one.

Returns:

The counter-clockwise edge node closest to the reference node by angular distance. If all edges nodes are dead ends the reference node will be returned.

degree() → int

Number of incident graph edges.

I.e. number of edges that share this node’s vertex.

See:

http://mathworld.wolfram.com/VertexOrder.html

remove_edge_node(edge_node: GraphNode) → None

Remove an outgoing edge node.

sort_edges() → None

Sort outgoing edges in CCW order.

class geom2d.planargraph.GraphPathBuilder(graph: Graph, random_seed: float | None = None)

Create paths from connected graph edges.

This version is more deterministic.

Given a Graph, build a set of paths made of connected graph edges.

build_longest_paths(path_strategy: PathStrategy = PathStrategy.STRAIGHTEST) → list[list[P]]

Find the longest paths in this graph.

build_paths(start_edge: Line | None = None, random_start: bool = False, path_strategy: PathStrategy = PathStrategy.STRAIGHTEST, max_path_len: int | None = None, hull_poly: list[P] | None = None) → list[list[P]]

Build edge paths.

Given the starting edge, find the set of edge paths that completely fill the graph…

Parameters:

  • start_edge – The graph edge that starts the path.

  • random_start – Choose a random starting edge.

  • path_strategy –

    How paths will be constructed. Possible path strategies are:

    • PathStrategy.STRAIGHTEST

    • PathStrategy.SQUIGGLY

    • PathStrategy.RANDOM

    • PathStrategy.RANDOM2

  • max_path_len – Maximimum number of segments in path. Default is no limit.

  • hull_poly – Optional outer hull polygon that stops the path building once it intersects the hull.

Returns:

A list of paths.

class geom2d.planargraph.MarkedEdge(edge: Line)

A graph edge that is used to keep track of graph traversal direction.

visited_left(dest_vertex: P) → bool

True if this edge has been visited with a CCW winding.

The edge will be marked as visited.

Parameters:

dest_vertex – The destination vertex. Determines which side of the edge has been visited (i.e. direction).

Returns:

True if this edge has been visited during a counter-clockwise traversal. I.e. the left side given the direction. Otherwise False.

class geom2d.planargraph.MarkedEdgeMap(edges: Iterable[Line])

Map of edges to marked edges.

lookup(p1: P, p2: P) → MarkedEdge

Find a MarkedEdge by edge endpoints.

mark_edge(p1: P, p2: P) → None

Mark an edge segment as visited.

class geom2d.planargraph.PathStrategy(value)

Path building strategy.

geom2d.planargraph.find_free_edge_node(edgemap: MarkedEdgeMap, start_node: GraphNode) → GraphNode | None

Find a free outgoing edge that is unmarked for CCW edge traversal.

Parameters:

  • edgemap – Map of marked visited edges.

  • start_node – Graph node to start face polygon.