packages/core/src/lib/geometry/path-radial.ts
This is the source snapshot used to build these API details. View this revision on GitHub.
1 import { PathGeometry } from './path-geometry.js';
2 import { simplifyPath, type SimplifyPathOptions } from './path-utilities.js';
3
4 type Point = readonly [number, number];
5
6 /**
7 * Simplifies line-only paths with a radial-distance prepass followed by the
8 * default Douglas--Peucker implementation. Each stage receives half of the
9 * requested error budget, so their errors compose within `tolerance`.
10 *
11 * @param path - Source geometry; it is not modified. See {@link PathGeometry}.
12 * @param options - Simplification tolerance and work limits. See {@link SimplifyPathOptions}.
13 * @returns Independent geometry with redundant line vertices removed. See {@link PathGeometry}.
14 *
15 * @see {@link PathGeometry}
16 * @see {@link SimplifyPathOptions}
17 */
18 export function simplifyPathRadial(path: PathGeometry, options: Readonly<SimplifyPathOptions>): PathGeometry {
19 const tolerance = requiredPositive(options.tolerance, 'tolerance');
20 const stageTolerance = tolerance / 2;
21 // A two-stage split cannot represent half of the smallest subnormal number
22 // without exceeding the caller's error budget. Retain the exact default
23 // contract in that case instead of applying the radial prepass.
24 if (stageTolerance === 0) return simplifyPath(path, options);
25 const filtered = new PathGeometry();
26 let current: Point | undefined;
27 let start: Point | undefined;
28 let run: Point[] = [];
29 const flushOpen = () => {
30 if (!run.length) return;
31 appendOpen(filtered, radialFilterOpen(run, stageTolerance));
32 run = current ? [current] : [];
33 };
34 for (const segment of path) {
35 switch (segment.type) {
36 case 'move':
37 flushOpen();
38 current = start = [segment.x, segment.y];
39 run = [current];
40 filtered.moveTo(segment.x, segment.y);
41 break;
42 case 'line':
43 current = [segment.x, segment.y];
44 run.push(current);
45 break;
46 case 'close': {
47 if (!current || !start) throw new TypeError('simplifyPathRadial requires a move segment before close.');
48 const raw = withoutClosingDuplicate(run);
49 const radial = radialFilterClosed(raw, stageTolerance);
50 // Do not make a valid closed subpath degenerate. The raw path is an
51 // exact fallback, and the shared DP stage will enforce the same rule.
52 appendOpen(filtered, radial.length >= 3 && hasThreeDistinct(radial) ? radial : raw);
53 filtered.closePath();
54 current = start;
55 run = [current];
56 break;
57 }
58 default: throw new TypeError('simplifyPathRadial requires line-only geometry.');
59 }
60 }
61 flushOpen();
62 return simplifyPath(filtered, { tolerance: stageTolerance, maxSegments: options.maxSegments });
63 }
64
65 function appendOpen(path: PathGeometry, points: readonly Point[]): void {
66 for (const [x, y] of points.slice(1)) path.lineTo(x, y);
67 }
68
69 function radialFilterOpen(points: readonly Point[], tolerance: number): Point[] {
70 if (points.length <= 2) return [...points];
71 const result: Point[] = [points[0]];
72 let previous = points[0];
73 for (let i = 1; i < points.length - 1; i++) {
74 if (distance(points[i], previous) > tolerance) {
75 result.push(points[i]);
76 previous = points[i];
77 }
78 }
79 const last = points.at(-1)!;
80 if (!samePoint(previous, last)) result.push(last);
81 return result;
82 }
83
84 function radialFilterClosed(points: readonly Point[], tolerance: number): Point[] {
85 if (points.length <= 3) return [...points];
86 const result: Point[] = [points[0]];
87 let previous = points[0];
88 for (let i = 1; i < points.length; i++) {
89 if (distance(points[i], previous) > tolerance) {
90 result.push(points[i]);
91 previous = points[i];
92 }
93 }
94 return result;
95 }
96
97 function withoutClosingDuplicate(points: readonly Point[]): Point[] {
98 return points.length > 1 && samePoint(points[0], points.at(-1)!) ? points.slice(0, -1) : [...points];
99 }
100 function hasThreeDistinct(points: readonly Point[]): boolean {
101 let first: Point | undefined;
102 let second: Point | undefined;
103 for (const point of points) {
104 if (!first) { first = point; continue; }
105 if (samePoint(point, first)) continue;
106 if (!second) { second = point; continue; }
107 if (!samePoint(point, second)) return true;
108 }
109 return false;
110 }
111 function requiredPositive(value: number, name: string): number {
112 if (!Number.isFinite(value) || value <= 0) throw new RangeError(`${name} must be a finite positive number.`);
113 return value;
114 }
115 function samePoint(a: Point, b: Point): boolean { return a[0] === b[0] && a[1] === b[1]; }
116 function distance(a: Point, b: Point): number { return Math.hypot(a[0] - b[0], a[1] - b[1]); }
117 Documentation version
Section titled “Documentation version”Documentation built with @pibbl/core 0.0.2, revision 2dccb19. ALPHA — NOT FOR PRODUCTION USE.