Skip to content

distill

pleat.gjh.distill

Distill a finite tiled half-edge graph back into a minimal :data:TilesetSpec.

The algorithm iteratively refines two equivalence classifiers:

  1. Faces are first classified by congruency (same shape).
  2. Half-edges are then classified by their local context: own class, reverse class, neighbors, and the classes of their two incident faces.
  3. Faces are re-classified by the cyclic sequence of their edges' classes.

Steps 2-3 repeat until the number of distinct classes stops growing. The fixpoint yields, for each tile in the spec, an exemplar face plus a labelling of its outgoing edges.

spec_from_graph 

spec_from_graph(G: EuclideanPositionHEG) -> TilesetSpec

Analyse a finite tiled Euclidean graph and produce a :data:TilesetSpec.

Source code in pleat/gjh/distill.py 
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
def spec_from_graph(G: EuclideanPositionHEG) -> TilesetSpec:
    """Analyse a finite tiled Euclidean graph and produce a :data:`TilesetSpec`."""
    cc = congruency_classifier()
    fs = list(G.faces)
    face_dicts: list[dict[Face, int]] = [{f: cc.classify(f) for f in fs}]

    hs = list(G.halfedges)
    lengths = np.array([np.linalg.norm(h.orig["pos"] - h.dest["pos"]) for h in hs])
    length_groups = fast_group_closeby(lengths[:, None], eps=1e-6)
    edge_dicts: list[dict[HalfEdge, int]] = [{h: int(lg) for h, lg in zip(hs, length_groups)}]

    before = 0
    for _ in count():
        hc = _EdgeClassifier(face_dicts[-1], edge_dicts[-1])
        edge_dicts.append({h: hc.classify(h) for h in hs})

        fc = _FaceClassifier(edge_dicts[-1])
        face_dicts.append({f: fc.classify(f) for f in fs})

        after = len(set(edge_dicts[-1].values())) + len(set(face_dicts[-1].values()))
        if before >= after:
            break
        before = after

    # Pick one exemplar face per class (skipping classes that touched the open border).
    exemplar_fs: list[Face] = []
    for key in set(face_dicts[-2].values()):
        if key < 0:
            continue
        exemplar_fs.append(next(f for f in fs if face_dicts[-2][f] == key and face_dicts[-1][f] >= 0))
    exemplar_fs.sort(key=lambda f: -f.order())

    tile_names = {f: chr(97 + i) for i, f in enumerate(exemplar_fs)}
    edge_names: dict[int, tuple[str, int]] = {}
    for f in exemplar_fs:
        for i, h in enumerate(f.halfedge_iter()):
            edge_class = edge_dicts[-2][h]
            if edge_class not in edge_names:
                edge_names[edge_class] = (tile_names[f], i)

    return {tile_names[f]: [edge_names[edge_dicts[-2][h.rev]] for h in f.halfedge_iter()] for f in exemplar_fs}