Skip to content

The VS Code of video editing, built for agents.

TypeScript
32.1 KB
Raw Blame
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

// Vector paths: a `<path>`'s `d` as cubic segments, and what is done with
// them — reading and writing SVG path data, morphing one path into another
// (a `d` keyframe track), trimming (`trimStart`/`trimEnd`/`trimOffset`),
// bounds and hit testing. The renderer, the hit test and the pen tool all
// read the same numbers.

/**
 * One subpath with every segment a cubic. `points` holds the start anchor
 * and then, per segment, its two control points and its end anchor:
 * `[x0, y0, c1x, c1y, c2x, c2y, x1, y1, ...]`. A straight segment has its
 * control points on its anchors. A closed subpath's last segment ends back on
 * its start, so the closing segment is one like the others (it can curve)
 * and every vertex is an anchor once.
 */
export interface Subpath {
	closed: boolean;
	points: number[];
}

export interface PathGeometry {
	subpaths: Subpath[];
}

/** A path as read from its `d`: what parsed, and why the rest did not. */
export interface ParsedPath {
	geometry: PathGeometry;
	/** Null when the whole string parsed; otherwise the geometry is what came before the error, as SVG renders it. */
	error: string | null;
}

/** Where a `d` is drawn from: SVG's `viewBox`, stretched onto the box. */
export interface ViewBoxRect {
	x: number;
	y: number;
	width: number;
	height: number;
}

/** Maps a `d`'s coordinates into the box: `x * sx + tx`, `y * sy + ty`. */
export interface PathTransform {
	sx: number;
	sy: number;
	tx: number;
	ty: number;
}

const EPSILON = 1e-9;

export const EMPTY_PATH: PathGeometry = { subpaths: [] };

export function segmentCount(subpath: Subpath): number {
	return (subpath.points.length - 2) / 6;
}

/** How many vertices a subpath has: a closed one's last anchor is its first. */
export function vertexCount(subpath: Subpath): number {
	const segments = segmentCount(subpath);
	return subpath.closed && segments > 0 ? segments : segments + 1;
}

// ── Parsing ─────────────────────────────────────────────────

const PARAMS: Record<string, number> = { m: 2, l: 2, h: 1, v: 1, c: 6, s: 4, q: 4, t: 2, a: 7, z: 0 };
const NUMBER = /[+-]?(?:\d+\.?\d*|\.\d+)(?:[eE][+-]?\d+)?/y;
const SEPARATORS = /[\s,]*/y;

/**
 * Reads SVG path data into cubic subpaths: every command, absolute and
 * relative, implicit repeats, `H`/`V`, quadratics and arcs (elevated and
 * approximated to cubics). Like SVG, a malformed string keeps what came
 * before the error.
 */
