alphageometry/modules/utils.py

"""Geometry utility helpers for alphageometry modules.

This module provides small, well-tested, dependency-free helpers for
polygons and triangulation used by the demo and visualizer. The code is
kept intentionally simple and documented so it is easy to unit-test.
"""

from __future__ import annotations

import math
from typing import List, Sequence, Tuple

Point = Tuple[float, float]
Triangle = Tuple[int, int, int]


def polygon_area(points: Sequence[Point]) -> float:
    """Return the (unsigned) area of a polygon using the shoelace formula.

    Points may be in any order (clockwise or counter-clockwise).
    """
    pts = list(points)
    if len(pts) < 3:
        return 0.0
    a = 0.0
    for i in range(len(pts)):
        x1, y1 = pts[i]
        x2, y2 = pts[(i + 1) % len(pts)]
        a += x1 * y2 - y1 * x2
    return 0.5 * abs(a)


def polygon_centroid(points: Sequence[Point]) -> Point:
    """Compute centroid (average of vertices) of a polygon.

    This is the simple arithmetic centroid (not the area-weighted polygon
    centroid). It's sufficient for lightweight visual placement.
    """
    pts = list(points)
    if not pts:
        return (0.0, 0.0)
    sx = sum(p[0] for p in pts)
    sy = sum(p[1] for p in pts)
    n = len(pts)
    return (sx / n, sy / n)


def _cross(a: Point, b: Point, c: Point) -> float:
    """Return cross product (b - a) x (c - b).

    Positive for counter-clockwise turn, negative for clockwise.
    """
    return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0])


def point_in_triangle(pt: Point, a: Point, b: Point, c: Point) -> bool:
    """Return True if pt lies inside triangle abc (including edges).

    Uses barycentric / sign tests which are robust for our demo floats.
    """
    # Compute barycentric coordinates
    v0 = (c[0] - a[0], c[1] - a[1])
    v1 = (b[0] - a[0], b[1] - a[1])
    v2 = (pt[0] - a[0], pt[1] - a[1])
    dot00 = v0[0] * v0[0] + v0[1] * v0[1]
    dot01 = v0[0] * v1[0] + v0[1] * v1[1]
    dot02 = v0[0] * v2[0] + v0[1] * v2[1]
    dot11 = v1[0] * v1[0] + v1[1] * v1[1]
    dot12 = v1[0] * v2[0] + v1[1] * v2[1]
    denom = dot00 * dot11 - dot01 * dot01
    if denom == 0:
        # degenerate triangle
        return False
    u = (dot11 * dot02 - dot01 * dot12) / denom
    v = (dot00 * dot12 - dot01 * dot02) / denom
    return u >= -1e-12 and v >= -1e-12 and (u + v) <= 1 + 1e-12


def earclip_triangulate(poly: Sequence[Point]) -> List[Triangle]:
    """Triangulate a simple polygon (no self-intersections) using ear clipping.

    Returns a list of triangles as tuples of vertex indices into the original
    polygon list. The polygon is not modified.
    """
    pts = list(poly)
    n = len(pts)
    if n < 3:
        return []
    # Work on indices to avoid copying points repeatedly
    idx = list(range(n))

    def is_convex(i_prev: int, i_curr: int, i_next: int) -> bool:
        a, b, c = pts[i_prev], pts[i_curr], pts[i_next]
        return _cross(a, b, c) > 0

    triangles: List[Triangle] = []
    safety = 0
    # Continue until only one triangle remains
    while len(idx) > 3 and safety < 10_000:
        safety += 1
        ear_found = False
        for k in range(len(idx)):
            i_prev = idx[(k - 1) % len(idx)]
            i_curr = idx[k]
            i_next = idx[(k + 1) % len(idx)]
            if not is_convex(i_prev, i_curr, i_next):
                continue
            a, b, c = pts[i_prev], pts[i_curr], pts[i_next]
            # ensure no other point is inside triangle abc
            any_inside = False
            for j in idx:
                if j in (i_prev, i_curr, i_next):
                    continue
                if point_in_triangle(pts[j], a, b, c):
                    any_inside = True
                    break
            if any_inside:
                continue
            # ear found
            triangles.append((i_prev, i_curr, i_next))
            idx.pop(k)
            ear_found = True
            break
        if not ear_found:
            # polygon might be degenerate; abort to avoid infinite loop
            break
    if len(idx) == 3:
        triangles.append((idx[0], idx[1], idx[2]))
    return triangles


def rdp_simplify(points: Sequence[Point], epsilon: float) -> List[Point]:
    """Ramer-Douglas-Peucker line simplification for polyline/polygon vertices.

    If the input is a closed polygon (first==last), the output will also be
    closed when epsilon is < small value. The algorithm works on open lists; for
    closed polygons callers can treat the ring appropriately.
    """
    pts = list(points)
    n = len(pts)
    if n < 3:
        return pts

    def _perp_dist(pt: Point, a: Point, b: Point) -> float:
        # distance from pt to line ab
        dx = b[0] - a[0]
        dy = b[1] - a[1]
        if dx == 0 and dy == 0:
            return math.hypot(pt[0] - a[0], pt[1] - a[1])
        t = ((pt[0] - a[0]) * dx + (pt[1] - a[1]) * dy) / (dx * dx + dy * dy)
        projx = a[0] + t * dx
        projy = a[1] + t * dy
        return math.hypot(pt[0] - projx, pt[1] - projy)

    def _rdp(seq: List[Point]) -> List[Point]:
        if len(seq) < 3:
            return seq[:]
        a = seq[0]
        b = seq[-1]
        maxd = 0.0
        idx = 0
        for i in range(1, len(seq) - 1):
            d = _perp_dist(seq[i], a, b)
            if d > maxd:
                maxd = d
                idx = i
        if maxd > epsilon:
            left = _rdp(seq[: idx + 1])
            right = _rdp(seq[idx:])
            return left[:-1] + right
        else:
            return [a, b]

    return _rdp(pts)


