"""Dirichlet eigenvalues on convex domains in three compact surfaces.

Run with Python, NumPy and SciPy, or call simulate(dict) from Pyodide.
The drawing of the flat torus is a topological picture; its metric is flat.
"""

import argparse
import json
import math
import time
from itertools import combinations

import numpy as np
from scipy.sparse import coo_matrix
from scipy.sparse.linalg import eigsh
from scipy.spatial import ConvexHull, Delaunay
from scipy.optimize import brentq


def metric(x, kind):
    r2 = np.sum(x * x, axis=-1)
    eye = np.broadcast_to(np.eye(2), x.shape[:-1] + (2, 2)).copy()
    xx = x[..., :, None] * x[..., None, :]
    if kind == "positive":
        return eye / (1 + r2)[..., None, None] - xx / (1 + r2)[..., None, None] ** 2
    if kind == "negative":
        return eye / (1 - r2)[..., None, None] + xx / (1 - r2)[..., None, None] ** 2
    return eye


def distances(points, kind):
    dot = points @ points.T
    r2 = np.sum(points * points, axis=1)
    if kind == "positive":
        c = (1 + dot) / np.sqrt((1 + r2[:, None]) * (1 + r2[None, :]))
        return np.arccos(np.clip(c, -1, 1))
    if kind == "negative":
        c = (1 - dot) / np.sqrt((1 - r2[:, None]) * (1 - r2[None, :]))
        return np.arccosh(np.maximum(c, 1))
    return np.sqrt(np.maximum(r2[:, None] + r2[None, :] - 2 * dot, 0))


def polygon(rng, diameter, aspect, kind, shape="random"):
    # Opposite vertices fix the intrinsic diameter without a numerical search.
    if shape == "strip":
        p = np.array([[-1., -aspect], [1., -aspect], [1., aspect], [-1., aspect]])
    else:
        half = int(rng.integers(5, 9))
        angle = np.arange(half) * np.pi / half + rng.uniform(-0.13, 0.13, half)
        radius = rng.uniform(0.86, 1.0, half)
        p = np.column_stack((radius * np.cos(angle), aspect * radius * np.sin(angle)))
        p = np.concatenate((p, -p))
        p = p[ConvexHull(p).vertices]
    spin = rng.uniform(0, 2 * np.pi)
    rotation = np.array([[np.cos(spin), -np.sin(spin)], [np.sin(spin), np.cos(spin)]])
    p = p @ rotation.T
    max_radius = np.max(np.linalg.norm(p, axis=1))
    if kind == "positive":
        scale = np.tan(diameter / 2) / max_radius
    elif kind == "negative":
        scale = np.tanh(diameter / 2) / max_radius
    else:
        scale = diameter / (2 * max_radius)
    return p * scale


def projective_radius(radius, kind):
    if kind == "positive":
        return np.tan(radius)
    if kind == "negative":
        return np.tanh(radius)
    return radius


def tangential_polygon(rng, diameter, inradius, kind):
    """Geodesic sides tangent to B(0,r), with opposite vertices at D/2."""
    outer = float(projective_radius(diameter / 2, kind))
    support = float(projective_radius(inradius, kind))
    largest_gap = 2 * np.arccos(support / outer)
    if largest_gap < .006:
        raise ValueError("The requested radius is extremely close to D/2. Choose r=D/2 for the disk, or leave a larger difference for a polygon.")
    remaining = np.pi - largest_gap
    count = max(2, int(np.ceil(2 * remaining / largest_gap))) + int(rng.integers(1, 4))
    weights = rng.uniform(.8, 1.2, count)
    gaps = np.r_[largest_gap, remaining * weights / weights.sum()]
    angles = np.r_[0., np.cumsum(gaps[:-1])]
    angles = np.r_[angles, angles + np.pi] + rng.uniform(0, 2 * np.pi)
    normal = np.column_stack((np.cos(angles), np.sin(angles)))
    following = np.roll(normal, -1, axis=0)
    matrices = np.stack((normal, following), axis=1)
    vertices = np.linalg.solve(matrices, np.full((len(normal), 2, 1), support)).reshape(-1, 2)
    return vertices