export function parsePath(d: string): ParsedPath {
	const subpaths: Subpath[] = [];
	let current: Subpath | null = null;
	let x = 0, y = 0; // current point
	let startX = 0, startY = 0; // current subpath's start
	let controlX = 0, controlY = 0; // last control point, for S/T
	let previous = ''; // last command, lowercase
	let command = '';
	let i = 0;
	let error: string | null = null;

	const skip = () => {
		SEPARATORS.lastIndex = i;
		SEPARATORS.exec(d);
		i = SEPARATORS.lastIndex;
	};

	const number = (): number | null => {
		skip();
		NUMBER.lastIndex = i;
		const match = NUMBER.exec(d);
		if (!match) return null;
		i = NUMBER.lastIndex;
		return Number(match[0]);
	};

	// Arc flags are a single digit and may run into what follows ("a1 1 0 01 1 1").
	const flag = (): number | null => {
		skip();
		const char = d[i];
		if (char !== '0' && char !== '1') return null;
		i++;
		return char === '1' ? 1 : 0;
	};

	const moveTo = (px: number, py: number) => {
		current = { closed: false, points: [px, py] };
		subpaths.push(current);
		x = startX = px;
		y = startY = py;
	};

	// A drawing command after a close starts a new subpath where the last one began.
	const open = (): Subpath => {
		if (current === null) moveTo(x, y);
		return current!;
	};

	const curveTo = (c1x: number, c1y: number, c2x: number, c2y: number, px: number, py: number) => {
		open().points.push(c1x, c1y, c2x, c2y, px, py);
		x = px;
		y = py;
	};

	const lineTo = (px: number, py: number) => curveTo(x, y, px, py, px, py);

	while (true) {
		skip();
		if (i >= d.length) break;

		const char = d[i]!;
		if (char.toLowerCase() in PARAMS) {
			command = char;
			i++;
		} else if (command === '' || command === 'z' || command === 'Z') {
			error = `Expected a command at ${i}, found "${char}"`;
			break;
		}

		const lower = command.toLowerCase();
		const relative = command !== command.toUpperCase();
		const args: number[] = [];
		for (let p = 0; p < PARAMS[lower]!; p++) {
			const value = lower === 'a' && (p === 3 || p === 4) ? flag() : number();
			if (value === null) {
				error = `Expected ${PARAMS[lower]} parameters for "${command}" at ${i}`;
				break;
			}
			args.push(value);
		}
		if (error !== null) break;

		const ox = relative ? x : 0;
		const oy = relative ? y : 0;

		switch (lower) {
			case 'm':
				moveTo(args[0]! + ox, args[1]! + oy);
				// Pairs after a moveto are linetos.
				command = relative ? 'l' : 'L';
				break;
			case 'l':
				lineTo(args[0]! + ox, args[1]! + oy);
				break;
			case 'h':
				lineTo(args[0]! + ox, y);
				break;
			case 'v':
				lineTo(x, args[0]! + oy);
				break;
			case 'c':
				curveTo(args[0]! + ox, args[1]! + oy, args[2]! + ox, args[3]! + oy, args[4]! + ox, args[5]! + oy);
				controlX = args[2]! + ox;
				controlY = args[3]! + oy;
				break;
			case 's': {
				const reflect = previous === 'c' || previous === 's';
				const c1x = reflect ? 2 * x - controlX : x;
				const c1y = reflect ? 2 * y - controlY : y;
				controlX = args[0]! + ox;
				controlY = args[1]! + oy;
				curveTo(c1x, c1y, controlX, controlY, args[2]! + ox, args[3]! + oy);
				break;
			}
			case 'q': {
				const qx = args[0]! + ox;
				const qy = args[1]! + oy;
				quadTo(qx, qy, args[2]! + ox, args[3]! + oy);
				break;
			}
			case 't': {
				const reflect = previous === 'q' || previous === 't';
				const qx = reflect ? 2 * x - controlX : x;
				const qy = reflect ? 2 * y - controlY : y;
				quadTo(qx, qy, args[0]! + ox, args[1]! + oy);
				break;
			}
			case 'a': {
				const ex = args[5]! + ox;
				const ey = args[6]! + oy;
				arcToCubics(x, y, args[0]!, args[1]!, args[2]!, args[3] === 1, args[4] === 1, ex, ey, curveTo);
				// A degenerate arc draws nothing but still moves the pen.
				x = ex;
				y = ey;
				break;
			}
			case 'z':
				if (current !== null) close(current, startX, startY);
				current = null;
				x = startX;
				y = startY;
				break;
		}
		previous = lower;
	}

	return { geometry: { subpaths }, error };

	function quadTo(qx: number, qy: number, px: number, py: number) {
		curveTo(
			x + (2 / 3) * (qx - x), y + (2 / 3) * (qy - y),
			px + (2 / 3) * (qx - px), py + (2 / 3) * (qy - py),
			px, py,
		);
		controlX = qx;
		controlY = qy;
	}
}

/**
 * Closes `subpath` back to its start: with a straight segment, unless its
 * last segment already ends there, in which case that one is the closing
 * segment — so `L 0 0 Z` and `Z` alone are the same outline.
 */
function close(subpath: Subpath, startX: number, startY: number): void {
	const { points } = subpath;
	const n = points.length;
	const ends = n > 2 && near(points[n - 2]!, startX) && near(points[n - 1]!, startY);
	if (n > 2 && !ends) {
		points.push(points[n - 2]!, points[n - 1]!, startX, startY, startX, startY);
	} else if (ends) {
		// Exactly on the start, so the seam has no gap to stroke over.
		points[n - 2] = startX;
		points[n - 1] = startY;
	}
	subpath.closed = true;
}

function near(a: number, b: number): boolean {
	return Math.abs(a - b) <= 1e-6;
}

/**
 * An SVG elliptical arc from (x1, y1) to (x2, y2) as cubics of at most a
 * quarter turn each (SVG 1.1 implementation notes, F.6.5–F.6.6).
 */
