"""Check the five STL shadows for any exact line of bilateral symmetry.

Usage
    python verify_five_mirror_axes.py "path/to/Double_Bowl.stl"

Requires Python 3.9+ and its standard library. Reads the original binary STL.
Camera sightline is cos(theta)*n0 + sin(theta)*(n0 x up), where up is the
normalized AXIS and n0 is world Z projected perpendicular to up, then normalized.
The camera looks along the sightline. Screen right is up x sightline.

A shadow's mirror must also preserve its convex hull. A unique longest hull
edge forces the only possible mirror to be its perpendicular bisector. For
each view, this program proves the edge is unique and exhibits a reflected
hull vertex outside the hull. Its printed lower bounds should be approximately
as follows, in the unitless coordinates of the STL.

    Angle  Edge length gap  Reflected point outside by
       0      3.447825              0.022563
      12      0.0000205             5.057443
      30      2.795206              3.300014
      45      2.751797              0.043013
     110      0.0000376             6.867436

All claims are certified by outward-rounded integer intervals. The check is
specific to these five directions and tests exact symmetry.
"""

import argparse
from dataclasses import dataclass
from math import isqrt
from pathlib import Path
from struct import Struct, unpack_from

DIGITS = 45
SCALE = 10**DIGITS
STL_SCALE = 2**16
ANGLES = (0, 12, 30, 45, 110)
AXIS = (6847216433474491, 4446256701202778, -5774636651787387)


