packages/core/src/lib/geometry/path-utilities.ts
This is the source snapshot used to build these API details. View this revision on GitHub.
1 import type { flattenPathWang } from './path-wang.js';
2 import type { simplifyPathRadial } from './path-radial.js';
3 import { arcPoint, TAU, type ArcSegment } from './path-arc.js';
4 import { PathGeometry, type PathSegment } from './path-geometry.js';
5
6 const DEFAULT_MAX_SEGMENTS = 1_000_000;
7
8 /**
9 * Positive approximation tolerance and output-segment budget for curve flattening.
10 *
11 * @see {@link flattenPath}
12 * @see {@link flattenPathWang}
13 */
14 export interface FlattenPathOptions {
15 /** Positive maximum geometric approximation error. See {@link FlattenPathOptions}. */
16 readonly tolerance: number;
17 /** Upper bound on the number of output path segments. See {@link FlattenPathOptions}. */
18 readonly maxSegments?: number;
19 }
20
21 /**
22 * Positive tolerance and output-segment budget for polyline simplification.
23 *
24 * @see {@link simplifyPath}
25 * @see {@link simplifyPathRadial}
26 */
27 export interface SimplifyPathOptions {
28 /** Positive maximum geometric approximation error. See {@link SimplifyPathOptions}. */
29 readonly tolerance: number;
30 /** Upper bound on the number of output path segments. See {@link SimplifyPathOptions}. */
31 readonly maxSegments?: number;
32 }
33
34 /**
35 * Subdivision count and output-segment budget for splitting path segments.
36 *
37 * @see {@link subdividePath}
38 */
39 export interface SubdividePathOptions {
40 /**
41 * Number of pieces produced from each drawable path segment. See {@link SubdividePathOptions}.
42 */
43 readonly divisions: number;
44 /** Upper bound on the number of output path segments. See {@link SubdividePathOptions}. */
45 readonly maxSegments?: number;
46 }
47
48 type Point = readonly [number, number];
49
50 /**
51 * Returns independent geometry with curves approximated by line segments within the requested
52 * tolerance.
53 *
54 * @param path - Source geometry; it is not modified. See {@link PathGeometry}.
55 * @param options - Maximum approximation error and flattening work limits. See
56 * {@link FlattenPathOptions} .
57 * @returns Independent geometry with curves replaced by line segments. See {@link PathGeometry}.
58 *
59 * @see {@link PathGeometry}
60 * @see {@link FlattenPathOptions}
61 */
62 export function flattenPath(path: PathGeometry, options: Readonly<FlattenPathOptions>): PathGeometry {
63 const tolerance = requiredPositive(options.tolerance, 'tolerance');
64 const output = collector(options.maxSegments);
65 let current: Point = [0, 0];
66 let start: Point = [0, 0];
67 for (const segment of path) {
68 switch (segment.type) {
69 case 'move': current = start = [segment.x, segment.y]; output.add(segment); break;
70 case 'line': current = [segment.x, segment.y]; output.add(segment); break;
71 case 'close': current = start; output.add(segment); break;
72 case 'quadratic': {
73 const end: Point = [segment.x, segment.y];
74 flattenQuadratic(current, [segment.cpx, segment.cpy], end, tolerance, output);
75 current = end;
76 break;
77 }
78 case 'cubic': {
79 const end: Point = [segment.x, segment.y];
80 flattenCubic(current, [segment.cp1x, segment.cp1y], [segment.cp2x, segment.cp2y], end, tolerance, output);
81 current = end;
82 break;
83 }
84 case 'arc': {
85 const arcStart = arcPoint(segment, segment.startAngle);
86 if (!samePoint(current, arcStart)) output.add(line(arcStart));
87 flattenArc(segment, tolerance, output);
88 current = arcPoint(segment, segment.startAngle + segment.sweep);
89 break;
90 }
91 }
92 }
93 return output.finish();
94 }
95
96 /**
97 * Returns independent geometry with each drawable segment split into the requested number of
98 * pieces.
99 *
100 * @param path - Source geometry; it is not modified. See {@link PathGeometry}.
101 * @param options - Subdivision length and work limits. See {@link SubdividePathOptions}.
102 * @returns Independent geometry with segments split according to the requested limits. See
103 * {@link PathGeometry} .
104 *
105 * @see {@link PathGeometry}
106 * @see {@link SubdividePathOptions}
107 */
108 export function subdividePath(path: PathGeometry, options: Readonly<SubdividePathOptions>): PathGeometry {
109 const divisions = requiredInteger(options.divisions, 'divisions');
110 const output = collector(options.maxSegments);
111 let current: Point = [0, 0];
112 let start: Point = [0, 0];
113 for (const segment of path) {
114 switch (segment.type) {
115 case 'move': current = start = [segment.x, segment.y]; output.add(segment); break;
116 case 'line': {
117 const end: Point = [segment.x, segment.y];
118 subdivideLine(current, end, divisions, output);
119 current = end;
120 break;
121 }
122 case 'quadratic': {
123 const end: Point = [segment.x, segment.y];
124 subdivideQuadratic(current, [segment.cpx, segment.cpy], end, divisions, output);
125 current = end;
126 break;
127 }
128 case 'cubic': {
129 const end: Point = [segment.x, segment.y];
130 subdivideCubic(current, [segment.cp1x, segment.cp1y], [segment.cp2x, segment.cp2y], end, divisions, output);
131 current = end;
132 break;
133 }
134 case 'arc': {
135 const arcStart = arcPoint(segment, segment.startAngle);
136 if (!samePoint(current, arcStart)) output.add(line(arcStart));
137 for (let i = 0; i < divisions; i++) {
138 output.add({ ...segment, startAngle: normalizeAngle(segment.startAngle + segment.sweep * i / divisions), sweep: segment.sweep / divisions });
139 }
140 current = arcPoint(segment, segment.startAngle + segment.sweep);
141 break;
142 }
143 case 'close':
144 if (!samePoint(current, start)) subdivideLine(current, start, divisions, output);
145 current = start;
146 output.add(segment);
147 break;
148 }
149 }
150 return output.finish();
151 }
152
153 /**
154 * Returns independent polyline geometry with redundant points removed within the requested
155 * tolerance.
156 *
157 * @param path - Source geometry; it is not modified. See {@link PathGeometry}.
158 * @param options - Simplification tolerance and work limits. See {@link SimplifyPathOptions}.
159 * @returns Independent geometry with redundant line vertices removed. See {@link PathGeometry}.
160 *
161 * @see {@link PathGeometry}
162 * @see {@link SimplifyPathOptions}
163 */
164 export function simplifyPath(path: PathGeometry, options: Readonly<SimplifyPathOptions>): PathGeometry {
165 const tolerance = requiredPositive(options.tolerance, 'tolerance');
166 const output = collector(options.maxSegments);
167 let current: Point | undefined;
168 let start: Point | undefined;
169 let run: Point[] = [];
170 const flushOpen = () => {
171 if (!run.length) return;
172 for (const point of simplifyOpen(run, tolerance).slice(1)) output.add(line(point));
173 run = current ? [current] : [];
174 };
175 for (const segment of path) {
176 switch (segment.type) {
177 case 'move':
178 flushOpen();
179 current = start = [segment.x, segment.y];
180 run = [current];
181 output.add(segment);
182 break;
183 case 'line':
184 current = [segment.x, segment.y];
185 run.push(current);
186 break;
187 case 'close': {
188 if (!current || !start) throw new TypeError('simplifyPath requires a move segment before close.');
189 const simplified = simplifyClosed(withoutClosingDuplicate(run), tolerance);
190 for (const point of simplified.slice(1)) output.add(line(point));
191 output.add(segment);
192 current = start;
193 run = [current];
194 break;
195 }
196 default: throw new TypeError('simplifyPath requires line-only geometry.');
197 }
198 }
199 flushOpen();
200 return output.finish();
201 }
202
203 function collector(maxSegments: number | undefined) {
204 const limit = maxSegments === undefined ? DEFAULT_MAX_SEGMENTS : requiredInteger(maxSegments, 'maxSegments');
205 const segments: PathSegment[] = [];
206 return {
207 add(segment: PathSegment) {
208 if (segments.length >= limit) throw new RangeError('Path utility output exceeds maxSegments.');
209 segments.push(segment);
210 },
211 finish() {
212 const output = new PathGeometry();
213 if (segments.length) output.spliceSegments(0, 0, segments);
214 return output;
215 },
216 };
217 }
218
219 function requiredPositive(value: number, name: string): number {
220 if (!Number.isFinite(value) || value <= 0) throw new RangeError(`${name} must be a finite positive number.`);
221 return value;
222 }
223
224 function requiredInteger(value: number, name: string): number {
225 if (!Number.isSafeInteger(value) || value <= 0) throw new RangeError(`${name} must be a positive integer.`);
226 return value;
227 }
228
229 function flattenQuadratic(a: Point, b: Point, c: Point, tolerance: number, output: ReturnType<typeof collector>): void {
230 const stack: Array<readonly [Point, Point, Point, number]> = [[a, b, c, 0]];
231 while (stack.length) {
232 const [p0, p1, p2, depth] = stack.pop()!;
233 if (pointSegmentDistance(p1, p0, p2) <= tolerance) { output.add(line(p2)); continue; }
234 if (depth >= 60) throw new RangeError('flattenPath cannot satisfy tolerance due to numerical nonprogress.');
235 const p01 = midpoint(p0, p1), p12 = midpoint(p1, p2), p = midpoint(p01, p12);
236 stack.push([p, p12, p2, depth + 1], [p0, p01, p, depth + 1]);
237 }
238 }
239
240 function flattenCubic(a: Point, b: Point, c: Point, d: Point, tolerance: number, output: ReturnType<typeof collector>): void {
241 const stack: Array<readonly [Point, Point, Point, Point, number]> = [[a, b, c, d, 0]];
242 while (stack.length) {
243 const [p0, p1, p2, p3, depth] = stack.pop()!;
244 if (Math.max(pointSegmentDistance(p1, p0, p3), pointSegmentDistance(p2, p0, p3)) <= tolerance) { output.add(line(p3)); continue; }
245 if (depth >= 60) throw new RangeError('flattenPath cannot satisfy tolerance due to numerical nonprogress.');
246 const p01 = midpoint(p0, p1), p12 = midpoint(p1, p2), p23 = midpoint(p2, p3);
247 const p012 = midpoint(p01, p12), p123 = midpoint(p12, p23), p = midpoint(p012, p123);
248 stack.push([p, p123, p23, p3, depth + 1], [p0, p01, p012, p, depth + 1]);
249 }
250 }
251
252 function flattenArc(arc: ArcSegment, tolerance: number, output: ReturnType<typeof collector>): void {
253 const radius = Math.hypot(arc.ux, arc.uy, arc.vx, arc.vy);
254 const stack: Array<readonly [number, number, number]> = [[arc.startAngle, arc.startAngle + arc.sweep, 0]];
255 while (stack.length) {
256 const [from, to, depth] = stack.pop()!;
257 const middle = (from + to) / 2;
258 const a = arcPoint(arc, from), b = arcPoint(arc, to);
259 const sampled = Math.max(
260 pointSegmentDistance(arcPoint(arc, from + (to - from) / 4), a, b),
261 pointSegmentDistance(arcPoint(arc, middle), a, b),
262 pointSegmentDistance(arcPoint(arc, to - (to - from) / 4), a, b),
263 );
264 const bound = radius * (to - from) ** 2 / 8;
265 if (sampled <= tolerance && bound <= tolerance) { output.add(line(b)); continue; }
266 if (depth >= 60 || middle === from || middle === to) throw new RangeError('flattenPath cannot satisfy tolerance due to numerical nonprogress.');
267 stack.push([middle, to, depth + 1], [from, middle, depth + 1]);
268 }
269 }
270
271 function subdivideLine(a: Point, b: Point, divisions: number, output: ReturnType<typeof collector>) {
272 for (let i = 1; i <= divisions; i++) output.add(line(interpolate(a, b, i / divisions)));
273 }
274
275 function subdivideQuadratic(a: Point, b: Point, c: Point, divisions: number, output: ReturnType<typeof collector>) {
276 let rest: readonly [Point, Point, Point] = [a, b, c];
277 for (let i = divisions; i > 1; i--) {
278 const [left, right] = splitQuadratic(...rest, 1 / i);
279 output.add({ type: 'quadratic', cpx: left[1][0], cpy: left[1][1], x: left[2][0], y: left[2][1] });
280 rest = right;
281 }
282 output.add({ type: 'quadratic', cpx: rest[1][0], cpy: rest[1][1], x: rest[2][0], y: rest[2][1] });
283 }
284
285 function subdivideCubic(a: Point, b: Point, c: Point, d: Point, divisions: number, output: ReturnType<typeof collector>) {
286 let rest: readonly [Point, Point, Point, Point] = [a, b, c, d];
287 for (let i = divisions; i > 1; i--) {
288 const [left, right] = splitCubic(...rest, 1 / i);
289 output.add({ type: 'cubic', cp1x: left[1][0], cp1y: left[1][1], cp2x: left[2][0], cp2y: left[2][1], x: left[3][0], y: left[3][1] });
290 rest = right;
291 }
292 output.add({ type: 'cubic', cp1x: rest[1][0], cp1y: rest[1][1], cp2x: rest[2][0], cp2y: rest[2][1], x: rest[3][0], y: rest[3][1] });
293 }
294
295 function simplifyOpen(points: readonly Point[], tolerance: number): Point[] {
296 if (points.length <= 2) return [...points];
297 const keep = new Uint8Array(points.length);
298 keep[0] = keep[points.length - 1] = 1;
299 const stack: Array<readonly [number, number]> = [[0, points.length - 1]];
300 while (stack.length) {
301 const [first, last] = stack.pop()!;
302 let index = -1, maximum = tolerance;
303 for (let i = first + 1; i < last; i++) {
304 const distance = pointSegmentDistance(points[i], points[first], points[last]);
305 if (distance > maximum) { maximum = distance; index = i; }
306 }
307 if (index !== -1) { keep[index] = 1; stack.push([first, index], [index, last]); }
308 }
309 const result: Point[] = [];
310 for (let i = 0; i < points.length; i++) if (keep[i]) result.push(points[i]);
311 return result;
312 }
313
314 function simplifyClosed(points: readonly Point[], tolerance: number): Point[] {
315 if (points.length <= 3 || !hasThreeDistinct(points)) return [...points];
316 const [firstAnchor, secondAnchor] = closedAnchors(points);
317 const first = simplifyOpen(points.slice(0, firstAnchor + 1), tolerance);
318 const second = simplifyOpen(points.slice(firstAnchor, secondAnchor + 1), tolerance);
319 const third = simplifyOpen([...points.slice(secondAnchor), points[0]], tolerance);
320 return [...first, ...second.slice(1), ...third.slice(1, -1)];
321 }
322
323 function closedAnchors(points: readonly Point[]): readonly [number, number] {
324 let farthest = 1, farthestDistance = -1;
325 for (let i = 1; i < points.length; i++) {
326 const distance = pointDistance(points[0], points[i]);
327 if (distance > farthestDistance) { farthestDistance = distance; farthest = i; }
328 }
329 let third = -1, thirdDistance = -1;
330 for (let i = 1; i < points.length; i++) {
331 if (i === farthest || samePoint(points[i], points[0]) || samePoint(points[i], points[farthest])) continue;
332 const distance = pointSegmentDistance(points[i], points[0], points[farthest]);
333 if (distance > thirdDistance) { thirdDistance = distance; third = i; }
334 }
335 const [firstAnchor, secondAnchor] = [farthest, third].sort((a, b) => a - b);
336 return [firstAnchor, secondAnchor];
337 }
338
339 function withoutClosingDuplicate(points: readonly Point[]): Point[] {
340 return points.length > 1 && samePoint(points[0], points.at(-1)!) ? points.slice(0, -1) : [...points];
341 }
342 function hasThreeDistinct(points: readonly Point[]): boolean {
343 const first = points[0];
344 let second: Point | undefined;
345 for (let i = 1; i < points.length; i++) {
346 const point = points[i];
347 if (samePoint(point, first)) continue;
348 if (!second) second = point;
349 else if (!samePoint(point, second)) return true;
350 }
351 return false;
352 }
353 function splitQuadratic(a: Point, b: Point, c: Point, t: number): readonly [readonly [Point, Point, Point], readonly [Point, Point, Point]] {
354 const ab = interpolate(a, b, t), bc = interpolate(b, c, t), p = interpolate(ab, bc, t);
355 return [[a, ab, p], [p, bc, c]];
356 }
357 function splitCubic(a: Point, b: Point, c: Point, d: Point, t: number): readonly [readonly [Point, Point, Point, Point], readonly [Point, Point, Point, Point]] {
358 const ab = interpolate(a, b, t), bc = interpolate(b, c, t), cd = interpolate(c, d, t);
359 const abc = interpolate(ab, bc, t), bcd = interpolate(bc, cd, t), p = interpolate(abc, bcd, t);
360 return [[a, ab, abc, p], [p, bcd, cd, d]];
361 }
362 function line([x, y]: Point): PathSegment { return { type: 'line', x, y }; }
363 function midpoint(a: Point, b: Point): Point { return interpolate(a, b, 0.5); }
364 function interpolate(a: Point, b: Point, t: number): Point { return [a[0] + (b[0] - a[0]) * t, a[1] + (b[1] - a[1]) * t]; }
365 function pointDistance(a: Point, b: Point): number { return Math.hypot(difference(a[0], b[0]), difference(a[1], b[1])); }
366 function samePoint(a: Point, b: Point): boolean { return a[0] === b[0] && a[1] === b[1]; }
367 function pointSegmentDistance(point: Point, a: Point, b: Point): number {
368 const x = difference(b[0], a[0]), y = difference(b[1], a[1]);
369 const px = difference(point[0], a[0]), py = difference(point[1], a[1]);
370 const scale = Math.max(Math.abs(x), Math.abs(y), Math.abs(px), Math.abs(py));
371 if (scale === 0) return Math.hypot(px, py);
372 const scaledX = x / scale, scaledY = y / scale;
373 const scaledPX = px / scale, scaledPY = py / scale;
374 const length = scaledX * scaledX + scaledY * scaledY;
375 if (length === 0) return Math.hypot(px, py);
376 const t = Math.max(0, Math.min(1, (scaledPX * scaledX + scaledPY * scaledY) / length));
377 return scale * Math.hypot(scaledPX - scaledX * t, scaledPY - scaledY * t);
378 }
379 function difference(value: number, origin: number): number {
380 const result = value - origin;
381 if (!Number.isFinite(result)) throw new RangeError('Path utility cannot compare coordinates with an unrepresentable difference.');
382 return result;
383 }
384 function normalizeAngle(angle: number): number { const normalized = angle % TAU; return Object.is(normalized, -0) ? 0 : normalized; }
385 Documentation version
Section titled “Documentation version”Documentation built with @pibbl/core 0.0.2, revision 2dccb19. ALPHA — NOT FOR PRODUCTION USE.