function arcToCubics(
	x1: number, y1: number,
	rx: number, ry: number, rotation: number,
	largeArc: boolean, sweep: boolean,
	x2: number, y2: number,
	curveTo: (c1x: number, c1y: number, c2x: number, c2y: number, x: number, y: number) => void,
): void {
	if (x1 === x2 && y1 === y2) return;
	rx = Math.abs(rx);
	ry = Math.abs(ry);
	if (rx === 0 || ry === 0) {
		curveTo(x1, y1, x2, y2, x2, y2);
		return;
	}

	const phi = (rotation * Math.PI) / 180;
	const cos = Math.cos(phi);
	const sin = Math.sin(phi);
	const dx = (x1 - x2) / 2;
	const dy = (y1 - y2) / 2;
	const x1p = cos * dx + sin * dy;
	const y1p = -sin * dx + cos * dy;

	// Radii too small for the endpoints grow until they just fit.
	const lambda = (x1p * x1p) / (rx * rx) + (y1p * y1p) / (ry * ry);
	if (lambda > 1) {
		rx *= Math.sqrt(lambda);
		ry *= Math.sqrt(lambda);
	}

	const numerator = rx * rx * ry * ry - rx * rx * y1p * y1p - ry * ry * x1p * x1p;
	const denominator = rx * rx * y1p * y1p + ry * ry * x1p * x1p;
	const coefficient = (largeArc !== sweep ? 1 : -1) * Math.sqrt(Math.max(0, numerator / denominator));
	const cxp = (coefficient * rx * y1p) / ry;
	const cyp = (-coefficient * ry * x1p) / rx;
	const cx = cos * cxp - sin * cyp + (x1 + x2) / 2;
	const cy = sin * cxp + cos * cyp + (y1 + y2) / 2;

	const angle = (ux: number, uy: number, vx: number, vy: number) => Math.atan2(ux * vy - uy * vx, ux * vx + uy * vy);
	const theta = angle(1, 0, (x1p - cxp) / rx, (y1p - cyp) / ry);
	let delta = angle((x1p - cxp) / rx, (y1p - cyp) / ry, (-x1p - cxp) / rx, (-y1p - cyp) / ry);
	if (!sweep && delta > 0) delta -= 2 * Math.PI;
	if (sweep && delta < 0) delta += 2 * Math.PI;

	const count = Math.max(1, Math.ceil(Math.abs(delta) / (Math.PI / 2) - 1e-9));
	const step = delta / count;
	const k = (4 / 3) * Math.tan(step / 4);
	const map = (ux: number, uy: number): [number, number] => [
		cos * rx * ux - sin * ry * uy + cx,
		sin * rx * ux + cos * ry * uy + cy,
	];

	for (let s = 0; s < count; s++) {
		const a = theta + s * step;
		const b = a + step;
		const [c1x, c1y] = map(Math.cos(a) - k * Math.sin(a), Math.sin(a) + k * Math.cos(a));
		const [c2x, c2y] = map(Math.cos(b) + k * Math.sin(b), Math.sin(b) - k * Math.cos(b));
		const [ex, ey] = s === count - 1 ? [x2, y2] : map(Math.cos(b), Math.sin(b));
		curveTo(c1x, c1y, c2x, c2y, ex, ey);
	}
}

// ── Writing ─────────────────────────────────────────────────

/** A number as path data spells it: rounded to `digits` places, no `-0`. */
function formatNumber(value: number, digits: number): string {
	const scale = 10 ** digits;
	const rounded = Math.round(value * scale) / scale;
	return Object.is(rounded, -0) ? '0' : String(rounded);
}

/**
 * The path as SVG path data in absolute `M`/`L`/`C`/`Z`: a segment whose
 * control points sit on its anchors is a line, and a closed subpath's
 * straight closing segment is the `Z` alone.
 */
export function formatPath(geometry: PathGeometry, digits = 2): string {
	const f = (value: number) => formatNumber(value, digits);
	const parts: string[] = [];

	for (const { closed, points } of geometry.subpaths) {
		parts.push(`M${f(points[0]!)} ${f(points[1]!)}`);
		const segments = (points.length - 2) / 6;
		for (let s = 0; s < segments; s++) {
			const o = 2 + s * 6;
			const line = isLine(points, o, f);
			if (closed && s === segments - 1 && line) break;
			parts.push(line
				? `L${f(points[o + 4]!)} ${f(points[o + 5]!)}`
				: `C${f(points[o]!)} ${f(points[o + 1]!)} ${f(points[o + 2]!)} ${f(points[o + 3]!)} ${f(points[o + 4]!)} ${f(points[o + 5]!)}`);
		}
		if (closed) parts.push('Z');
	}

	return parts.join(' ');
}

/** Whether the segment at `o` is straight as written: its controls round onto its anchors. */
function isLine(points: number[], o: number, f: (value: number) => string): boolean {
	return f(points[o]!) === f(points[o - 2]!) && f(points[o + 1]!) === f(points[o - 1]!)
		&& f(points[o + 2]!) === f(points[o + 4]!) && f(points[o + 3]!) === f(points[o + 5]!);
}