def ceil_div(n, d):
    return -(-n // d)


@dataclass(frozen=True)
class Interval:
    # Endpoints in units of 1/SCALE.
    lo: int
    hi: int

    @classmethod
    def rational(cls, n, d=1):
        return cls(n * SCALE // d, ceil_div(n * SCALE, d))

    def __add__(self, other):
        return Interval(self.lo + other.lo, self.hi + other.hi)

    def __neg__(self):
        return Interval(-self.hi, -self.lo)

    def __sub__(self, other):
        return self + -other

    def __mul__(self, other):
        products = [a * b for a in (self.lo, self.hi) for b in (other.lo, other.hi)]
        return Interval(min(products) // SCALE, ceil_div(max(products), SCALE))

    def __truediv__(self, other):
        if other.lo <= 0 <= other.hi:
            raise ValueError("Cannot certify division by an interval containing zero")
        pairs = [(a * SCALE, b) for a in (self.lo, self.hi) for b in (other.lo, other.hi)]
        return Interval(min(n // d for n, d in pairs), max(ceil_div(n, d) for n, d in pairs))

    def sqrt(self):
        if self.lo < 0:
            raise ValueError("Cannot certify the square root of this interval")
        hi = self.hi * SCALE
        root = isqrt(hi)
        return Interval(isqrt(self.lo * SCALE), root + (root * root < hi))

    def padded(self, amount):
        return Interval(self.lo - amount, self.hi + amount)


I = Interval.rational
ZERO = I(0)
ONE = I(1)


def arctangent_inverse(denominator):
    x = I(1, denominator)
    x_squared = x * x
    power = x
    total = ZERO
    for index in range(40):
        term = power / I(2 * index + 1)
        total = total + (term if index % 2 == 0 else -term)
        power = power * x_squared
    return total.padded((power / I(81)).hi)


PI = I(16) * arctangent_inverse(5) - I(4) * arctangent_inverse(239)


def sin_cos(degrees):
    if degrees == 0:
        return ZERO, ONE
    x = PI * I(degrees, 180)
    x_squared = x * x
    sine, cosine = x, ONE
    sin_term, cos_term = sine, cosine
    for index in range(1, 30):
        sin_term = sin_term * x_squared / I((2 * index) * (2 * index + 1))
        cos_term = cos_term * x_squared / I((2 * index - 1) * (2 * index))
        sine = sine + (sin_term if index % 2 == 0 else -sin_term)
        cosine = cosine + (cos_term if index % 2 == 0 else -cos_term)
    sin_remainder = sin_term * x_squared / I(60 * 61)
    cos_remainder = cos_term * x_squared / I(59 * 60)
    return sine.padded(sin_remainder.hi), cosine.padded(cos_remainder.hi)


def dot(a, b):
    products = iter(x * y for x, y in zip(a, b))
    result = next(products)
    for product in products:
        result = result + product
    return result


def subtract(a, b):
    return tuple(x - y for x, y in zip(a, b))


def det(a, b):
    return a[0] * b[1] - a[1] * b[0]


def read_vertices(path):
    content = path.read_bytes()
    if len(content) < 84:
        raise ValueError("Expected a binary STL")
    count, = unpack_from("<I", content, 80)
    if len(content) != 84 + 50 * count:
        raise ValueError("The binary STL size does not match its triangle count")
    triangle = Struct("<9f")
    points = set()
    for offset in range(84, len(content), 50):
        coords = triangle.unpack_from(content, offset + 12)
        for start in (0, 3, 6):
            scaled = tuple(value * STL_SCALE for value in coords[start : start + 3])
            if not all(value.is_integer() for value in scaled):
                raise ValueError("This checker expects the source STL's exact coordinate grid")
            points.add(tuple(int(value) for value in scaled))
    if (count, len(points)) != (1806, 905):
        raise ValueError("Expected the study STL with 1806 triangles and 905 unique vertices")
    origin = min(points)
    return [subtract(point, origin) for point in sorted(points)]


def project(vertices, degrees):
    x, y, z = AXIS
    transverse = I(x * x + y * y).sqrt()
    size = I(x * x + y * y + z * z).sqrt()
    up = tuple(I(c) / size for c in AXIS)
    base_right = tuple(I(c) / transverse for c in (y, -x, 0))
    n0 = tuple(I(c) / (size * transverse) for c in (-x * z, -y * z, x * x + y * y))
    sine, cosine = sin_cos(degrees)
    right = tuple(cosine * b + sine * n for b, n in zip(base_right, n0))
    screen = []
    for vertex in vertices:
        position = tuple(I(c, STL_SCALE) for c in vertex)
        screen.append((dot(right, position), dot(up, position)))
    return screen


def hull(vertices, screen, degrees):
    if degrees == 0:
        # The horizontal and vertical coordinates each have a common positive
        # denominator. Their integer numerators give the exact sort order.
        x, y, _ = AXIS
        order = sorted(range(len(vertices)), key=lambda i: (dot((y, -x, 0), vertices[i]), dot(AXIS, vertices[i])))
    else:
        order = sorted(range(len(vertices)), key=lambda i: screen[i][0].lo)
        if any(screen[i][0].hi >= screen[j][0].lo for i, j in zip(order, order[1:])):
            raise ValueError("Could not certify the horizontal sort order")

    def turn(i, j, k):
        row = det(subtract(screen[j], screen[i]), subtract(screen[k], screen[i]))
        if row.lo > 0:
            return True
        if row.hi < 0:
            return False
        u = subtract(vertices[j], vertices[i])
        v = subtract(vertices[k], vertices[i])
        if all(u[a] * v[b] == u[b] * v[a] for a, b in ((0, 1), (0, 2), (1, 2))):
            return False
        raise ValueError("Could not certify a hull turn")

    def half(indices):
        chain = []
        for i in indices:
            while len(chain) > 1 and not turn(chain[-2], chain[-1], i):
                chain.pop()
            chain.append(i)
        return chain[:-1]

    return [screen[i] for i in half(order) + half(reversed(order))]


def certify_outline(polygon):
    edges = [(p, subtract(q, p)) for p, q in zip(polygon, polygon[1:] + polygon[:1])]
    lengths_squared = [dot(edge, edge) for _, edge in edges]
    i = max(range(len(edges)), key=lambda j: lengths_squared[j].lo)
    longest = lengths_squared[i]
    runner_up = max(length.hi for j, length in enumerate(lengths_squared) if j != i)
    length_gap = longest.sqrt() - Interval(runner_up, runner_up).sqrt()
    if length_gap.lo <= 0:
        raise ValueError("Could not certify a unique longest boundary edge")

    start, edge = edges[i]
    midpoint = tuple(s + d * I(1, 2) for s, d in zip(start, edge))
    edge_lengths = [length.sqrt() for length in lengths_squared]
    best_witness = 0
    for point in polygon:
        shift = I(2) * dot(subtract(point, midpoint), edge) / longest
        reflected = subtract(point, tuple(shift * d for d in edge))
        for (side_start, side), side_length in zip(edges, edge_lengths):
            signed_distance = -det(side, subtract(reflected, side_start)) / side_length
            best_witness = max(best_witness, signed_distance.lo)
    if best_witness <= 0:
        raise ValueError("Could not certify a reflected vertex outside the convex outline")
    return length_gap.lo, best_witness


def format_lower_bound(value, decimals=10):
    integer = value // 10 ** (DIGITS - decimals)
    whole, fraction = divmod(integer, 10**decimals)
    return f"{whole}.{fraction:0{decimals}d}"


def main():
    parser = argparse.ArgumentParser(description=__doc__.splitlines()[0])
    parser.add_argument("stl", type=Path, help="path to the original binary STL")
    args = parser.parse_args()

    try:
        points = read_vertices(args.stl)
        print("Angle   Hull vertices   Longest-edge gap >=   Reflected point outside by >=")
        for degrees in ANGLES:
            outline = hull(points, project(points, degrees), degrees)
            gap, witness = certify_outline(outline)
            print(f"{degrees:>5} {len(outline):>15} {format_lower_bound(gap):>21} {format_lower_bound(witness):>30}")
    except (ValueError, OSError) as error:
        parser.exit(1, f"Verification stopped. {error}\n")

    print("All five shadows lack an exact mirror axis.")


if __name__ == "__main__":
    main()
