Spaces:
Running
Running
File size: 4,157 Bytes
19abe39 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 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 | import numpy as np
from typing import Optional
BOUNDARY_TOL = 1e-9
VERTEX_TOL = 1e-9
class CreaseGraph:
"""
Planar graph representing an origami crease pattern on a unit square.
Vertices: points in [0,1]x[0,1], deduplicated by proximity.
Edges: segments between vertices, labeled M (mountain), V (valley), or B (boundary).
"""
def __init__(self):
self.vertices: dict[int, tuple[float, float]] = {}
self.edges: dict[int, tuple[int, int, str]] = {}
self.vertex_edges: dict[int, list[int]] = {}
self._next_vertex_id: int = 0
self._next_edge_id: int = 0
corners = [(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)]
for x, y in corners:
vid = self._next_vertex_id
self.vertices[vid] = (x, y)
self.vertex_edges[vid] = []
self._next_vertex_id += 1
boundary_pairs = [(0, 1), (1, 2), (2, 3), (3, 0)]
for v1, v2 in boundary_pairs:
eid = self._next_edge_id
self.edges[eid] = (v1, v2, 'B')
self.vertex_edges[v1].append(eid)
self.vertex_edges[v2].append(eid)
self._next_edge_id += 1
def add_vertex(self, x: float, y: float) -> int:
for vid, (vx, vy) in self.vertices.items():
if abs(vx - x) < VERTEX_TOL and abs(vy - y) < VERTEX_TOL:
return vid
vid = self._next_vertex_id
self.vertices[vid] = (float(x), float(y))
self.vertex_edges[vid] = []
self._next_vertex_id += 1
return vid
def add_edge(self, v1_id: int, v2_id: int, assignment: str) -> int:
pair = frozenset((v1_id, v2_id))
for eid, (ev1, ev2, _) in self.edges.items():
if frozenset((ev1, ev2)) == pair:
return eid
eid = self._next_edge_id
self.edges[eid] = (v1_id, v2_id, assignment)
self.vertex_edges[v1_id].append(eid)
self.vertex_edges[v2_id].append(eid)
self._next_edge_id += 1
return eid
def get_cyclic_edges(self, vertex_id: int) -> list[int]:
vx, vy = self.vertices[vertex_id]
edge_ids = self.vertex_edges[vertex_id]
def angle_of_edge(eid: int) -> float:
ev1, ev2, _ = self.edges[eid]
other_id = ev2 if ev1 == vertex_id else ev1
ox, oy = self.vertices[other_id]
return float(np.arctan2(oy - vy, ox - vx))
return sorted(edge_ids, key=angle_of_edge)
def interior_vertices(self) -> list[int]:
result = []
for vid, (x, y) in self.vertices.items():
if (
x > BOUNDARY_TOL
and x < 1.0 - BOUNDARY_TOL
and y > BOUNDARY_TOL
and y < 1.0 - BOUNDARY_TOL
):
result.append(vid)
return result
def split_edge(self, edge_id: int, new_vertex_id: int) -> tuple[int, int]:
ev1, ev2, assignment = self.edges[edge_id]
del self.edges[edge_id]
if edge_id in self.vertex_edges[ev1]:
self.vertex_edges[ev1].remove(edge_id)
if edge_id in self.vertex_edges[ev2]:
self.vertex_edges[ev2].remove(edge_id)
eid1 = self._next_edge_id
self.edges[eid1] = (ev1, new_vertex_id, assignment)
self.vertex_edges[ev1].append(eid1)
self.vertex_edges[new_vertex_id].append(eid1)
self._next_edge_id += 1
eid2 = self._next_edge_id
self.edges[eid2] = (new_vertex_id, ev2, assignment)
self.vertex_edges[new_vertex_id].append(eid2)
self.vertex_edges[ev2].append(eid2)
self._next_edge_id += 1
return (eid1, eid2)
def crease_edges(self) -> list[int]:
return [eid for eid, (_, _, a) in self.edges.items() if a in ('M', 'V')]
def boundary_midpoints(self) -> list[tuple[float, float]]:
midpoints = []
for eid, (v1, v2, assignment) in self.edges.items():
if assignment == 'B':
x1, y1 = self.vertices[v1]
x2, y2 = self.vertices[v2]
midpoints.append(((x1 + x2) / 2.0, (y1 + y2) / 2.0))
return midpoints
|