// ── Mapping ─────────────────────────────────────────────────

/**
 * How a `d` drawn in `viewBox` lands in a `width` × `height` box: stretched
 * to fill it on each axis (SVG's `preserveAspectRatio="none"`). Without a
 * viewBox the coordinates are the box's own.
 */
export function viewBoxTransform(viewBox: ViewBoxRect | null, width: number, height: number): PathTransform {
	if (viewBox === null || viewBox.width <= 0 || viewBox.height <= 0) {
		return { sx: 1, sy: 1, tx: 0, ty: 0 };
	}
	const sx = width / viewBox.width;
	const sy = height / viewBox.height;
	return { sx, sy, tx: -viewBox.x * sx, ty: -viewBox.y * sy };
}

/** The path with every coordinate mapped by `transform`. */
export function transformPath(geometry: PathGeometry, { sx, sy, tx, ty }: PathTransform): PathGeometry {
	return {
		subpaths: geometry.subpaths.map(({ closed, points }) => ({
			closed,
			points: points.map((value, index) => (index % 2 === 0 ? value * sx + tx : value * sy + ty)),
		})),
	};
}

/**
 * Traces the path onto `path` (the caller begins it), its coordinates
 * mapped by `transform` on the way so a stretched path needs no copy.
 */
export function tracePath(path: CanvasPath, geometry: PathGeometry, transform?: PathTransform): void {
	const { sx, sy, tx, ty } = transform ?? { sx: 1, sy: 1, tx: 0, ty: 0 };
	for (const { closed, points } of geometry.subpaths) {
		path.moveTo(points[0]! * sx + tx, points[1]! * sy + ty);
		for (let o = 2; o < points.length; o += 6) {
			const straight = points[o] === points[o - 2] && points[o + 1] === points[o - 1]
				&& points[o + 2] === points[o + 4] && points[o + 3] === points[o + 5];
			if (straight) {
				path.lineTo(points[o + 4]! * sx + tx, points[o + 5]! * sy + ty);
			} else {
				path.bezierCurveTo(
					points[o]! * sx + tx, points[o + 1]! * sy + ty,
					points[o + 2]! * sx + tx, points[o + 3]! * sy + ty,
					points[o + 4]! * sx + tx, points[o + 5]! * sy + ty,
				);
			}
		}
		if (closed) path.closePath();
	}
}

// ── Bounds ──────────────────────────────────────────────────

export interface PathBounds {
	minX: number;
	minY: number;
	maxX: number;
	maxY: number;
}

/** The tight bounds of the path's outline (curve extrema included), or null for an empty path. */
export function pathBounds(geometry: PathGeometry): PathBounds | null {
	let minX = Infinity, minY = Infinity, maxX = -Infinity, maxY = -Infinity;
	const include = (x: number, y: number) => {
		if (x < minX) minX = x;
		if (x > maxX) maxX = x;
		if (y < minY) minY = y;
		if (y > maxY) maxY = y;
	};

	for (const { points } of geometry.subpaths) {
		include(points[0]!, points[1]!);
		for (let o = 2; o < points.length; o += 6) {
			const x0 = points[o - 2]!, y0 = points[o - 1]!;
			const x3 = points[o + 4]!, y3 = points[o + 5]!;
			include(x3, y3);
			for (const t of cubicExtrema(x0, points[o]!, points[o + 2]!, x3)) {
				include(cubicAt(x0, points[o]!, points[o + 2]!, x3, t), cubicAt(y0, points[o + 1]!, points[o + 3]!, y3, t));
			}
			for (const t of cubicExtrema(y0, points[o + 1]!, points[o + 3]!, y3)) {
				include(cubicAt(x0, points[o]!, points[o + 2]!, x3, t), cubicAt(y0, points[o + 1]!, points[o + 3]!, y3, t));
			}
		}
	}

	return minX === Infinity ? null : { minX, minY, maxX, maxY };
}

/** The union of several paths' bounds, or null when all are empty. */
export function unionPathBounds(geometries: Iterable<PathGeometry>): PathBounds | null {
	let union: PathBounds | null = null;
	for (const geometry of geometries) {
		const bounds = pathBounds(geometry);
		if (bounds === null) continue;
		union = union === null ? bounds : {
			minX: Math.min(union.minX, bounds.minX),
			minY: Math.min(union.minY, bounds.minY),
			maxX: Math.max(union.maxX, bounds.maxX),
			maxY: Math.max(union.maxY, bounds.maxY),
		};
	}
	return union;
}

function cubicAt(p0: number, p1: number, p2: number, p3: number, t: number): number {
	const u = 1 - t;
	return u * u * u * p0 + 3 * u * u * t * p1 + 3 * u * t * t * p2 + t * t * t * p3;
}

