"""Stopped Short - 2026-11-16, concept "branch", for the gallery at 4j.am.

A digital interpretation of the day's wall-drawing instruction, drawn by
program (Python 3 + Pillow/numpy). It does not depict or simulate a
physical wall, pencil or graphite; it is a drawing that carries the
instruction out literally where the instruction is definite, with the open
parts decided as below (and stated in statement.md):

    Black pencil. From ten chance points on the edges, lines a foot long
    straight in. Each end splits into two lines 6 to 9 tenths as long,
    turned 15 to 45 degrees, one each way. A line that would cross or
    come within 1/16 inch of another stops there and splits no more.

Decided where the instruction is open:
  * the wall is taken as eight feet square, so a foot is 250 px on
    the 2000 px render and 1/16 inch is 1.3 px;
  * the ten edge points are one seeded chance draw (seed 16): a chance
    edge, then a chance place on it;
  * entry lines run straight in, square to their edge;
  * each split makes two children, each a chance 6 to 9 tenths of its
    parent's drawn length, each turned a chance 15 to 45 degrees, the
    first child one way and the second the other;
  * the two lines of a split share their starting point; neither is
    "another" line to the other, and neither is their parent;
  * a line that would cross or come within 1/16 inch of an earlier line
    is drawn up to that point and ends there, blunt, and splits no more
    (the stopping point is found exactly, not by sampling); a line that
    would stop within its first 1/16 inch is not drawn at all; a line
    that meets the wall's edge stops there and splits no more;
  * ends split generation by generation, all ends of one generation
    before the next, so the ten trees grow together and crowd each
    other out;
  * splitting ends when a child would be shorter than 1/16 inch - the
    smallest distance the instruction names; those ends are the piece's
    fine tips;
  * lines are straight black strokes just over a pixel wide - a fine
    pencil line; a stopped end keeps its 1/16-inch clearance, a hair of
    paper between the strokes.

Run: python3 source.py  (writes render-1.png; deterministic for seed 16)
"""

import json
import math
import hashlib
from io import BytesIO

import numpy as np
from PIL import Image, ImageDraw

W = 2000                 # output wall, px (square)
SS = 4                   # supersample factor for the render
PX_PER_FOOT = 250.0      # the wall is taken as eight feet square
FOOT = PX_PER_FOOT
D16 = PX_PER_FOOT / 12.0 / 16.0          # 1/16 inch in px = 2.604
SEED = 16
MAX_DEPTH = 30           # safety bound only; never reached (see facts)
MAX_SEGMENTS = 200000    # safety bound only
TITLE = "Stopped Short"
CONCEPT = "branch"

rng = np.random.default_rng(SEED)

# ---------------------------------------------------------------- geometry

segs = []          # dict(x0,y0,x1,y1,parent,depth,tree,terminal,intended,
                   #      drawn,ratio,angle)
cell = {}
CS = 2.0 * D16     # grid cell side


