Skip to content

crease_orientation

pleat.shrink_rotate.crease_orientation

Halfedge orientation marks for crease pattern stacking order.

Many origami pipelines need to know, for each interior edge, which of the two adjacent faces is above the other in the folded model. We encode this via a single halfedge attribute, the THIS_WAY mark:

The face whose halfedge carries ``THIS_WAY`` lies *above* the face on
the opposite side, in the folded model.

This module provides several strategies for setting THIS_WAY automatically. All assigners share two important conventions:

  1. Border halfedges are skipped. THIS_WAY is meaningful only on interior edges, where two faces meet.
  2. Already-assigned edges are not overwritten. Each helper checks for an existing THIS_WAY on either side of an edge and leaves it alone if present. This makes the helpers chainable — apply a primary strategy first, then a tiebreaker:

.. code-block:: python

   # Primary: faces with larger area on top.
   assign_this_way_by_face_area(G)
   # Tiebreaker on equal-area edges: distance from center.
   assign_this_way_by_distance(G)

Use :func:clear_this_way to start over.

Strategies

  • :func:assign_this_way_by_face_z_order and :func:assign_this_way_by_vertex_z_order — explicit numeric z_order attribute (e.g. set by user code or by a BFS).
  • :func:assign_this_way_by_face_bfs — BFS distance from a chosen source face; nearer faces lie on top.
  • :func:assign_this_way_from_center — convenience: BFS from the face closest to the geometric centroid of G.
  • :func:assign_this_way_by_distance — distance of face midpoints from a point (default: centroid); nearer faces lie on top.
  • :func:assign_this_way_by_face_degree — larger-degree (or smaller-, see flag) faces lie on top.
  • :func:assign_this_way_by_face_area — larger-area faces lie on top by default.

THIS_WAY module-attribute 

THIS_WAY = 'this_way'

Halfedge attribute name marking the upper side of an interior edge (h.face will lie above h.rev.face).

clear_this_way 

clear_this_way(G: HalfEdgeGraph) -> None

Remove all THIS_WAY marks from halfedges of G.

Call before re-running an assignment from scratch.

Source code in pleat/shrink_rotate/crease_orientation.py 
72
73
74
75
76
77
78
79
def clear_this_way(G: HalfEdgeGraph) -> None:
    """Remove all THIS_WAY marks from halfedges of *G*.

    Call before re-running an assignment from scratch.
    """
    for e in G.halfedges:
        if THIS_WAY in e.attributes:
            del e[THIS_WAY]

assign_this_way_by_face_z_order 

assign_this_way_by_face_z_order(
    G: HalfEdgeGraph, key: str = "z_order"
) -> None

Use a numeric face attribute key to orient each interior edge.

The halfedge whose face has the larger value of key is left unmarked; the opposite halfedge gets THIS_WAY (i.e. its face lies above). Ties are broken using the mean key over the faces incident to each endpoint.

Skips edges that already have THIS_WAY assigned on either side.

Source code in pleat/shrink_rotate/crease_orientation.py 
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
def assign_this_way_by_face_z_order(G: HalfEdgeGraph, key: str = "z_order") -> None:
    """Use a numeric face attribute ``key`` to orient each interior edge.

    The halfedge whose face has the *larger* value of ``key`` is left
    unmarked; the opposite halfedge gets THIS_WAY (i.e. its face lies
    above). Ties are broken using the mean ``key`` over the faces incident
    to each endpoint.

    Skips edges that already have THIS_WAY assigned on either side.
    """
    for e in _interior_unassigned_halfedges(G):
        f1, f2 = e.face, e.rev.face
        if f1[key] > f2[key]:
            e[THIS_WAY] = True
        elif f1[key] < f2[key]:
            e.rev[THIS_WAY] = True
        else:
            z_orig = np.mean([f[key] for f in e.orig.true_face_iter()])
            z_dest = np.mean([f[key] for f in e.dest.true_face_iter()])
            if z_orig > z_dest:
                e[THIS_WAY] = True
            elif z_dest > z_orig:
                e.rev[THIS_WAY] = True

assign_this_way_by_vertex_z_order 

assign_this_way_by_vertex_z_order(
    G: HalfEdgeGraph, key: str = "z_order"
) -> None

Like :func:assign_this_way_by_face_z_order but keyed on endpoint vertices.

Skips edges that already have THIS_WAY assigned on either side.