/** The parameters in (0, 1) where one axis of a cubic turns. */
function cubicExtrema(p0: number, p1: number, p2: number, p3: number): number[] {
	const a = -p0 + 3 * p1 - 3 * p2 + p3;
	const b = 2 * (p0 - 2 * p1 + p2);
	const c = p1 - p0;
	const roots: number[] = [];
	if (Math.abs(a) < EPSILON) {
		if (Math.abs(b) > EPSILON) roots.push(-c / b);
	} else {
		const discriminant = b * b - 4 * a * c;
		if (discriminant >= 0) {
			const root = Math.sqrt(discriminant);
			roots.push((-b + root) / (2 * a), (-b - root) / (2 * a));
		}
	}
	return roots.filter((t) => t > 0 && t < 1);
}

// ── Splitting ───────────────────────────────────────────────

type Cubic = [x0: number, y0: number, c1x: number, c1y: number, c2x: number, c2y: number, x3: number, y3: number];

/** The segment at index `s` of `points`, start anchor included. */
function cubicOf(points: number[], s: number): Cubic {
	const o = 2 + s * 6;
	return [points[o - 2]!, points[o - 1]!, points[o]!, points[o + 1]!, points[o + 2]!, points[o + 3]!, points[o + 4]!, points[o + 5]!];
}

/**
 * Whether a segment is straight as stored: its control points on its
 * anchors. Such a segment is parameterized linearly here (its point at `t` is
 * `t` of the way along), so it splits, trims and morphs into straight pieces.
 */
function isStraight(cubic: Cubic): boolean {
	return cubic[2] === cubic[0] && cubic[3] === cubic[1] && cubic[4] === cubic[6] && cubic[5] === cubic[7];
}

/** The point at `t` along a segment. */
function pointOn(cubic: Cubic, t: number): [number, number] {
	if (isStraight(cubic)) {
		return [cubic[0] + (cubic[6] - cubic[0]) * t, cubic[1] + (cubic[7] - cubic[1]) * t];
	}
	return [cubicAt(cubic[0], cubic[2], cubic[4], cubic[6], t), cubicAt(cubic[1], cubic[3], cubic[5], cubic[7], t)];
}

/**
 * A segment split at `t`: the part before and the part after. A curve
 * splits by de Casteljau, a straight segment into two straight ones.
 */
export function splitCubic(cubic: Cubic, t: number): [Cubic, Cubic] {
	if (isStraight(cubic)) {
		const [mx, my] = pointOn(cubic, t);
		return [
			[cubic[0], cubic[1], cubic[0], cubic[1], mx, my, mx, my],
			[mx, my, mx, my, cubic[6], cubic[7], cubic[6], cubic[7]],
		];
	}
	const [x0, y0, x1, y1, x2, y2, x3, y3] = cubic;
	const lerp = (a: number, b: number) => a + (b - a) * t;
	const ax = lerp(x0, x1), ay = lerp(y0, y1);
	const bx = lerp(x1, x2), by = lerp(y1, y2);
	const cx = lerp(x2, x3), cy = lerp(y2, y3);
	const dx = lerp(ax, bx), dy = lerp(ay, by);
	const ex = lerp(bx, cx), ey = lerp(by, cy);
	const fx = lerp(dx, ex), fy = lerp(dy, ey);
	return [[x0, y0, ax, ay, dx, dy, fx, fy], [fx, fy, ex, ey, cx, cy, x3, y3]];
}

/** The part of a cubic between `t0` and `t1`. */
function sliceCubic(cubic: Cubic, t0: number, t1: number): Cubic {
	const [head] = t1 >= 1 ? [cubic] : splitCubic(cubic, t1);
	if (t0 <= 0) return head;
	return splitCubic(head, t1 <= 0 ? 0 : t0 / t1)[1];
}

/** Rough length of a segment, enough to rank segments by: its control polygon. */
function hullLength(cubic: Cubic): number {
	const [x0, y0, x1, y1, x2, y2, x3, y3] = cubic;
	return Math.hypot(x1 - x0, y1 - y0) + Math.hypot(x2 - x1, y2 - y1) + Math.hypot(x3 - x2, y3 - y2);
}

/**
 * The subpath with segment `s` split in two at `t`: a vertex inserted on the
 * outline without changing it. Its vertices after the split are one further on.
 */
