import json, time
from pathlib import Path
import numpy as np
from scipy.spatial import ConvexHull

SEED = 206
rng = np.random.default_rng(SEED)
N_DIR = 64
angles = np.linspace(0, 2*np.pi, N_DIR, endpoint=False)
DIRECTIONS = np.c_[np.cos(angles), np.sin(angles)]


def hull(points):
    p = np.asarray(points, float)
    if len(p) <= 2:
        return p
    return p[ConvexHull(p).vertices]


def random_polygon(n=12):
    # A compact, nondegenerate convex object represented by its hull vertices.
    return hull(rng.normal(size=(n, 2)) * np.array([1.0, .7]) + rng.normal(size=2))


def support_tuple(poly, dirs=DIRECTIONS):
    p = np.asarray(poly)
    # deterministic tie break is adequate away from measure-zero ties
    return p[np.argmax(p @ dirs.T, axis=0)]


def decode(x):
    return hull(np.asarray(x))


def tuple_add(x, y, alpha=1., beta=1.):
    return alpha * np.asarray(x) + beta * np.asarray(y)


def generic_minkowski(a, b):
    return hull((a[:, None, :] + b[None, :, :]).reshape(-1, 2))


def point_segment_distance(p, a, b):
    v = b-a
    den = np.dot(v, v)
    t = 0.0 if den == 0 else np.clip(np.dot(p-a, v)/den, 0, 1)
    return np.linalg.norm(p-(a+t*v))


def directed_poly_distance(a, b):
    if len(b) == 1:
        return max(np.linalg.norm(x-b[0]) for x in a)
    return max(min(point_segment_distance(x, b[i], b[(i+1)%len(b)]) for i in range(len(b))) for x in a)


def hausdorff(a, b):
    return max(directed_poly_distance(a,b), directed_poly_distance(b,a))


def tuple_distance(x, y):
    return np.max(np.linalg.norm(np.asarray(x)-np.asarray(y), axis=1))


def verify_math(trials=300):
    add_err, scale_err, lip_ratios = [], [], []
    for _ in range(trials):
        a, b = random_polygon(), random_polygon()
        xa, xb = support_tuple(a), support_tuple(b)
        # Support identity, checked by comparing every directional support point.
        lhs = support_tuple(generic_minkowski(a,b))
        rhs = xa + xb
        add_err.append(np.max(np.linalg.norm(lhs-rhs, axis=1)))
        lam = rng.uniform(0, 3)
        lhs_s = support_tuple(lam*a)
        scale_err.append(np.max(np.linalg.norm(lhs_s-lam*xa, axis=1)))
        # Perturb point tuples; convexification should not amplify Hausdorff error.
        noise = rng.normal(size=xa.shape)*.03
        dec0, dec1 = decode(xa), decode(xa+noise)
        lip_ratios.append(hausdorff(dec0,dec1)/(np.max(np.linalg.norm(noise,axis=1))+1e-12))
    return {"max_add_identity_error": float(max(add_err)),
            "max_scaling_identity_error": float(max(scale_err)),
            "max_convexification_ratio": float(max(lip_ratios)),
            "median_convexification_ratio": float(np.median(lip_ratios))}


def chain_trial(length, n=8):
    objs = [random_polygon(n) for _ in range(length)]
    # Perturb each latent tuple independently, then compare decoded chain output.
    tuples = [support_tuple(x) for x in objs]
    noisy = [x + rng.normal(size=x.shape)*0.01 for x in tuples]
    structured, structured_noisy = tuples[0], noisy[0]
    t0 = time.perf_counter()
    for x, xn in zip(tuples[1:], noisy[1:]):
        structured = tuple_add(structured, x)
        structured_noisy = tuple_add(structured_noisy, xn)
    structured_time = time.perf_counter()-t0
    # Generic control repeatedly forms all pairwise vertex sums and hulls.
    generic = objs[0]
    t0 = time.perf_counter()
    for x in objs[1:]:
        generic = generic_minkowski(generic, x)
    generic_time = time.perf_counter()-t0
    exact = generic
    struct_poly = decode(structured)
    noisy_poly = decode(structured_noisy)
    return {"structured_error": hausdorff(struct_poly, exact),
            "structured_perturbed_error": hausdorff(noisy_poly, struct_poly),
            "structured_tuple_bound": tuple_distance(structured_noisy, structured),
            "generic_vertices": int(len(generic)),
            "structured_time": structured_time, "generic_time": generic_time}


def main():
    math = verify_math()
    rows = [chain_trial(k) for k in range(2, 11)]
    out = {"seed": SEED, "directions": N_DIR, "math": math, "chains": rows}
    Path("results.json").write_text(json.dumps(out, indent=2))
    print(json.dumps(out, indent=2))

if __name__ == "__main__":
    main()