def bounding_box(points: Sequence[Point]) -> Tuple[Point, Point]:
    pts = list(points)
    if not pts:
        return (0.0, 0.0), (0.0, 0.0)
    minx = min(p[0] for p in pts)
    maxx = max(p[0] for p in pts)
    miny = min(p[1] for p in pts)
    maxy = max(p[1] for p in pts)
    return (minx, miny), (maxx, maxy)


def polygon_is_ccw(points: Sequence[Point]) -> bool:
    """Return True if polygon vertices are ordered counter-clockwise.

    Uses the signed shoelace area: positive means counter-clockwise.
    """
    pts = list(points)
    if len(pts) < 3:
        return True
    a = 0.0
    for i in range(len(pts)):
        x1, y1 = pts[i]
        x2, y2 = pts[(i + 1) % len(pts)]
        a += x1 * y2 - y1 * x2
    return a > 0


def point_on_segment(p: Point, a: Point, b: Point, eps: float = 1e-12) -> bool:
    """Return True if point p lies on the segment ab (including endpoints)."""
    (px, py), (ax, ay), (bx, by) = p, a, b
    # collinear check via cross and bounding box check
    cross = (py - ay) * (bx - ax) - (px - ax) * (by - ay)
    if abs(cross) > eps:
        return False
    # between check
    dot = (px - ax) * (px - bx) + (py - ay) * (py - by)
    return dot <= eps


def point_in_polygon(pt: Point, poly: Sequence[Point]) -> bool:
    """Winding-number style point-in-polygon test (True if inside or on edge).

    Robust for simple polygons and includes points on the boundary.
    """
    x, y = pt
    wn = 0
    n = len(poly)
    for i in range(n):
        x0, y0 = poly[i]
        x1, y1 = poly[(i + 1) % n]
        # check if point on edge
        if point_on_segment(pt, (x0, y0), (x1, y1)):
            return True
        if y0 <= y:
            if y1 > y and _cross((x0, y0), (x1, y1), (x, y)) > 0:
                wn += 1
        else:
            if y1 <= y and _cross((x0, y0), (x1, y1), (x, y)) < 0:
                wn -= 1
    return wn != 0


def convex_hull(points: Sequence[Point]) -> List[Point]:
    """Compute convex hull of a set of points using Graham scan.

    Returns the vertices of the convex hull in counter-clockwise order. For
    fewer than 3 unique points the function returns the sorted unique list.
    """
    pts = sorted(set(points))
    if len(pts) <= 1:
        return list(pts)

    def _cross(o: Point, a: Point, b: Point) -> float:
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

    lower: List[Point] = []
    for p in pts:
        while len(lower) >= 2 and _cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)

    upper: List[Point] = []
    for p in reversed(pts):
        while len(upper) >= 2 and _cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)

    # Concatenate lower and upper, omit last point of each because it repeats
    hull = lower[:-1] + upper[:-1]
    return hull


def rdp_simplify_closed(points: Sequence[Point], epsilon: float) -> List[Point]:
    """Simplify a closed polygon ring using RDP and return a closed ring.

    The returned list will have first point != last point (open ring) but the
    consumer can append the first to close it if desired.
    """
    pts = list(points)
    if not pts:
        return []
    # If ring is closed (first == last), remove last for processing
    closed = pts[0] == pts[-1]
    if closed:
        pts = pts[:-1]
    simplified = rdp_simplify(pts, epsilon)
    # If simplified reduced to 2 points for a polygon, keep at least 3 by
    # returning the original small ring
    if len(simplified) < 3:
        return pts
    return simplified


def safe_earclip_triangulate(poly: Sequence[Point]) -> List[Triangle]:
    """Wrapper around earclip_triangulate that ensures consistent orientation
    and returns triangles as indices into the original polygon list.
    """
    pts = list(poly)
    if not pts:
        return []
    # Ensure polygon is counter-clockwise for our earclip implementation
    if not polygon_is_ccw(pts):
        pts = list(reversed(pts))
        reversed_map = True
    else:
        reversed_map = False
    tris = earclip_triangulate(pts)
    # Map indices back to original order if we reversed
    if reversed_map:
        # when reversed, index i in pts corresponds to original index (n-1-i)
        n = len(pts)
        mapped = [tuple(n - 1 - idx for idx in tri) for tri in tris]
        return mapped
    return tris
__all__ = [
    "Point",
    "Triangle",
    "polygon_area",
    "polygon_centroid",
    "polygon_is_ccw",
    "point_in_triangle",
    "point_in_polygon",
    "earclip_triangulate",
    "safe_earclip_triangulate",
    "rdp_simplify",
    "rdp_simplify_closed",
    "bounding_box",
    "convex_hull",
]