export function splitSegment(subpath: Subpath, s: number, t: number): Subpath {
	if (s < 0 || s >= segmentCount(subpath)) return subpath;
	const [head, tail] = splitCubic(cubicOf(subpath.points, s), t);
	const points = subpath.points.slice();
	const o = 2 + s * 6;
	points.splice(o, 6, ...head.slice(2), ...tail.slice(2));
	return { closed: subpath.closed, points };
}

/**
 * The subpath with vertex `v` taken out: an end vertex takes its one segment
 * with it, any other merges its two segments into one that keeps their outer
 * control points. Unchanged if it would leave no segment at all.
 */
export function removeVertex(subpath: Subpath, v: number): Subpath {
	const segments = segmentCount(subpath);
	const vertices = vertexCount(subpath);
	if (v < 0 || v >= vertices || vertices <= 2) return subpath;
	const { points } = subpath;

	if (!subpath.closed) {
		if (v === 0) return { closed: false, points: points.slice(6) };
		if (v === vertices - 1) return { closed: false, points: points.slice(0, -6) };
		// Segment v-1 runs into the vertex, segment v out of it.
		const into = 2 + (v - 1) * 6;
		const merged = [points[into]!, points[into + 1]!, points[into + 8]!, points[into + 9]!, points[into + 10]!, points[into + 11]!];
		const next = points.slice();
		next.splice(into, 12, ...merged);
		return { closed: false, points: next };
	}

	// Closed: the segment into v and the one out of it, wrapping round.
	const into = (v - 1 + segments) % segments;
	const out = v;
	const a = cubicOf(points, into);
	const b = cubicOf(points, out);
	const merged: Cubic = [a[0], a[1], a[2], a[3], b[4], b[5], b[6], b[7]];
	const cubics: Cubic[] = [];
	for (let s = 0; s < segments; s++) {
		if (s === out) continue;
		cubics.push(s === into ? merged : cubicOf(points, s));
	}
	// Taking out the first vertex leaves the merged segment last, so the next
	// vertex is first.
	return fromCubics(cubics, true);
}

function fromCubics(cubics: Cubic[], closed: boolean): Subpath {
	const points = [cubics[0]![0], cubics[0]![1]];
	for (const cubic of cubics) points.push(...cubic.slice(2));
	return { closed, points };
}

// ── Morphing ────────────────────────────────────────────────

/**
 * `subpath` with as many segments as `count`: the longest segment is split in
 * half, again and again, so the outline is the same and the new vertices
 * land where there is the most room. A subpath with no segment at all (a
 * lone point) grows segments of no length.
 */
function subdivide(subpath: Subpath, count: number): Subpath {
	let segments = segmentCount(subpath);
	if (segments >= count) return subpath;
	if (segments === 0) {
		const [x, y] = subpath.points as [number, number];
		const points = [x, y];
		for (let s = 0; s < count; s++) points.push(x, y, x, y, x, y);
		return { closed: subpath.closed, points };
	}

	const cubics: Cubic[] = [];
	for (let s = 0; s < segments; s++) cubics.push(cubicOf(subpath.points, s));
	const lengths = cubics.map(hullLength);
	while (segments < count) {
		let longest = 0;
		for (let s = 1; s < lengths.length; s++) if (lengths[s]! > lengths[longest]!) longest = s;
		const halves = splitCubic(cubics[longest]!, 0.5);
		cubics.splice(longest, 1, ...halves);
		lengths.splice(longest, 1, hullLength(halves[0]), hullLength(halves[1]));
		segments++;
	}
	return fromCubics(cubics, subpath.closed);
}

/** Two paths made the same shape of data, so they lerp number for number; null when they cannot be. */
type MatchedPair = [PathGeometry, PathGeometry];

const matches = new WeakMap<PathGeometry, WeakMap<PathGeometry, MatchedPair | null>>();

/**
 * `from` and `to` with the same subpaths, the same open/closed flags and the
 * same number of segments in each, the shorter of each pair subdivided to the
 * longer. Null when they differ in subpath count or in which are closed:
 * those hold instead of morphing. Paths are parsed once and never changed,
 * so a pair is matched once and kept.
 */
function matchPaths(from: PathGeometry, to: PathGeometry): MatchedPair | null {
	let byTarget = matches.get(from);
	if (byTarget === undefined) {
		byTarget = new WeakMap();
		matches.set(from, byTarget);
	}
	const cached = byTarget.get(to);
	if (cached !== undefined) return cached;

	let pair: MatchedPair | null = null;
	if (from.subpaths.length === to.subpaths.length
		&& from.subpaths.every((subpath, index) => subpath.closed === to.subpaths[index]!.closed)) {
		const a: Subpath[] = [];
		const b: Subpath[] = [];
		from.subpaths.forEach((subpath, index) => {
			const other = to.subpaths[index]!;
			const count = Math.max(segmentCount(subpath), segmentCount(other));
			a.push(subdivide(subpath, count));
			b.push(subdivide(other, count));
		});
		pair = [{ subpaths: a }, { subpaths: b }];
	}
	byTarget.set(to, pair);
	return pair;
}

