packages/core/src/lib/geometry/path-wang.ts
This is the source snapshot used to build these API details. View this revision on GitHub.
1 import { arcPoint, type ArcSegment } from './path-arc.js';
2 import { PathGeometry, type PathSegment } from './path-geometry.js';
3 import type { FlattenPathOptions } from './path-utilities.js';
4
5 const DEFAULT_MAX_SEGMENTS = 1_000_000;
6
7 type Point = readonly [number, number];
8
9 /**
10 * Flattens curves with Wang's uniform-parameter bound.
11 *
12 * This trades adaptive placement for a known output count and independent point
13 * evaluation. It is most useful when predictable allocation or parallel output
14 * generation matters more than minimizing the number of line segments.
15 *
16 * @param path - Source geometry; it is not modified. See {@link PathGeometry}.
17 * @param options - Maximum approximation error and flattening work limits. See
18 * {@link FlattenPathOptions} .
19 * @returns Independent geometry with curves replaced by line segments. See {@link PathGeometry}.
20 *
21 * @see {@link PathGeometry}
22 * @see {@link FlattenPathOptions}
23 */
24 export function flattenPathWang(path: PathGeometry, options: Readonly<FlattenPathOptions>): PathGeometry {
25 const tolerance = requiredPositive(options.tolerance, 'tolerance');
26 const output = collector(options.maxSegments);
27 let current: Point = [0, 0];
28 let start: Point = [0, 0];
29 for (const segment of path) {
30 switch (segment.type) {
31 case 'move': current = start = [segment.x, segment.y]; output.add(segment); break;
32 case 'line': current = [segment.x, segment.y]; output.add(segment); break;
33 case 'close': current = start; output.add(segment); break;
34 case 'quadratic': {
35 const end: Point = [segment.x, segment.y];
36 flattenQuadratic(current, [segment.cpx, segment.cpy], end, tolerance, output);
37 current = end;
38 break;
39 }
40 case 'cubic': {
41 const end: Point = [segment.x, segment.y];
42 flattenCubic(current, [segment.cp1x, segment.cp1y], [segment.cp2x, segment.cp2y], end, tolerance, output);
43 current = end;
44 break;
45 }
46 case 'arc': {
47 const arcStart = arcPoint(segment, segment.startAngle);
48 if (!samePoint(current, arcStart)) output.add(line(arcStart));
49 flattenArc(segment, tolerance, output);
50 current = arcPoint(segment, segment.startAngle + segment.sweep);
51 break;
52 }
53 }
54 }
55 return output.finish();
56 }
57
58 function flattenQuadratic(a: Point, b: Point, c: Point, tolerance: number, output: ReturnType<typeof collector>): void {
59 const n = segmentsForSecondDifference(secondDifference(a, b, c), 2, tolerance);
60 output.reserve(n);
61 for (let i = 1; i <= n; i++) output.add(line(i === n ? c : evaluateQuadratic(a, b, c, i / n)));
62 }
63
64 function flattenCubic(a: Point, b: Point, c: Point, d: Point, tolerance: number, output: ReturnType<typeof collector>): void {
65 const n = Math.max(
66 segmentsForSecondDifference(secondDifference(a, b, c), 3, tolerance),
67 segmentsForSecondDifference(secondDifference(b, c, d), 3, tolerance),
68 );
69 output.reserve(n);
70 for (let i = 1; i <= n; i++) output.add(line(i === n ? d : evaluateCubic(a, b, c, d, i / n)));
71 }
72
73 function flattenArc(arc: ArcSegment, tolerance: number, output: ReturnType<typeof collector>): void {
74 const stretch = operatorNorm(arc.ux, arc.uy, arc.vx, arc.vy);
75 if (!Number.isFinite(stretch)) throw new RangeError('flattenPathWang arc calculation overflowed.');
76 if (stretch === 0 || arc.sweep === 0) {
77 output.add(line(arcPoint(arc, arc.startAngle + arc.sweep)));
78 return;
79 }
80 // The image of a unit-circle chord deviates by no more than its sagitta times
81 // the affine basis' maximum stretch. Restricting each span to pi also handles
82 // complete turns and finite chord distances conservatively.
83 const ratio = Math.min(1, tolerance / stretch);
84 // 1 - cos(x) loses useful precision for small tolerances. The equivalent
85 // sagitta form remains stable: 2 sin^2(span / 4) <= tolerance / stretch.
86 const span = Math.min(Math.PI, 4 * Math.asin(Math.sqrt(ratio / 2)));
87 const n = checkedSegments(Math.ceil(Math.abs(arc.sweep) / span));
88 output.reserve(n);
89 for (let i = 1; i <= n; i++) output.add(line(arcPoint(arc, i === n ? arc.startAngle + arc.sweep : arc.startAngle + arc.sweep * i / n)));
90 }
91
92 function segmentsForSecondDifference(difference: Point, degree: 2 | 3, tolerance: number): number {
93 // Wang's formula: sqrt(|second difference| * n(n - 1) / (8 * tolerance)).
94 const length = Math.hypot(difference[0], difference[1]);
95 if (!Number.isFinite(length)) throw new RangeError('flattenPathWang curve calculation overflowed.');
96 return checkedSegments(Math.max(1, Math.ceil(Math.sqrt(length * degree * (degree - 1) / (8 * tolerance)))));
97 }
98
99 function evaluateQuadratic(a: Point, b: Point, c: Point, t: number): Point {
100 const ab = interpolate(a, b, t), bc = interpolate(b, c, t);
101 return interpolate(ab, bc, t);
102 }
103
104 function evaluateCubic(a: Point, b: Point, c: Point, d: Point, t: number): Point {
105 const ab = interpolate(a, b, t), bc = interpolate(b, c, t), cd = interpolate(c, d, t);
106 return interpolate(interpolate(ab, bc, t), interpolate(bc, cd, t), t);
107 }
108
109 function secondDifference(a: Point, b: Point, c: Point): Point {
110 return [a[0] - 2 * b[0] + c[0], a[1] - 2 * b[1] + c[1]];
111 }
112
113 function operatorNorm(ux: number, uy: number, vx: number, vy: number): number {
114 const scale = Math.max(Math.abs(ux), Math.abs(uy), Math.abs(vx), Math.abs(vy));
115 if (scale === 0) return 0;
116 const a = ux / scale, b = uy / scale, c = vx / scale, d = vy / scale;
117 return scale * Math.sqrt((a * a + b * b + c * c + d * d + Math.hypot(a * a + c * c - b * b - d * d, 2 * (a * b + c * d))) / 2);
118 }
119
120 function collector(maxSegments: number | undefined) {
121 const limit = maxSegments === undefined ? DEFAULT_MAX_SEGMENTS : requiredInteger(maxSegments, 'maxSegments');
122 const segments: PathSegment[] = [];
123 return {
124 reserve(count: number) {
125 if (segments.length + count > limit) throw new RangeError('Path utility output exceeds maxSegments.');
126 },
127 add(segment: PathSegment) {
128 if (segments.length >= limit) throw new RangeError('Path utility output exceeds maxSegments.');
129 segments.push(segment);
130 },
131 finish() {
132 const output = new PathGeometry();
133 if (segments.length) output.spliceSegments(0, 0, segments);
134 return output;
135 },
136 };
137 }
138
139 function checkedSegments(value: number): number {
140 if (!Number.isSafeInteger(value) || value < 1) throw new RangeError('flattenPathWang cannot satisfy tolerance due to numerical nonprogress.');
141 return value;
142 }
143 function requiredPositive(value: number, name: string): number {
144 if (!Number.isFinite(value) || value <= 0) throw new RangeError(`${name} must be a finite positive number.`);
145 return value;
146 }
147 function requiredInteger(value: number, name: string): number {
148 if (!Number.isSafeInteger(value) || value <= 0) throw new RangeError(`${name} must be a positive integer.`);
149 return value;
150 }
151 function line([x, y]: Point): PathSegment { return { type: 'line', x, y }; }
152 function interpolate(a: Point, b: Point, t: number): Point { return [a[0] + (b[0] - a[0]) * t, a[1] + (b[1] - a[1]) * t]; }
153 function samePoint(a: Point, b: Point): boolean { return a[0] === b[0] && a[1] === b[1]; }
154 Documentation version
Section titled “Documentation version”Documentation built with @pibbl/core 0.0.2, revision 272a94a. ALPHA — NOT FOR PRODUCTION USE.