def cell_key(x, y):
    return (int(x // CS), int(y // CS))


def grid_insert(idx):
    s = segs[idx]
    n = max(1, int(math.hypot(s["x1"] - s["x0"], s["y1"] - s["y0"])
                   / (CS / 2.0)) + 1)
    for k in range(n + 1):
        t = k / n
        cell.setdefault(cell_key(s["x0"] + (s["x1"] - s["x0"]) * t,
                                 s["y0"] + (s["y1"] - s["y0"]) * t),
                        []).append(idx)


def candidates(x0, y0, x1, y1, pad):
    out = set()
    for cx in range(int((min(x0, x1) - pad) // CS),
                    int((max(x0, x1) + pad) // CS) + 1):
        for cy in range(int((min(y0, y1) - pad) // CS),
                        int((max(y0, y1) + pad) // CS) + 1):
            out.update(cell.get((cx, cy), ()))
    return out


def seg_arrays(idxs):
    a = np.array([[segs[j]["x0"], segs[j]["y0"]] for j in idxs])
    b = np.array([[segs[j]["x1"], segs[j]["y1"]] for j in idxs])
    return a, b


def point_set_dist(px, py, a, b, ba, ll):
    """Exact distance from point(s) (px, py) to the segment set."""
    pa = np.stack([np.atleast_1d(px), np.atleast_1d(py)],
                  axis=1)[:, None, :] - a[None, :, :]
    t = np.clip((pa * ba[None, :, :]).sum(axis=2) / ll[None, :], 0.0, 1.0)
    proj = a[None, :, :] + t[:, :, None] * ba[None, :, :]
    d = np.sqrt(((np.stack([np.atleast_1d(px), np.atleast_1d(py)], axis=1)
                  [:, None, :] - proj) ** 2).sum(axis=2))
    return d.min(axis=1)


def first_proximity_hit(x, y, dx, dy, length, exclude):
    """Exact first distance along the ray P(t) = (x, y) + t*(dx, dy)
    where it would come within 1/16 inch of an earlier line (excluding
    `exclude`), or None. Analytic: for each earlier segment the set of t
    within 1/16 inch of it is an interval, found exactly from the two
    endpoint discs (quadratic roots) and the strip around the segment's
    interior (linear crossing, valid while the perpendicular foot falls
    on the segment). A crossing is covered: entering a disc happens
    before reaching the line."""
    cand = candidates(x, y, x + dx * length, y + dy * length,
                      D16 + CS) - set(exclude)
    if not cand:
        return None
    a, b = seg_arrays(list(cand))
    p0 = np.array([x, y])
    d = np.array([dx, dy])
    best = math.inf

    def disc_hits(e):
        """First t entering the D16-disc around point e, or inf."""
        w = p0 - e
        bq = w @ d
        cq = w @ w - D16 * D16
        if cq <= 0:
            return 0.0                    # starts inside the disc
        disc = bq * bq - cq
        if disc < 0:
            return math.inf
        t1 = -bq - math.sqrt(disc)
        return t1 if t1 >= 0 else 0.0     # t1<0<t2: inside at t=0

    for j in range(len(a)):
        t = min(disc_hits(a[j]), disc_hits(b[j]))
        ba = b[j] - a[j]
        L = math.hypot(ba[0], ba[1])
        if L > 1e-12:
            u = ba / L
            cr0 = (p0[0] - a[j][0]) * u[1] - (p0[1] - a[j][1]) * u[0]
            crd = d[0] * u[1] - d[1] * u[0]
            s0 = (p0 - a[j]) @ u
            du = d @ u
            if abs(crd) > 1e-12:
                if abs(cr0) < D16 and 0.0 <= s0 <= L:
                    t = min(t, 0.0)       # starts within the strip
                for sgn, entering in ((D16, crd < 0), (-D16, crd > 0)):
                    tr = (sgn - cr0) / crd
                    if tr >= 0 and entering:
                        sr = s0 + tr * du
                        if 0.0 <= sr <= L:
                            t = min(t, tr)
            elif abs(cr0) < D16 and abs(du) > 1e-12:
                # parallel and within D16 of the line: entry is where
                # the abreast parameter s(t) enters [0, L]
                srt = sorted(((0.0 - s0) / du, (L - s0) / du))
                lo, hi = max(srt[0], 0.0), srt[1]
                if lo <= hi:
                    t = min(t, lo)
        if t < best:
            best = t
    if best is math.inf or best > length:
        return None
    return best


def edge_stop(x, y, dx, dy, length):
    """Distance along the ray where it first reaches the wall's edge,
    or None if it stays inside for `length`."""
    t = math.inf
    if dx > 0:
        t = min(t, (W - x) / dx)
    elif dx < 0:
        t = min(t, -x / dx)
    if dy > 0:
        t = min(t, (W - y) / dy)
    elif dy < 0:
        t = min(t, -y / dy)
    if t is math.inf or t > length:
        return None
    return t


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


def seg_seg_dist_exact(p1, p2, p3, p4):
    """Exact minimum distance between two segments (0 if they cross)."""
    d1 = orient(p3, p4, p1)
    d2 = orient(p3, p4, p2)
    d3 = orient(p1, p2, p3)
    d4 = orient(p1, p2, p4)
    if ((d1 > 0) != (d2 > 0)) and ((d3 > 0) != (d4 > 0)):
        return 0.0

    def pt_seg(p, a, b):
        ax, ay = a
        bx, by = b
        dx, dy = bx - ax, by - ay
        ll = dx * dx + dy * dy
        if ll == 0:
            return math.hypot(p[0] - ax, p[1] - ay)
        t = max(0.0, min(1.0, ((p[0] - ax) * dx + (p[1] - ay) * dy) / ll))
        return math.hypot(p[0] - (ax + t * dx), p[1] - (ay + t * dy))

    return min(pt_seg(p1, p3, p4), pt_seg(p2, p3, p4),
               pt_seg(p3, p1, p2), pt_seg(p4, p1, p2))


def grow(x, y, theta, length, parent, sibling, depth, tree, ratio, angle):
    """Draw one line from (x, y). Returns its index, or None if it is not
    drawn (stops within its first 1/16 inch, or shorter than 1/16 inch).
    Splitting is driven generation by generation in `grow_forest`."""
    if len(segs) >= MAX_SEGMENTS or length < D16:
        return None
    dx, dy = math.cos(theta), math.sin(theta)
    exclude = tuple(i for i in (parent, sibling) if i is not None)
    t_hit = first_proximity_hit(x, y, dx, dy, length, exclude)
    t_edge = edge_stop(x, y, dx, dy, length)
    if t_hit is not None and t_hit < D16:
        return None                       # stops at birth: not drawn
    if t_hit is not None and (t_edge is None or t_hit <= t_edge) \
            and t_hit < length:
        drawn, terminal = t_hit, "proximity"
    elif t_edge is not None and t_edge < length:
        drawn, terminal = max(t_edge, 0.0), "edge"
    else:
        drawn, terminal = length, "open"
    if drawn < D16:
        return None            # stops within its first 1/16 inch: not drawn
    idx = len(segs)
    segs.append(dict(x0=x, y0=y, x1=x + dx * drawn, y1=y + dy * drawn,
                     parent=parent, depth=depth, tree=tree,
                     terminal=terminal, intended=length, drawn=drawn,
                     ratio=ratio, angle=angle))
    grid_insert(idx)
    return idx


def grow_forest():
    """Ten chance points on the edges, one foot straight in; then every
    open end splits, generation by generation, all ends of one
    generation before the next."""
    EDGES = ["top", "right", "bottom", "left"]
    INWARD = {"top": math.pi / 2, "bottom": -math.pi / 2,
              "left": 0.0, "right": math.pi}
    generation = []
    for i in range(10):
        e = EDGES[int(rng.integers(0, 4))]
        p = 30.0 + (W - 60.0) * rng.random()
        if e == "top":
            x, y = p, 0.0
        elif e == "bottom":
            x, y = p, float(W)
        elif e == "left":
            x, y = 0.0, p
        else:
            x, y = float(W), p
        entry_points.append((e, round(x, 1), round(y, 1)))
        idx = grow(x, y, INWARD[e], FOOT, None, None, 0, i, None, None)
        if idx is not None:
            generation.append(idx)
    depth = 1
    while generation and depth <= MAX_DEPTH:
        nxt = []
        for idx in generation:
            s = segs[idx]
            if s["terminal"] != "open":
                continue
            ex, ey, theta, drawn = s["x1"], s["y1"], 0.0, s["drawn"]
            theta = math.atan2(s["y1"] - s["y0"], s["x1"] - s["x0"])
            r1 = 0.6 + 0.3 * rng.random()
            r2 = 0.6 + 0.3 * rng.random()
            a1 = math.radians(15.0 + 30.0 * rng.random())
            a2 = math.radians(15.0 + 30.0 * rng.random())
            c1 = grow(ex, ey, theta + a1, drawn * r1, idx, None,
                      depth, s["tree"], r1, math.degrees(a1))
            c2 = grow(ex, ey, theta - a2, drawn * r2, idx, c1,
                      depth, s["tree"], r2, math.degrees(a2))
            if c1 is None and c2 is None:
                s["terminal"] = "tip"     # both children not drawn
            for c in (c1, c2):
                if c is not None:
                    nxt.append(c)
        generation = nxt
        depth += 1


entry_points = []
grow_forest()

# ---------------------------------------------------------------- rendering

img = Image.new("L", (W * SS, W * SS), 250)
dr = ImageDraw.Draw(img)
for s in segs:
    gray = int(24 + 20 * rng.random())   # pressure varies line to line
    dr.line([(s["x0"] * SS, s["y0"] * SS), (s["x1"] * SS, s["y1"] * SS)],
            fill=gray, width=int(round(1.2 * SS)))
img = img.resize((W, W), Image.LANCZOS).convert("RGB")
buf = BytesIO()
img.save(buf, format="PNG")
png = buf.getvalue()
with open("render-1.png", "wb") as f:
    f.write(png)

# ---------------------------------------------------------------- checks
# Exact segment-to-segment distance for every pair that does not share an
# end point: no such pair may come within 1/16 inch.

endpoint_key = {}
for i, s in enumerate(segs):
    endpoint_key.setdefault((round(s["x0"], 6), round(s["y0"], 6)),
                            set()).add(i)
    endpoint_key.setdefault((round(s["x1"], 6), round(s["y1"], 6)),
                            set()).add(i)


def share_endpoint(i, j):
    si = ((round(segs[i]["x0"], 6), round(segs[i]["y0"], 6)),
          (round(segs[i]["x1"], 6), round(segs[i]["y1"], 6)))
    sj = ((round(segs[j]["x0"], 6), round(segs[j]["y0"], 6)),
          (round(segs[j]["x1"], 6), round(segs[j]["y1"], 6)))
    return bool(set(si) & set(sj))


min_gap = math.inf
min_pair = None
for i, s in enumerate(segs):
    for j in candidates(s["x0"], s["y0"], s["x1"], s["y1"], D16 + CS):
        if j <= i or share_endpoint(i, j):
            continue
        t = seg_seg_dist_exact(
            (s["x0"], s["y0"]), (s["x1"], s["y1"]),
            (segs[j]["x0"], segs[j]["y0"]), (segs[j]["x1"], segs[j]["y1"]))
        if t < min_gap:
            min_gap = t
            min_pair = (i, j)

# Split ratios and angles within their ranges.
ratios = [s["ratio"] for s in segs if s["ratio"] is not None]
angles = [s["angle"] for s in segs if s["angle"] is not None]

facts = dict(
    title=TITLE, concept=CONCEPT, seed=SEED,
    wall_px=W, wall_feet=W / FOOT, foot_px=FOOT, d16_px=round(D16, 4),
    entry_points=entry_points,
    segments_drawn=len(segs),
    terminal_counts={k: sum(1 for s in segs if s["terminal"] == k)
                     for k in ("proximity", "edge", "tip", "cap")},
    per_tree_segments=[sum(1 for s in segs if s["tree"] == t)
                       for t in range(10)],
    max_depth_reached=max(s["depth"] for s in segs),
    total_ink_px=round(sum(s["drawn"] for s in segs), 1),
    longest_line_px=round(max(s["drawn"] for s in segs), 1),
    shortest_line_px=round(min(s["drawn"] for s in segs), 2),
    ratio_min=round(min(ratios), 4), ratio_max=round(max(ratios), 4),
    angle_min=round(min(angles), 3), angle_max=round(max(angles), 3),
    min_gap_px=round(min_gap, 3), min_gap_rule_px=round(D16, 3),
    min_gap_pair=min_pair,
    render_sha256=hashlib.sha256(png).hexdigest(),
)
with open("facts.json", "w") as f:
    json.dump(facts, f, indent=2)
print(json.dumps(facts, indent=2))