/**
 * The path `progress` of the way from `from` to `to`, each anchor and
 * control point on a straight line (After Effects' path keyframes). Vertex
 * counts that differ are evened out by subdividing; a different number of
 * subpaths, or an open one against a closed one, holds `from` until the
 * next keyframe instead.
 */
export function interpolatePath(from: PathGeometry, to: PathGeometry, progress: number): PathGeometry {
	if (progress === 0 || from === to) return from;
	if (progress === 1) return to;

	// An easing that overshoots (a spring) carries the morph past either end.
	const pair = matchPaths(from, to);
	if (pair === null) return progress < 1 ? from : to;

	const [a, b] = pair;
	return {
		subpaths: a.subpaths.map((subpath, index) => {
			const target = b.subpaths[index]!.points;
			return {
				closed: subpath.closed,
				points: subpath.points.map((value, p) => value + (target[p]! - value) * progress),
			};
		}),
	};
}

// ── Trimming ────────────────────────────────────────────────

/** Samples per segment when measuring and flattening. */
const SAMPLES = 16;

/** Cumulative arc length along a segment at `SAMPLES + 1` evenly spaced parameters. */
function measure(cubic: Cubic): number[] {
	const lengths = [0];
	let px = cubic[0], py = cubic[1];
	for (let i = 1; i <= SAMPLES; i++) {
		const [x, y] = pointOn(cubic, i / SAMPLES);
		lengths.push(lengths[i - 1]! + Math.hypot(x - px, y - py));
		px = x;
		py = y;
	}
	return lengths;
}

/** The parameter at arc length `length` along a segment measured by `measure`. */
function parameterAt(lengths: number[], length: number): number {
	const total = lengths[SAMPLES]!;
	if (length <= 0 || total <= 0) return 0;
	if (length >= total) return 1;
	let i = 1;
	while (lengths[i]! < length) i++;
	const before = lengths[i - 1]!;
	const span = lengths[i]! - before;
	return (i - 1 + (span > 0 ? (length - before) / span : 0)) / SAMPLES;
}

/** The stretch of a subpath between arc lengths `from` and `to`, as cubics. */
function slice(cubics: Cubic[], measures: number[][], from: number, to: number): Cubic[] {
	const out: Cubic[] = [];
	let start = 0;
	for (let s = 0; s < cubics.length; s++) {
		const length = measures[s]![SAMPLES]!;
		const end = start + length;
		if (end > from && start < to && length > 0) {
			const t0 = parameterAt(measures[s]!, from - start);
			const t1 = parameterAt(measures[s]!, to - start);
			out.push(sliceCubic(cubics[s]!, t0, t1));
		}
		start = end;
	}
	return out;
}

/**
 * The path trimmed to the stretch from `start` to `end` of each subpath, as
 * fractions of its length (After Effects' Trim Paths, trimming every subpath
 * at once). `offset` slides that stretch along the path and wraps: on a
 * closed subpath across its start, on an open one into a second piece.
 * `start` above `end` trims the same as the two the other way round; a
 * stretch of the whole length or more leaves the path as it is.
 */
export function trimPath(geometry: PathGeometry, start: number, end: number, offset: number): PathGeometry {
	const from = Math.min(1, Math.max(0, Math.min(start, end)));
	const to = Math.min(1, Math.max(0, Math.max(start, end)));
	const span = to - from;
	if (span >= 1) return geometry;
	if (span <= 0) return EMPTY_PATH;

	const shift = from + offset;
	const head = shift - Math.floor(shift);
	const subpaths: Subpath[] = [];

	for (const subpath of geometry.subpaths) {
		const segments = segmentCount(subpath);
		if (segments === 0) continue;
		const cubics: Cubic[] = [];
		for (let s = 0; s < segments; s++) cubics.push(cubicOf(subpath.points, s));
		const measures = cubics.map(measure);
		const total = measures.reduce((sum, lengths) => sum + lengths[SAMPLES]!, 0);
		if (total <= 0) continue;

		const a = head * total;
		const b = (head + span) * total;
		if (b <= total) {
			const piece = slice(cubics, measures, a, b);
			if (piece.length) subpaths.push(fromCubics(piece, false));
			continue;
		}

		const first = slice(cubics, measures, a, total);
		const second = slice(cubics, measures, 0, b - total);
		if (subpath.closed) {
			// Through the start, which is where the outline continues.
			const joined = [...first, ...second];
			if (joined.length) subpaths.push(fromCubics(joined, false));
		} else {
			if (first.length) subpaths.push(fromCubics(first, false));
			if (second.length) subpaths.push(fromCubics(second, false));
		}
	}

	return { subpaths };
}