def constant_lens(diameter, inradius, kind, resolution):
    """An equal-ball lens in the simply connected constant-curvature model."""
    half = diameter / 2
    if kind == "positive":
        radius = np.arctan2(1 - np.cos(inradius) * np.cos(half), np.sin(inradius) * np.cos(half))
    elif kind == "negative":
        lower = float(np.log(np.cosh(half)))
        if inradius <= lower + 1e-10:
            raise ValueError(f"A hyperbolic equal-ball lens at D={diameter:.6g} needs r>{lower:.6g}. The random convex polygon supports thinner domains.")
        ratio = (np.cosh(inradius) * np.cosh(half) - 1) / (np.sinh(inradius) * np.cosh(half))
        radius = np.arctanh(ratio)
    else:
        radius = diameter ** 2 / (8 * inradius) + inradius / 2
    separation = max(0., radius - inradius)
    angles = max(64, 4 * ((resolution + 1) // 2))
    theta = np.arange(angles) * (2 * np.pi / angles)
    direction = np.column_stack((np.cos(theta), np.sin(theta)))
    cosine = abs(direction[:, 0])
    if kind == "positive":
        a, b = np.cos(separation), np.sin(separation) * cosine
        radial = np.arccos(np.clip(np.cos(radius) / np.sqrt(a * a + b * b), -1, 1)) - np.arctan2(b, a)
    elif kind == "negative":
        a, b = np.cosh(separation), np.sinh(separation) * cosine
        radial = np.arccosh(np.maximum(np.cosh(radius) / np.sqrt(a * a - b * b), 1)) - np.arctanh(b / a)
    else:
        root = np.sqrt(radius * radius - separation * separation * (1 - cosine * cosine))
        radial = (radius * radius - separation * separation) / (root + separation * cosine)
    boundary = direction * projective_radius(radial, kind)[:, None]
    return radial_mesh(boundary, resolution), float(radius)


def radial_mesh(boundary, resolution):
    angles = len(boundary)
    rings = max(5, resolution // 2)
    points = np.vstack((np.zeros((1, 2)), *[boundary * j / rings for j in range(1, rings + 1)]))
    triangles = [[0, 1 + k, 1 + (k + 1) % angles] for k in range(angles)]
    for j in range(1, rings):
        lo, hi = 1 + (j - 1) * angles, 1 + j * angles
        for k in range(angles):
            nxt = (k + 1) % angles
            triangles.extend(([lo + k, hi + k, hi + nxt], [lo + k, hi + nxt, lo + nxt]))
    fixed = np.arange(len(points)) >= 1 + (rings - 1) * angles
    return points, np.asarray(triangles), fixed


def prescribed_strip(rng, diameter, inradius, kind):
    outer = projective_radius(diameter / 2, kind)
    maximum = float(np.arctan(outer / np.sqrt(2))) if kind == "positive" else (float(np.arctanh(outer / np.sqrt(2))) if kind == "negative" else diameter / np.sqrt(8))
    if inradius > maximum + 1e-10:
        raise ValueError(f"At D={diameter:.6g}, the strip family requires r≤{maximum:.6g}. Choose the random convex polygon for larger inradii.")
    seed = int(rng.integers(0, 2**32 - 1))

    def candidate(aspect):
        return polygon(np.random.default_rng(seed), diameter, aspect, kind, "strip")

    aspect = brentq(lambda a: inradius_polygon(candidate(a), kind) - inradius, 1e-10, 1, xtol=1e-12)
    return candidate(aspect)


def strip_mesh(p, resolution):
    nu, nv = resolution, max(12, resolution // 2)
    u, v = np.meshgrid(np.linspace(0, 1, nu + 1), np.linspace(0, 1, nv + 1))
    points = p[0] + u.ravel()[:, None] * (p[1] - p[0]) + v.ravel()[:, None] * (p[3] - p[0])
    fixed = ((u == 0) | (u == 1) | (v == 0) | (v == 1)).ravel()
    triangles = []
    for j in range(nv):
        for i in range(nu):
            a = j * (nu + 1) + i
            triangles.extend(([a, a + 1, a + nu + 2], [a, a + nu + 2, a + nu + 1]))
    return points, np.asarray(triangles), fixed


def inradius_polygon(p, kind):
    edges = np.roll(p, -1, axis=0) - p
    normal = np.column_stack((edges[:, 1], -edges[:, 0]))
    normal /= np.linalg.norm(normal, axis=1)[:, None]
    support = np.sum(normal * p, axis=1)
    h = float(np.min(support))
    if kind == "positive":
        return float(np.arctan(h))
    if kind == "negative":
        # In a hyperbolic polygon the incenter need not be its symmetry center.
        # In hyperboloid coordinates, tangency to three sides is a 3x3 system.
        sides = np.column_stack((support, -normal)) / np.sqrt(1 - support ** 2)[:, None]
        triples = np.asarray(list(combinations(range(len(p)), 3)))
        matrices = sides[triples]
        matrices = matrices[np.abs(np.linalg.det(matrices)) > 1e-12]
        v = np.linalg.solve(matrices, np.ones((len(matrices), 3, 1))).reshape(-1, 3)
        norm = v[:, 0] ** 2 - np.sum(v[:, 1:] ** 2, axis=1)
        v = v[(norm > 1e-12) & (v[:, 0] > 0)]
        candidates = np.vstack((np.zeros((1, 2)), v[:, 1:] / v[:, :1]))
        scale = np.sqrt(1 - np.sum(candidates ** 2, axis=1))[:, None]
        sinh_distance = (support - candidates @ normal.T) / (scale * np.sqrt(1 - support ** 2))
        best = np.max(np.min(sinh_distance, axis=1))
        return float(np.arcsinh(best))
    return h


def polygon_mesh(p, resolution):
    # Align the sampling grid with a thin polygon before triangulating it.
    _, axes = np.linalg.eigh(p.T @ p)
    p = p @ axes
    lo, hi = p.min(axis=0), p.max(axis=0)
    hull = ConvexHull(p)
    width = hi - lo
    h = max(width) / resolution
    nx = max(12, int(np.ceil(width[0] / h)))
    ny = max(12, int(np.ceil(width[1] / h)))
    spacing = width / np.array([nx, ny])
    boundary = []
    for a, b in zip(p, np.roll(p, -1, axis=0)):
        count = max(2, int(np.ceil(np.linalg.norm((b - a) / spacing))))
        for t in np.arange(count) / count:
            boundary.append((1 - t) * a + t * b)
    boundary = np.asarray(boundary)
    gx, gy = np.meshgrid(np.linspace(lo[0], hi[0], nx + 1), np.linspace(lo[1], hi[1], ny + 1))
    interior = np.column_stack((gx.ravel(), gy.ravel()))
    inequalities = interior @ hull.equations[:, :2].T + hull.equations[:, 2]
    interior = interior[np.all(inequalities < -min(spacing) * 0.18, axis=1)]
    points = np.vstack((boundary, interior))
    triangles = Delaunay(points / spacing).simplices
    a = points[triangles[:, 1]] - points[triangles[:, 0]]
    b = points[triangles[:, 2]] - points[triangles[:, 0]]
    double_area = np.abs(a[:, 0] * b[:, 1] - a[:, 1] * b[:, 0])
    triangles = triangles[double_area > h * h * 1e-10]
    fixed = np.arange(len(points)) < len(boundary)
    return points @ axes.T, triangles, fixed


def disk_mesh(radius, resolution):
    rings = max(5, resolution // 2)
    angles = max(40, resolution * 3)
    theta = np.arange(angles) * 2 * np.pi / angles
    points = [[0.0, 0.0]]
    for j in range(1, rings + 1):
        r = radius * j / rings
        points.extend(np.column_stack((r * np.cos(theta), r * np.sin(theta))).tolist())
    triangles = []
    for k in range(angles):
        triangles.append([0, 1 + k, 1 + (k + 1) % angles])
    for j in range(1, rings):
        lower, upper = 1 + (j - 1) * angles, 1 + j * angles
        for k in range(angles):
            nxt = (k + 1) % angles
            triangles.extend(([lower + k, upper + k, upper + nxt], [lower + k, upper + nxt, lower + nxt]))
    points = np.asarray(points)
    fixed = np.arange(len(points)) >= 1 + (rings - 1) * angles
    return points, np.asarray(triangles), fixed


def sphere_rotation(rng):
    n = rng.normal(size=3)
    n /= np.linalg.norm(n)
    a = np.array([0.0, 0.0, 1.0]) if abs(n[2]) < 0.9 else np.array([1.0, 0.0, 0.0])
    e1 = np.cross(a, n)
    e1 /= np.linalg.norm(e1)
    phase = rng.uniform(0, 2 * np.pi)
    e1 = np.cos(phase) * e1 + np.sin(phase) * np.cross(n, e1)
    return np.column_stack((e1, np.cross(n, e1), n))


def ellipsoid_exp(points, axes, rotation):
    """Exponential map by the constrained geodesic equation in R^3."""
    q = 1.0 / axes ** 2
    direction = rotation[:, 2]
    center = direction / np.sqrt(np.sum(q * direction ** 2))
    basis = ellipsoid_frame(center, axes, rotation[:, 0])
    velocity = points @ basis.T
    x, _ = geodesic_flow(center, velocity, axes, steps=48)
    constraint_error = float(np.max(np.abs(np.sum(x * x * q, axis=1) - 1)))
    return x, center, constraint_error


def ellipsoid_frame(center, axes, hint=None):
    q = 1.0 / axes ** 2
    normal = q * center
    normal /= np.linalg.norm(normal)
    if hint is None:
        hint = np.array([0., 0., 1.]) if abs(normal[2]) < .9 else np.array([1., 0., 0.])
    e1 = hint - np.dot(hint, normal) * normal
    e1 /= np.linalg.norm(e1)
    return np.column_stack((e1, np.cross(normal, e1)))


def geodesic_flow(origins, velocity, axes, steps=24):
    q = 1.0 / axes ** 2
    x = np.broadcast_to(origins, velocity.shape).copy()
    v = velocity.copy()

    def acceleration(xv, vv):
        numerator = np.sum(vv * vv * q, axis=1)
        denominator = np.sum((xv * q) ** 2, axis=1)
        return -(numerator / denominator)[:, None] * xv * q

    dt = 1.0 / steps
    for _ in range(steps):
        a1 = acceleration(x, v)
        x2, v2 = x + 0.5 * dt * v, v + 0.5 * dt * a1
        a2 = acceleration(x2, v2)
        x3, v3 = x + 0.5 * dt * v2, v + 0.5 * dt * a2
        a3 = acceleration(x3, v3)
        x4, v4 = x + dt * v3, v + dt * a3
        a4 = acceleration(x4, v4)
        x += dt * (v + 2 * v2 + 2 * v3 + v4) / 6
        v += dt * (a1 + 2 * a2 + 2 * a3 + a4) / 6
    return x, v


def ellipsoid_distance(origins, targets, axes, steps=24):
    """Short geodesic shooting, batched over point pairs in a normal region."""
    targets = np.asarray(targets, dtype=float).reshape(-1, 3)
    origins = np.broadcast_to(origins, targets.shape).copy()
    normal = origins / axes ** 2
    normal /= np.linalg.norm(normal, axis=1)[:, None]
    chord = targets - origins
    tangent = chord - np.sum(chord * normal, axis=1)[:, None] * normal
    length = np.linalg.norm(tangent, axis=1)
    e1 = tangent / np.maximum(length[:, None], 1e-15)
    near = length < 1e-12
    for i in np.flatnonzero(near):
        e1[i] = ellipsoid_frame(origins[i], axes)[:, 0]
    e2 = np.cross(normal, e1)
    u = np.column_stack((length, np.zeros(len(length))))
    epsilon = 1e-6 / (axes.max() / axes.min() ** 2)
    for _ in range(5):
        velocity = u[:, :1] * e1 + u[:, 1:] * e2
        x, terminal = geodesic_flow(origins, velocity, axes, steps)
        residual3 = x - targets
        residual = np.column_stack((np.sum(residual3 * e1, axis=1), np.sum(residual3 * e2, axis=1)))
        if np.max(np.linalg.norm(residual, axis=1)) < 2e-10:
            break
        perturbed = np.vstack((velocity + epsilon * e1, velocity + epsilon * e2))
        xx, _ = geodesic_flow(np.vstack((origins, origins)), perturbed, axes, steps)
        d1, d2 = (xx[:len(x)] - x) / epsilon, (xx[len(x):] - x) / epsilon
        jacobian = np.stack((np.column_stack((np.sum(d1 * e1, axis=1), np.sum(d1 * e2, axis=1))), np.column_stack((np.sum(d2 * e1, axis=1), np.sum(d2 * e2, axis=1)))), axis=2)
        u -= np.linalg.solve(jacobian, residual[:, :, None]).reshape(-1, 2)
    velocity = u[:, :1] * e1 + u[:, 1:] * e2
    x, terminal = geodesic_flow(origins, velocity, axes, steps)
    error = float(np.max(np.linalg.norm(x - targets, axis=1)))
    if error > 3e-7:
        raise RuntimeError("Geodesic shooting did not reach the requested accuracy.")
    return np.linalg.norm(u, axis=1), terminal, error


def lens_boundary(center, basis, axes, radius, inradius, angles=64):
    separation = radius - inradius
    centers, _ = geodesic_flow(center, np.array([-separation, separation])[:, None] * basis[:, 0], axes)
    theta = np.arange(angles) * (2 * np.pi / angles)
    direction = np.column_stack((np.cos(theta), np.sin(theta)))
    cosine = abs(direction[:, 0])
    root = np.sqrt(np.maximum(radius ** 2 - separation ** 2 * (1 - cosine ** 2), 0))
    radial = (radius ** 2 - separation ** 2) / np.maximum(root + separation * cosine, 1e-15)
    lower, upper = np.zeros(angles), np.full(angles, radius)
    worst_shooting = 0.
    for _ in range(7):
        points, radial_velocity = geodesic_flow(center, (direction * radial[:, None]) @ basis.T, axes)
        origins = np.repeat(centers, angles, axis=0)
        targets = np.vstack((points, points))
        distance, terminal, shooting_error = ellipsoid_distance(origins, targets, axes)
        worst_shooting = max(worst_shooting, shooting_error)
        distance = distance.reshape(2, angles)
        terminal = terminal.reshape(2, angles, 3)
        active = np.argmax(distance, axis=0)
        d = distance[active, np.arange(angles)]
        mismatch = d - radius
        if np.max(abs(mismatch)) < 5e-9:
            break
        lower = np.where(mismatch < 0, radial, lower)
        upper = np.where(mismatch >= 0, radial, upper)
        endpoint_direction = terminal[active, np.arange(angles)] / np.maximum(d[:, None], 1e-15)
        radial_direction = radial_velocity / np.maximum(radial[:, None], 1e-15)
        derivative = np.sum(endpoint_direction * radial_direction, axis=1)
        candidate = radial - mismatch / np.maximum(derivative, 1e-5)
        candidate = np.where((candidate > lower) & (candidate < upper), candidate, .5 * (lower + upper))
        radial = np.where(abs(mismatch) < 5e-9, radial, candidate)
    else:
        # The last Newton update must be evaluated before returning its boundary.
        points, _ = geodesic_flow(center, (direction * radial[:, None]) @ basis.T, axes)
        distance, _, shooting_error = ellipsoid_distance(origins, np.vstack((points, points)), axes)
        worst_shooting = max(worst_shooting, shooting_error)
        mismatch = np.max(distance.reshape(2, angles), axis=0) - radius
    if np.max(abs(mismatch)) > 2e-7:
        raise RuntimeError("The geodesic lens boundary did not converge.")
    return direction * radial[:, None], points, centers, {"boundary_distance_residual": float(np.max(abs(mismatch))), "shooting_endpoint_residual": worst_shooting}


def ellipsoid_boundary_diameter(boundary, axes):
    i, j = np.triu_indices(len(boundary), 1)
    chord = np.linalg.norm(boundary[i] - boundary[j], axis=1)
    curvature = axes.max() / axes.min() ** 2
    upper = 2 * np.arcsin(np.minimum(.999999, curvature * chord / 2)) / curvature
    order = np.argsort(chord)[::-1]
    best, endpoint_error = 0., 0.
    pending = order
    while len(pending):
        batch = pending[:64]
        distance, _, residual = ellipsoid_distance(boundary[i[batch]], boundary[j[batch]], axes)
        best = max(best, float(np.max(distance)))
        endpoint_error = max(endpoint_error, residual)
        pending = pending[64:]
        pending = pending[upper[pending] > best + 1e-9]
    return best, endpoint_error


def lens_mesh(center, basis, axes, radius, inradius, resolution):
    angles = max(48, 4 * ((resolution + 1) // 2))
    boundary, _, centers, checks = lens_boundary(center, basis, axes, radius, inradius, angles)
    points, triangles, fixed = radial_mesh(boundary, resolution)
    embedded, _ = geodesic_flow(center, points @ basis.T, axes, steps=48)
    diameter, error = ellipsoid_boundary_diameter(embedded[fixed], axes)
    checks["shooting_endpoint_residual"] = max(checks["shooting_endpoint_residual"], error)
    checks["surface_constraint_residual"] = float(np.max(abs(np.sum((embedded / axes) ** 2, axis=1) - 1)))
    checks["boundary_samples"] = angles
    checks["construction_radius"] = radius
    checks["center_distance"] = 2 * (radius - inradius)
    checks["centers"] = centers.tolist()
    return points, triangles, fixed, embedded, diameter, checks


def ellipsoid_lens(axes, rotation, diameter, inradius, resolution, construction_radius=None):
    q = 1 / axes ** 2
    center = rotation[:, 2] / np.sqrt(np.sum(q * rotation[:, 2] ** 2))
    basis = ellipsoid_frame(center, axes, rotation[:, 0])
    curvature = axes.max() / axes.min() ** 2
    radius_limit = .35 / curvature
    if construction_radius is None:
        if not 0 < diameter <= 2 * radius_limit + 1e-12:
            raise ValueError(f"For this ellipsoid, choose 0 < D ≤ {2 * radius_limit:.6g}.")
        minimum = radius_limit - math.sqrt(max(radius_limit ** 2 - diameter ** 2 / 4, 0))
        if not minimum - 1e-10 <= inradius <= diameter / 2 + 1e-10:
            raise ValueError(f"At D={diameter:.6g}, this guaranteed-convex lens family requires {minimum:.6g} ≤ r ≤ {diameter / 2:.6g}. No parameters were changed.")
        if abs(diameter - 2 * inradius) < 1e-9:
            radius = inradius
        else:
            radius = diameter ** 2 / (8 * inradius) + inradius / 2
            for _ in range(7):
                _, boundary, _, _ = lens_boundary(center, basis, axes, radius, inradius, 48)
                measured, _ = ellipsoid_boundary_diameter(boundary, axes)
                mismatch = measured - diameter
                if abs(mismatch) < 3e-7:
                    break
                radius = float(np.clip(radius - mismatch * measured / (4 * inradius), inradius, radius_limit))
            if abs(mismatch) > 2e-5:
                raise RuntimeError("The diameter fit for the geodesic lens did not converge.")
    else:
        radius = float(construction_radius)
        if not 0 < inradius <= radius <= radius_limit + 1e-12:
            raise ValueError("Invalid internal lens construction parameters.")
    result = lens_mesh(center, basis, axes, radius, inradius, resolution)
    checks = result[-1]
    checks["radius_limit"] = radius_limit
    checks["convexity_radius_lower_bound"] = np.pi / (2 * curvature)
    checks["target_diameter_error"] = None if construction_radius is not None else abs(result[4] - diameter)
    if construction_radius is None and checks["target_diameter_error"] > max(5e-5, 2e-4 * diameter):
        raise RuntimeError("The requested diameter needs a finer geometric fit; increase the mesh resolution.")
    return result, center, basis


def assemble(points, triangles, kind, embedded=None):
    tri = points[triangles]
    edge = np.stack((tri[:, 1] - tri[:, 0], tri[:, 2] - tri[:, 0]), axis=2)
    determinant = np.linalg.det(edge)
    area = np.abs(determinant) / 2
    inverse = np.linalg.inv(edge)
    reference = np.array([[-1., -1.], [1., 0.], [0., 1.]])
    gradient = np.einsum("ij,tjk->tik", reference, inverse)
    stiffness = np.zeros((len(triangles), 3, 3))
    mass = np.zeros_like(stiffness)
    barycentric = np.array([[2/3, 1/6, 1/6], [1/6, 2/3, 1/6], [1/6, 1/6, 2/3]])

    if embedded is not None:
        xyz = embedded[triangles]
        physical_edge = np.stack((xyz[:, 1] - xyz[:, 0], xyz[:, 2] - xyz[:, 0]), axis=2)
        jacobian = np.einsum("tij,tjk->tik", physical_edge, inverse)
        g = np.einsum("tki,tkj->tij", jacobian, jacobian)
    for basis in barycentric:
        if embedded is None:
            sample = np.einsum("j,tjk->tk", basis, tri)
            g = metric(sample, kind)
        density = np.sqrt(np.linalg.det(g))
        invg = np.linalg.inv(g)
        weight = area * density / 3
        stiffness += np.einsum("tik,tkl,tjl->tij", gradient, invg, gradient) * weight[:, None, None]
        mass += np.outer(basis, basis)[None, :, :] * weight[:, None, None]
    row = np.repeat(triangles, 3, axis=1).ravel()
    col = np.tile(triangles, (1, 3)).ravel()
    shape = (len(points), len(points))
    k = coo_matrix((stiffness.ravel(), (row, col)), shape=shape).tocsr()
    m = coo_matrix((mass.ravel(), (row, col)), shape=shape).tocsr()
    return k, m, float(np.sum(mass))


def solve(points, triangles, fixed, kind, embedded=None):
    k, m, area = assemble(points, triangles, kind, embedded)
    free = np.flatnonzero(~fixed)
    kk, mm = k[free][:, free], m[free][:, free]
    if len(free) < 4:
        raise ValueError("The domain is too thin for this mesh. Increase the resolution.")
    initial = np.random.default_rng(913).normal(size=len(free))
    values, vectors = eigsh(kk, k=3, M=mm, sigma=0, which="LM", tol=2e-9, v0=initial)
    order = np.argsort(values)
    values, vectors = values[order], vectors[:, order]
    first = np.zeros(len(points))
    first[free] = vectors[:, 0]
    if np.sum(first) < 0:
        first *= -1
    residuals = []
    for value, vector in zip(values, vectors.T):
        a, b = kk @ vector, mm @ vector
        residuals.append(float(np.linalg.norm(a - value * b) / max(np.linalg.norm(a), 1e-15)))
    return values, first, area, residuals


def surface_mesh(kind, axes):
    if kind == "negative":
        # Regular {8,8} octagon: opposite sides are identified.
        vertex_radius = np.sqrt(np.cos(np.pi / 4))
        theta = np.arange(8) * np.pi / 4
        vertex = vertex_radius * np.column_stack((np.cos(theta), np.sin(theta)))
        klein = 2 * vertex / (1 + np.sum(vertex * vertex, axis=1))[:, None]
        boundary = []
        for a, b in zip(klein, np.roll(klein, -1, axis=0)):
            for t in np.linspace(0, 1, 25, endpoint=False):
                q = (1 - t) * a + t * b
                p = q / (1 + np.sqrt(1 - np.dot(q, q)))
                boundary.append([p[0], p[1], 0.0])
        xyz = np.asarray([[0., 0., 0.]] + boundary)
        triangles = [[0, i + 1, (i + 1) % len(boundary) + 1] for i in range(len(boundary))]
        return xyz, np.asarray(triangles)
    nu, nv = 64, 32
    vertices, triangles = [], []
    for j in range(nv + 1):
        v = j * np.pi / nv if kind == "positive" else j * 2 * np.pi / nv
        for i in range(nu + 1):
            u = i * 2 * np.pi / nu
            if kind == "positive":
                p = axes * np.array([np.sin(v) * np.cos(u), np.sin(v) * np.sin(u), np.cos(v)])
            else:
                p = np.array([(1.8 + .6 * np.cos(v)) * np.cos(u), (1.8 + .6 * np.cos(v)) * np.sin(u), .6 * np.sin(v)])
            vertices.append(p)
    for j in range(nv):
        for i in range(nu):
            a = j * (nu + 1) + i
            triangles.extend(([a, a + 1, a + nu + 2], [a, a + nu + 2, a + nu + 1]))
    return np.asarray(vertices), np.asarray(triangles)


def display_domain(points, kind, rng, rotation, embedded=None):
    if embedded is not None:
        return embedded
    if kind == "positive":
        xyz = np.column_stack((points, np.ones(len(points))))
        xyz /= np.linalg.norm(xyz, axis=1)[:, None]
        return xyz @ rotation.T
    if kind == "negative":
        z = points / (1 + np.sqrt(1 - np.sum(points * points, axis=1)))[:, None]
        z = z[:, 0] + 1j * z[:, 1]
        # The whole domain stays in a ball smaller than systole / 4.
        shift = np.tanh(0.04 / 2) * np.sqrt(rng.random()) * np.exp(2j * np.pi * rng.random())
        z = (z + shift) / (1 + np.conjugate(shift) * z)
        return np.column_stack((z.real, z.imag, np.full(len(z), 0.004)))
    offset = rng.uniform(0, 4, 2)
    uv = (points + offset) * (2 * np.pi / 4)
    u, v = uv.T
    return np.column_stack(((1.8 + .603 * np.cos(v)) * np.cos(u), (1.8 + .603 * np.cos(v)) * np.sin(u), .603 * np.sin(v)))


def pack_mesh(vertices, triangles, values=None):
    return {
        "vertices": np.asarray(vertices, dtype=float).ravel().tolist(),
        "indices": np.asarray(triangles, dtype=int).ravel().tolist(),
        "values": (np.zeros(len(vertices)) if values is None else values).astype(float).tolist(),
    }


def build_target(kind, deformation, diameter, inradius, shape, resolution, seed, construction_radius=None):
    rng = np.random.default_rng(seed)
    rotation = sphere_rotation(rng)
    axes = np.array([1., 1., 1. + deformation if kind == "positive" else 1.])
    embedded, geometry_checks = None, {}
    if kind == "positive" and abs(deformation) > 1e-12:
        data, center, basis = ellipsoid_lens(axes, rotation, diameter, inradius, resolution, construction_radius)
        points, triangles, fixed, embedded, attained_diameter, geometry_checks = data
        radius = geometry_checks["construction_radius"]

        def remesh(n):
            cp, ct, cf, ce, _, _ = lens_mesh(center, basis, axes, radius, inradius, n)
            return cp, ct, cf, ce

        family = "Intersection of two strongly convex geodesic balls on the ellipsoid"
        diameter_method = "Maximum short-geodesic distance on the sampled lens boundary; radius fitted to the target"
        inradius_method = "Exact lens inradius R−s, attained at the midpoint of the two centers"
        shape = "lens"
    else:
        if shape == "random" and .49999 < inradius / diameter < .5:
            # A nearly circular target is represented by its smooth lens instead
            # of thousands of almost parallel tangent sides.
            shape = "lens"
        if abs(inradius - diameter / 2) < 1e-12:
            chart_radius = projective_radius(diameter / 2, kind)
            points, triangles, fixed = disk_mesh(chart_radius, resolution)

            def remesh(n):
                return (*disk_mesh(chart_radius, n), None)

            family = "Geodesic disk"
            shape = "disk"
            diameter_method = "Exact diameter 2r of the target geodesic disk"
            inradius_method = "Exact radius of the target geodesic disk"
        elif shape == "lens":
            (points, triangles, fixed), radius = constant_lens(diameter, inradius, kind, resolution)

            def remesh(n):
                return (*constant_lens(diameter, inradius, kind, n)[0], None)

            geometry_checks["construction_radius"] = radius
            family = "Equal-ball geodesic lens in the constant-curvature covering space"
            diameter_method = "Exact diameter from the right-triangle identity for the target lens"
            inradius_method = "Exact lens inradius R−s"
        else:
            vertices = prescribed_strip(rng, diameter, inradius, kind) if shape == "strip" else tangential_polygon(rng, diameter, inradius, kind)
            mesher = strip_mesh if shape == "strip" else polygon_mesh
            points, triangles, fixed = mesher(vertices, resolution)

            def remesh(n):
                return (*mesher(vertices, n), None)

            geometry_checks["vertex_diameter_error"] = abs(float(np.max(distances(vertices, kind))) - diameter)
            geometry_checks["polygon_vertices"] = len(vertices)
            family = "Geodesic strip in projective coordinates" if shape == "strip" else "Random tangential geodesic polygon"
            diameter_method = "Exact intrinsic diameter: two opposite vertices at distance D/2 from the center"
            inradius_method = "Largest inscribed circle, obtained from the side constraints" if shape == "strip" else "All geodesic sides are tangent to the centered intrinsic circle of radius r"
        attained_diameter = diameter
    return {"points": points, "triangles": triangles, "fixed": fixed, "embedded": embedded, "diameter": attained_diameter, "inradius": inradius, "axes": axes, "rotation": rotation, "rng": rng, "remesh": remesh, "family": family, "shape": shape, "diameter_method": diameter_method, "inradius_method": inradius_method, "geometry_checks": geometry_checks}


def theory_for_surface(kind, deformation):
    euclidean = {"title": "Andrews–Clutterbuck, Proof of the fundamental gap conjecture", "url": "https://arxiv.org/abs/1006.1686"}
    if kind == "positive" and abs(deformation) < 1e-12:
        return {"kind": "exact", "value": 3., "scope": "Infimum over proper geodesically convex Dirichlet domains on the round unit sphere; the sharp constant is approached by shrinking thin domains.", "references": [{"title": "Dai–Seto–Wei, Fundamental gap estimate for convex domains on sphere—the case n=2", "url": "https://arxiv.org/abs/1803.01115"}]}
    if kind == "negative":
        return {"kind": "exact", "value": 0., "scope": "Infimum over convex Dirichlet domains on the compact hyperbolic surface. Negative sectional curvature permits normalized gaps arbitrarily close to zero.", "references": [{"title": "Khan–Nguyen, Negative curvature constricts the fundamental gap of convex domains", "url": "https://arxiv.org/abs/2211.06404"}]}
    if kind == "flat":
        return {"kind": "upper_bound", "value": 1., "scope": "Global infimum is at most 1 under the manuscript's definition of convexity: wrapped bands are admissible. The exact global value is not asserted here.", "local_reference": {"value": 3., "scope": "Sharp infimum for the strongly convex domains that lift to bounded Euclidean convex domains."}, "references": [euclidean], "derivation": "On R²/(LZ)², a wrapped band of width 0<w<L/2 has gap=4π²/L², D²=L²/4+w², and normalized gap=1+4w²/L²→1."}
    return {"kind": "upper_bound", "value": 3., "exact_value_known": False,
            "scope": "The global infimum is at most 3, as on every smooth surface. Its exact value is not determined here, and no positive all-domain lower bound is certified. The tested lens family can have a minimum above 3; its finite search is not claimed to approximate the global infimum closely.",
            "derivation": "At fixed aspect a in (0,1], shrinking strongly convex domains can approach a Euclidean 1-by-a rectangle after rescaling. Metric, Dirichlet spectrum and diameter convergence give normalized gaps tending to 3(1+a^2). Taking a to zero afterwards proves the all-domain upper bound 3.",
            "references": [euclidean, {"title": "Dibble, The convexity radius of a Riemannian manifold", "url": "https://arxiv.org/abs/1412.0341"}, {"title": "Xu, Local estimate on convexity radius and decay of injectivity radius in a Riemannian manifold", "url": "https://arxiv.org/abs/1704.03269"}]}


def surface_constant(kind, deformation):
    start = time.perf_counter()
    seed = 481516
    resolution = 24 if kind == "positive" and abs(deformation) > 1e-12 else 36
    records, specifications = [], []
    if kind == "positive" and abs(deformation) > 1e-12:
        axes = np.array([1., 1., 1. + deformation])
        radius_limit = .35 * axes.min() ** 2 / axes.max()
        for scale in (.45, .95):
            for fraction in (.2, .5, .8, 1.):
                radius = scale * radius_limit
                specifications.append((2 * radius, fraction * radius, "lens", radius))
        ranges = {"construction_radius": [.45 * radius_limit, .95 * radius_limit], "inradius_over_ball_radius": [.2, 1.], "centers": "Eight reproducible locations and orientations on the ellipsoid"}
        families = ["Intersections of small strongly convex geodesic balls"]
    else:
        for diameter in (.35, .8, 1.3):
            for ratio in (.06, .22, .44):
                specifications.append((diameter, ratio * diameter, "random", None))
            for ratio in (.035, .10, .27):
                specifications.append((diameter, ratio * diameter, "strip", None))
        ranges = {"diameter": [.35, 1.3], "inradius_over_diameter": [.035, .44], "seeds": "Fixed independently of the selected domain"}
        families = ["Tangential geodesic polygons", "Projective geodesic strips"]

    def evaluate(spec, index, mesh_resolution):
        diameter, inradius, shape, radius = spec
        domain = build_target(kind, deformation, diameter, inradius, shape, mesh_resolution, seed + index, radius)
        values, _, _, residual = solve(domain["points"], domain["triangles"], domain["fixed"], kind, domain["embedded"])
        actual_diameter = domain["diameter"]
        return {"family": domain["family"], "diameter": actual_diameter, "inradius": inradius, "eigenvalues": values[:2].tolist(), "normalized_gap": float((values[1] - values[0]) * actual_diameter ** 2 / np.pi ** 2), "resolution": mesh_resolution, "nodes": len(domain["points"]), "seed": seed + index, "algebraic_residual": max(residual[:2]), "method": "P1 finite elements", "construction_radius": radius}

    for index, spec in enumerate(specifications):
        records.append(evaluate(spec, index, resolution))
    best = min(range(len(records)), key=lambda j: records[j]["normalized_gap"])
    refined = evaluate(specifications[best], best, int(resolution * 1.5))
    change = abs(refined["normalized_gap"] - records[best]["normalized_gap"])
    refinement = {"coarse": records[best]["normalized_gap"], "fine": refined["normalized_gap"], "absolute_change": change, "relative_change": change / max(abs(refined["normalized_gap"]), 1e-15), "numerically_sensitive": change > .1 * abs(refined["normalized_gap"]), "certified_error_bound": False}
    refined["refined_from_record"] = best
    records.append(refined)
    if kind == "flat":
        length = 4.
        for width in (.08, .2, .6):
            diameter = math.sqrt(length ** 2 / 4 + width ** 2)
            first = np.pi ** 2 / width ** 2
            second = first + 4 * np.pi ** 2 / length ** 2
            records.append({"family": "Wrapped flat cylinder (analytic spectrum)", "diameter": diameter, "inradius": width / 2, "eigenvalues": [first, second], "normalized_gap": 1 + 4 * width ** 2 / length ** 2, "resolution": None, "method": "Exact separation of variables", "width": width})
        families.append("Wrapped flat cylinders, analytic spectrum")
        ranges["wrapped_band_width"] = [.08, .6]
    return {"operation": "constant", "normalization": "gap*D^2/pi^2", "theory": theory_for_surface(kind, deformation), "search": {"minimum": min(row["normalized_gap"] for row in records), "count": len(records), "families": families, "ranges": ranges, "resolution": resolution, "records": records, "refinement": refinement, "certified": False, "interpretation": "Smallest value among the listed computations. This finite search does not determine the global infimum or prove a lower bound for every convex domain; FEM differences also require numerical error assessment."}, "meta": {"geometry": kind, "deformation": deformation if kind == "positive" else 0., "seed": seed, "seconds": time.perf_counter() - start}}


def simulate(params=None):
    params = params or {}
    start = time.perf_counter()
    kind = str(params.get("geometry", "positive"))
    if kind not in ("positive", "flat", "negative"):
        raise ValueError("geometry must be positive, flat or negative")
    deformation = float(params.get("deformation", 0.)) if kind == "positive" else 0.
    if not np.isfinite(deformation) or not -.35 <= deformation <= .6:
        raise ValueError("The deformation must lie between −0.35 and 0.6.")
    if params.get("operation") == "constant":
        return surface_constant(kind, deformation)
    axes = np.array([1., 1., 1. + deformation])
    ellipsoid = kind == "positive" and abs(deformation) > 1e-12
    radius_limit = .35 * axes.min() ** 2 / axes.max() if ellipsoid else None
    maximum_diameter = 2 * radius_limit if ellipsoid else 1.35
    diameter = float(params.get("diameter", 1.4 * radius_limit if ellipsoid else 1.0))
    inradius = float(params["inradius"]) if params.get("inradius") is not None else .28 * diameter
    if not np.isfinite(diameter) or not 0 < diameter <= maximum_diameter + 1e-12:
        raise ValueError(f"For this surface and domain family, choose 0 < D ≤ {maximum_diameter:.6g}. No parameters were changed.")
    if not np.isfinite(inradius) or not 0 < inradius <= diameter / 2 + 1e-12:
        raise ValueError("A convex domain must have 0 < r ≤ D/2. No parameters were changed.")
    resolution = int(params.get("resolution", 32))
    if not 12 <= resolution <= 96:
        raise ValueError("The mesh resolution must lie between 12 and 96.")
    shape = str(params.get("shape", "random"))
    if shape not in ("random", "strip", "lens"):
        raise ValueError("shape must be random, strip or lens")
    seed = int(params.get("seed", 1729))
    domain = build_target(kind, deformation, diameter, inradius, shape, resolution, seed)
    points, triangles, fixed, embedded = (domain[key] for key in ("points", "triangles", "fixed", "embedded"))
    eigenvalues, first, area, residuals = solve(points, triangles, fixed, kind, embedded)
    gap = float(eigenvalues[1] - eigenvalues[0])
    attained_diameter = domain["diameter"]
    normalized = gap * attained_diameter ** 2 / np.pi ** 2
    xyz, surface_triangles = surface_mesh(kind, domain["axes"])
    domain_xyz = display_domain(points, kind, domain["rng"], domain["rotation"], embedded)
    if kind == "positive":
        normal = domain_xyz / domain["axes"] ** 2
        normal /= np.linalg.norm(normal, axis=1)[:, None]
        domain_xyz = domain_xyz + .003 * normal
    first /= max(np.max(first), 1e-15)
    comparison = None
    if bool(params.get("refine", True)):
        cp, ct, cf, ce = domain["remesh"](max(10, int(resolution * .7)))
        cv, _, _, _ = solve(cp, ct, cf, kind, ce)
        coarse_gap = float(cv[1] - cv[0])
        comparison = {"coarse_eigenvalues": cv[:2].tolist(), "coarse_nodes": len(cp), "fine_nodes": len(points), "gap_relative_change": abs(gap - coarse_gap) / max(abs(gap), 1e-15), "normalized_gap_change": abs(gap - coarse_gap) * attained_diameter ** 2 / np.pi ** 2, "certified_error_bound": False}
    warnings = []
    if comparison and comparison["gap_relative_change"] > .05:
        warnings.append("The spectral gap changes by more than 5% between these meshes. Increase the resolution before interpreting it.")
    if domain["shape"] in ("lens", "disk"):
        warnings.append("The target has a curved boundary; finite elements use a polygonal approximation. Refinement measures sensitivity, not a certified error bound.")
    minimum_inradius = radius_limit - math.sqrt(max(radius_limit ** 2 - diameter ** 2 / 4, 0.)) if ellipsoid else 0.
    checks = domain["geometry_checks"]
    return {
        "operation": "domain",
        "eigenvalues": eigenvalues[:2].tolist(), "diameter": attained_diameter, "inradius": inradius,
        "area": area, "gap": gap, "normalized_gap": float(normalized), "product_gap": gap * attained_diameter ** 2,
        "geometry": pack_mesh(xyz, surface_triangles), "domain": pack_mesh(domain_xyz, triangles, first),
        "constraints": {"requested": {"diameter": diameter, "inradius": inradius}, "attained": {"diameter": attained_diameter, "inradius": inradius}, "feasible": True, "diameter_error": abs(attained_diameter - diameter), "inradius_error": 0., "limits": {"maximum_diameter": maximum_diameter, "minimum_inradius": minimum_inradius, "maximum_inradius": diameter / 2, "ellipsoid_ball_radius_limit": radius_limit}, "interpretation": "The inradius is fixed by the construction. The ellipsoid diameter is a converged boundary-sampling and geodesic-shooting estimate; other target diameters are analytic."},
        "meta": {"model": kind, "seed": seed, "requested_diameter": diameter, "requested_inradius": inradius, "aspect": 2 * inradius / diameter, "shape": domain["shape"], "deformation": deformation, "status": "Computed for this convex domain; compare meshes before interpreting the gap", "domain_family": domain["family"], "diameter_method": domain["diameter_method"], "inradius_method": domain["inradius_method"], "metric": {"positive": "Induced metric of the sphere or ellipsoid", "flat": "dx² + dy² on R²/(4Z)²; the torus drawing is not isometric", "negative": "Curvature −1; regular octagon with angles π/4 and opposite sides identified"}[kind], "method": "P1 finite elements on surface triangles" if embedded is not None else "P1 finite elements, exact intrinsic metric and three-point quadrature", "warnings": warnings, "seconds": time.perf_counter() - start},
        "diagnostics": {"nodes": len(points), "triangles": len(triangles), "boundary_nodes": int(np.sum(fixed)), "eigenpair_relative_residuals": residuals[:2], "geodesic_constraint_error": checks.get("surface_constraint_residual"), "geometry": checks, "refinement": comparison, "interpretation": "This calculation concerns one domain. Neither a finite search minimum nor an algebraic eigensolver residual is a certified all-domain lower bound."}
    }


if __name__ == "__main__":
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument("--output", default="gap.json")
    parser.add_argument("--operation", choices=("domain", "constant"), default="domain")
    parser.add_argument("--geometry", choices=("positive", "flat", "negative"), default="positive")
    parser.add_argument("--deformation", type=float, default=0.)
    parser.add_argument("--diameter", type=float)
    parser.add_argument("--inradius", type=float)
    parser.add_argument("--shape", choices=("random", "strip", "lens"), default="random")
    parser.add_argument("--resolution", type=int, default=32)
    parser.add_argument("--seed", type=int, default=1729)
    arguments = {key: value for key, value in vars(parser.parse_args()).items() if value is not None}
    output = arguments.pop("output")
    result = simulate(arguments)
    with open(output, "w", encoding="utf-8") as stream:
        json.dump(result, stream, ensure_ascii=False, separators=(",", ":"), allow_nan=False)
    summary = {"theory": result["theory"], "sample_minimum": result["search"]["minimum"]} if result["operation"] == "constant" else {key: result[key] for key in ("eigenvalues", "diameter", "inradius", "normalized_gap")}
    print(json.dumps(summary, indent=2))

