conversions

pleat.conversions

Convert between NetworkX graphs and half-edge graph representations.

The main entry point is :func:EHEG_from_nx, which embeds an undirected planar :class:networkx.Graph (with vertex positions) into an :class:~pleat.half.EuclideanPositionHEG. Faces are recovered from the planar embedding implied by the cyclic angular order of edges around each vertex; the unbounded outer face is detected as the unique negatively- oriented face and removed.

EHEG_from_nx

EHEG_from_nx(
    nxg: Graph,
    positions: dict | None = None,
    return_v_lookup: bool = False,
) -> "EuclideanPositionHEG | tuple[EuclideanPositionHEG, dict]"

Convert a planar undirected :class:networkx.Graph to an :class:EuclideanPositionHEG.

Parameters:

Name	Type	Description	Default
nxg	Graph	An undirected, planar graph. Dangling vertices (degree 1) are pruned with a warning; node and edge attributes are copied onto the resulting :class:Vertex / :class:HalfEdge objects.	required
positions	dict | None	Optional {node: 2d position} mapping. Defaults to interpreting each node n as np.array(n).	None
return_v_lookup	bool	If True, also return {nx_node: Vertex}.	False

Returns:

Type	Description
'EuclideanPositionHEG | tuple[EuclideanPositionHEG, dict]'	The resulting graph, or (graph, v_lookup) if return_v_lookup is True.

Source code in pleat/conversions.py

def EHEG_from_nx(
    nxg: nx.Graph,
    positions: dict | None = None,
    return_v_lookup: bool = False,
) -> "EuclideanPositionHEG | tuple[EuclideanPositionHEG, dict]":
    """Convert a planar undirected :class:`networkx.Graph` to an :class:`EuclideanPositionHEG`.

    Args:
        nxg: An undirected, planar graph.  Dangling vertices (degree 1) are
            pruned with a warning; node and edge attributes are copied onto
            the resulting :class:`Vertex` / :class:`HalfEdge` objects.
        positions: Optional ``{node: 2d position}`` mapping.  Defaults to
            interpreting each node ``n`` as ``np.array(n)``.
        return_v_lookup: If True, also return ``{nx_node: Vertex}``.

    Returns:
        The resulting graph, or ``(graph, v_lookup)`` if *return_v_lookup* is True.
    """
    assert not nxg.is_directed()
    if positions is None:
        positions = {n: np.array(n) for n in nxg.nodes()}
    assert isinstance(positions, dict)
    n_dangling = _delete_dangling_edges_nx(nxg)
    if n_dangling > 0:
        logger.warning("Deleted %d dangling edges in conversion to EHG", n_dangling)
    result = EuclideanPositionHEG()
    v_lookup = dict()
    for n, attrs in nxg.nodes().data():
        v = Vertex()
        # assign node attributes
        for key, value in attrs.items():
            v[key] = value
        v["pos"] = positions[n]
        v_lookup[n] = v
    result.add_vertices(v_lookup.values())
    h_lookup = dict()
    # orig, dest
    for n in nxg.nodes():
        v = v_lookup[n]
        h_lookup[v] = dict()
        for m in nxg[n]:
            w = v_lookup[m]
            h = HalfEdge(orig=v, dest=w)
            # assign edge attributes
            for key, value in nxg[n][m].items():
                h[key] = value
            h_lookup[v][w] = h
            v.any_outgoing = h
        result.add_halfedges(h_lookup[v].values())
    # rev
    for v in h_lookup:
        for w in h_lookup[v]:
            h_lookup[v][w].rev = h_lookup[w][v]
    # nex, pre
    for v in h_lookup:
        outgoing_halfedges = list(h_lookup[v].values())
        dirs = np.array([v["pos"] - h.dest["pos"] for h in outgoing_halfedges])
        angles = angle_to_axis(dirs) % (2 * np.pi)
        order = np.argsort(angles)
        outgoing_halfedges = [outgoing_halfedges[i] for i in order]
        for hrevnex, h, hprerev in rotate_by(outgoing_halfedges, (0, 1, 2)):
            h.rev.nex = hrevnex
            h.pre = hprerev.rev

    # the faces
    unassigned_edges = copy(result.halfedges)
    while unassigned_edges:
        h = next(iter(unassigned_edges))
        f = Face(any_side=h)
        result.add_face(f)
        for k in f.halfedge_iter():
            k.face = f
            unassigned_edges.remove(k)
        # print(f.area())

    result.check_consistency()

    # detect 'outside' faces which should be None by their orientation
    # it is selected as the one with maximal negative area
    # (area 0 faces might have slightly negative areas due to numerical issues)
    outside_face = None
    current_min_area = 0
    for f in frozenset(result.faces):
        area = f.area()
        if area < current_min_area:
            current_min_area = area
            outside_face = f
    assert outside_face is not None, "Could not find an outside face to delete. Are all areas 0?"
    result.delete_face(outside_face)

    if not return_v_lookup:
        return result
    else:
        return result, v_lookup

delaunay_tiling

delaunay_tiling(
    points: ndarray, prune_sliver_angle: float | None = 0.3
) -> EuclideanPositionHEG

Build a Delaunay triangulation of points as an :class:EuclideanPositionHEG.

Parameters:

Name	Type	Description	Default
points	ndarray	(N, 2) array of 2D vertex positions.	required
prune_sliver_angle	float | None	If not None, iteratively delete border faces whose smallest interior angle is below this threshold (in radians), along with border vertices of order < 3. This cleans up thin sliver triangles produced by the Delaunay triangulation of the convex hull. Set to None to skip pruning.	0.3

Returns:

Type	Description
EuclideanPositionHEG	The Delaunay triangulation as a half-edge graph with vertex positions.

Source code in pleat/conversions.py

def delaunay_tiling(
    points: np.ndarray,
    prune_sliver_angle: float | None = 0.3,
) -> EuclideanPositionHEG:
    """Build a Delaunay triangulation of ``points`` as an :class:`EuclideanPositionHEG`.

    Args:
        points: ``(N, 2)`` array of 2D vertex positions.
        prune_sliver_angle: If not None, iteratively delete border faces whose
            smallest interior angle is below this threshold (in radians), along
            with border vertices of order < 3. This cleans up thin sliver
            triangles produced by the Delaunay triangulation of the convex hull.
            Set to ``None`` to skip pruning.

    Returns:
        The Delaunay triangulation as a half-edge graph with vertex positions.
    """
    from scipy.spatial import Delaunay

    points = np.asarray(points)
    assert points.ndim == 2 and points.shape[1] == 2, f"expected (N, 2) points, got {points.shape}"

    triangulation = Delaunay(points)
    faces = triangulation.simplices
    edges = np.stack([faces, np.roll(faces, 1, axis=1)], axis=-1).reshape(-1, 2)
    nx_graph = nx.Graph()
    nx_graph.add_nodes_from(range(len(points)))
    nx_graph.add_edges_from(edges)
    G = EHEG_from_nx(nx_graph, positions={i: pos for i, pos in enumerate(points)})

    if prune_sliver_angle is not None:
        G.recompute_lengths_and_angles()
        while True:
            to_delete = [
                f
                for f in G.faces
                if f.on_border() and np.min([h["in_angle"] for h in f.halfedge_iter()]) < prune_sliver_angle
            ]
            to_delete += [v for v in G.vertices if v.on_border() and v.order() < 3]
            if not to_delete:
                break
            G.delete_subset(to_delete)

    return G