// ── Hit testing ─────────────────────────────────────────────

/** A subpath as a polyline, `[x0, y0, x1, y1, ...]`. */
function flatten(subpath: Subpath): number[] {
	const { points } = subpath;
	const out = [points[0]!, points[1]!];
	for (let s = 0; s < segmentCount(subpath); s++) {
		const cubic = cubicOf(points, s);
		const steps = isStraight(cubic) ? 1 : SAMPLES;
		for (let i = 1; i <= steps; i++) out.push(...pointOn(cubic, i / steps));
	}
	return out;
}

/**
 * Whether (x, y) is inside the area the path fills, every subpath closed the
 * way a fill closes it, by the nonzero or the even-odd rule.
 */
export function pointInPath(geometry: PathGeometry, x: number, y: number, evenOdd = false): boolean {
	let winding = 0;
	for (const subpath of geometry.subpaths) {
		const line = flatten(subpath);
		const n = line.length / 2;
		for (let i = 0; i < n; i++) {
			const ax = line[i * 2]!, ay = line[i * 2 + 1]!;
			const j = (i + 1) % n;
			const bx = line[j * 2]!, by = line[j * 2 + 1]!;
			if (ay <= y) {
				if (by > y && (bx - ax) * (y - ay) - (x - ax) * (by - ay) > 0) winding++;
			} else if (by <= y && (bx - ax) * (y - ay) - (x - ax) * (by - ay) < 0) {
				winding--;
			}
		}
	}
	return evenOdd ? winding % 2 !== 0 : winding !== 0;
}

/** The shortest distance from (x, y) to the path's outline (not its area). */
export function distanceToPath(geometry: PathGeometry, x: number, y: number): number {
	let best = Infinity;
	for (const subpath of geometry.subpaths) {
		const line = flatten(subpath);
		if (line.length === 2) best = Math.min(best, Math.hypot(x - line[0]!, y - line[1]!));
		for (let i = 2; i < line.length; i += 2) {
			best = Math.min(best, distanceToSegment(x, y, line[i - 2]!, line[i - 1]!, line[i]!, line[i + 1]!));
		}
	}
	return best;
}

function distanceToSegment(x: number, y: number, ax: number, ay: number, bx: number, by: number): number {
	const dx = bx - ax;
	const dy = by - ay;
	const lengthSquared = dx * dx + dy * dy;
	const t = lengthSquared > 0 ? Math.max(0, Math.min(1, ((x - ax) * dx + (y - ay) * dy) / lengthSquared)) : 0;
	return Math.hypot(x - (ax + t * dx), y - (ay + t * dy));
}

/** The point `t` along segment `segment` of subpath `subpath`. */
export function pointOnPath(geometry: PathGeometry, subpath: number, segment: number, t: number): { x: number; y: number } {
	const [x, y] = pointOn(cubicOf(geometry.subpaths[subpath]!.points, segment), t);
	return { x, y };
}

/**
 * The point on the path's outline closest to (x, y): which subpath, which
 * segment, the parameter along it, and how far away it is. Null for an empty
 * path. What an editor inserts a vertex at.
 */
export function nearestOnPath(geometry: PathGeometry, x: number, y: number): { subpath: number; segment: number; t: number; distance: number } | null {
	let best: { subpath: number; segment: number; t: number; distance: number } | null = null;
	geometry.subpaths.forEach((subpath, index) => {
		for (let s = 0; s < segmentCount(subpath); s++) {
			const cubic = cubicOf(subpath.points, s);
			// Coarse samples, then a finer look around the closest one.
			let bestT = 0;
			let bestDistance = Infinity;
			const probe = (t: number) => {
				const [px, py] = pointOn(cubic, t);
				const distance = Math.hypot(px - x, py - y);
				if (distance < bestDistance) {
					bestDistance = distance;
					bestT = t;
				}
			};
			for (let i = 0; i <= SAMPLES * 2; i++) probe(i / (SAMPLES * 2));
			const around = bestT;
			const step = 1 / (SAMPLES * 2);
			for (let i = -10; i <= 10; i++) probe(Math.min(1, Math.max(0, around + (i / 10) * step)));
			if (best === null || bestDistance < best.distance) {
				best = { subpath: index, segment: s, t: bestT, distance: bestDistance };
			}
		}
	});
	return best;
}