Source code in pleat/shrink_rotate/crease_orientation.py 
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
def assign_this_way_by_vertex_z_order(G: HalfEdgeGraph, key: str = "z_order") -> None:
    """Like :func:`assign_this_way_by_face_z_order` but keyed on endpoint vertices.

    Skips edges that already have THIS_WAY assigned on either side.
    """
    for e in _interior_unassigned_halfedges(G):
        v1, v2 = e.orig, e.dest
        if v1[key] > v2[key]:
            e[THIS_WAY] = True
        elif v1[key] < v2[key]:
            e.rev[THIS_WAY] = True
        else:
            z_orig = np.mean([v[key] for v in e.face.vertex_iter()])
            z_dest = np.mean([v[key] for v in e.rev.face.vertex_iter()])
            if z_orig > z_dest:
                e[THIS_WAY] = True
            elif z_dest > z_orig:
                e.rev[THIS_WAY] = True

assign_this_way_by_bfs 

assign_this_way_by_bfs(
    G: HalfEdgeGraph,
    source: Vertex | Face | set[Vertex] | set[Face],
) -> None

Use BFS depth from source face: shallower lies on top.

Skips edges that already have THIS_WAY assigned on either side.

Source code in pleat/shrink_rotate/crease_orientation.py 
143
144
145
146
147
148
149
150
151
152
153
154
def assign_this_way_by_bfs(G: HalfEdgeGraph, source: Vertex | Face | set[Vertex] | set[Face]) -> None:
    """Use BFS depth from *source* face: shallower lies on top.

    Skips edges that already have THIS_WAY assigned on either side.
    """
    if not isinstance(source, set):
        source = {source}
    source_faces = {f for s in source for f in (s.true_face_iter() if isinstance(s, Vertex) else [s])}
    source_vertices = {v for s in source for v in (s.vertex_iter() if isinstance(s, Face) else [s])}

    assign_this_way_by_face_bfs(G, source_faces)  # primary: face BFS
    assign_this_way_by_vertex_bfs(G, source_vertices)  # tiebreaker: vertex BFS

assign_this_way_by_face_bfs 

assign_this_way_by_face_bfs(
    G: HalfEdgeGraph, source: Face | set[Face]
) -> None

Use BFS depth from source face: shallower faces lie on top.

Faces visited later (greater BFS depth) are marked as lying below; the halfedge of the deeper-visited face on each interior edge gets THIS_WAY.

Skips edges that already have THIS_WAY assigned on either side.

Source code in pleat/shrink_rotate/crease_orientation.py 
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
def assign_this_way_by_face_bfs(G: HalfEdgeGraph, source: Face | set[Face]) -> None:
    """Use BFS depth from *source* face: shallower faces lie on top.

    Faces visited later (greater BFS depth) are marked as lying below; the
    halfedge of the deeper-visited face on each interior edge gets
    THIS_WAY.

    Skips edges that already have THIS_WAY assigned on either side.
    """
    # Reuse the canonical BFS spanner so the traversal matches other helpers.
    depth = _bfs_face_depth(source)
    for e in _interior_unassigned_halfedges(G):
        d_here = depth.get(e.face)
        d_other = depth.get(e.rev.face)
        if d_here is None or d_other is None:
            continue
        if d_here > d_other:
            e.rev[THIS_WAY] = True
        elif d_other > d_here:
            e[THIS_WAY] = True

assign_this_way_by_vertex_bfs 

assign_this_way_by_vertex_bfs(
    G: HalfEdgeGraph, source: Vertex | set[Vertex]
) -> None

Use BFS depth from source vertex: shallower faces lie on top.

Faces visited later (greater BFS depth) are marked as lying below; the halfedge of the deeper-visited face on each interior edge gets THIS_WAY.

Skips edges that already have THIS_WAY assigned on either side.

Source code in pleat/shrink_rotate/crease_orientation.py 
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
def assign_this_way_by_vertex_bfs(G: HalfEdgeGraph, source: Vertex | set[Vertex]) -> None:
    """Use BFS depth from *source* vertex: shallower faces lie on top.

    Faces visited later (greater BFS depth) are marked as lying below; the
    halfedge of the deeper-visited face on each interior edge gets
    THIS_WAY.

    Skips edges that already have THIS_WAY assigned on either side.
    """
    depth = _bfs_vertex_depth(source)
    for e in _interior_unassigned_halfedges(G):
        d_here = depth.get(e.orig)
        d_other = depth.get(e.dest)
        if d_here is None or d_other is None:
            continue
        if d_here > d_other:
            e.rev[THIS_WAY] = True
        elif d_other > d_here:
            e[THIS_WAY] = True

