# packages/core/src/lib/geometry/path-wang.ts This is the source snapshot used to build these API details. [View this revision on GitHub](https://github.com/benlesh/pibbl/blob/272a94aaf62e0bd6ad8726a4c607a76a9ec44ca1/packages/core/src/lib/geometry/path-wang.ts#L24). [Back to reference](/reference/functions/path-geometry/)
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 Documentation built with @pibbl/core 0.0.2, revision 272a94a. ALPHA — NOT FOR PRODUCTION USE.