assign_this_way_from_center 

assign_this_way_from_center(G: HalfEdgeGraph) -> None

Convenience: BFS from the face nearest the geometric centroid of G.

Equivalent to selecting the centermost face and calling :func:assign_this_way_by_bfs. Skips already-assigned edges.

Source code in pleat/shrink_rotate/crease_orientation.py 
213
214
215
216
217
218
219
220
221
def assign_this_way_from_center(G: HalfEdgeGraph) -> None:
    """Convenience: BFS from the face nearest the geometric centroid of *G*.

    Equivalent to selecting the centermost face and calling
    :func:`assign_this_way_by_bfs`. Skips already-assigned edges.
    """
    center = _graph_centroid(G)
    src = _face_nearest_to(G, center)
    assign_this_way_by_bfs(G, src)

assign_this_way_by_distance 

assign_this_way_by_distance(
    G: HalfEdgeGraph, point=None
) -> None

Orient interior edges by distance of face midpoints from point.

The face whose midpoint is farther from point lies below (gets THIS_WAY). When point is None the centroid of G is used.

Skips already-assigned edges.

Source code in pleat/shrink_rotate/crease_orientation.py 
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
def assign_this_way_by_distance(G: HalfEdgeGraph, point=None) -> None:
    """Orient interior edges by distance of face midpoints from *point*.

    The face whose midpoint is *farther* from *point* lies below (gets
    THIS_WAY). When *point* is ``None`` the centroid of *G* is used.

    Skips already-assigned edges.
    """
    point = _graph_centroid(G) if point is None else np.asarray(point)
    for e in _interior_unassigned_halfedges(G):
        d_here = float(np.linalg.norm(np.asarray(e.face.midpoint()) - point))
        d_other = float(np.linalg.norm(np.asarray(e.rev.face.midpoint()) - point))
        if d_here > d_other:
            e.rev[THIS_WAY] = True
        elif d_other > d_here:
            e[THIS_WAY] = True
        else:  # faces have the same distance; go by distance of endpoints of the edge
            d_orig = float(np.linalg.norm(np.asarray(e.orig["pos"]) - point))
            d_dest = float(np.linalg.norm(np.asarray(e.dest["pos"]) - point))
            if d_orig > d_dest:
                e.rev[THIS_WAY] = True
            elif d_dest > d_orig:
                e[THIS_WAY] = True

assign_this_way_by_face_degree 

assign_this_way_by_face_degree(
    G: HalfEdgeGraph, larger_on_top: bool = True
) -> None

Orient interior edges by face degree (number of incident edges).

With larger_on_top (the default), the smaller-degree face is marked as lying below. Set larger_on_top=False to invert.

Skips already-assigned edges.

Source code in pleat/shrink_rotate/crease_orientation.py 
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
def assign_this_way_by_face_degree(G: HalfEdgeGraph, larger_on_top: bool = True) -> None:
    """Orient interior edges by face degree (number of incident edges).

    With *larger_on_top* (the default), the smaller-degree face is marked
    as lying below. Set ``larger_on_top=False`` to invert.

    Skips already-assigned edges.
    """
    for e in _interior_unassigned_halfedges(G):
        d_here = e.face.order()
        d_other = e.rev.face.order()
        if d_here == d_other:
            continue
        higher = (d_here > d_other) == larger_on_top
        if higher:
            e[THIS_WAY] = True
        else:
            e.rev[THIS_WAY] = True

assign_this_way_by_face_area 

assign_this_way_by_face_area(
    G: HalfEdgeGraph, larger_on_top: bool = True
) -> None

Orient interior edges by face area.

With larger_on_top (the default), the smaller-area face lies below. Set larger_on_top=False to invert.

Skips already-assigned edges.

Source code in pleat/shrink_rotate/crease_orientation.py 
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
def assign_this_way_by_face_area(G: HalfEdgeGraph, larger_on_top: bool = True) -> None:
    """Orient interior edges by face area.

    With *larger_on_top* (the default), the smaller-area face lies below.
    Set ``larger_on_top=False`` to invert.

    Skips already-assigned edges.
    """
    areas = {f: f.area() for f in G.faces if not f.on_border()}
    for e in _interior_unassigned_halfedges(G):
        a_here = areas.get(e.face)
        a_other = areas.get(e.rev.face)
        if a_here is None or a_other is None or a_here == a_other:
            continue
        higher = (a_here > a_other) == larger_on_top
        if higher:
            e[THIS_WAY] = True
        else:
            e.rev[THIS_WAY] = True