packages/core/src/lib/geometry/path-bending.ts
This is the source snapshot used to build these API details. View this revision on GitHub.
1 import type { ArcBendTransformOptions, BendTransformOptions } from './transform-bend.js';
2 import { PathGeometry, type PathSegment } from './path-geometry.js';
3 import { TAU } from './path-arc.js';
4 import { bendSpanBounds, bendSpanPoint, bendSpans, splitBendSpan, type BendBounds, type BendPoint, type BendSpan } from './path-bend-spans.js';
5 import { measureBendGuide, prepareBendGuide } from './path-bend-guide.js';
6
7 export interface PathBendFrame {
8 readonly x: number; readonly y: number; readonly width: number; readonly height: number;
9 }
10 /**
11 * Circular guide geometry used when bending a path along an arc.
12 *
13 * @see {@link ArcBendTransformOptions}
14 */
15 export interface PathBendArc {
16 /** Horizontal coordinate of the center. See {@link PathBendArc}. */
17 readonly cx: number;
18 /** Vertical coordinate of the center. See {@link PathBendArc}. */
19 readonly cy: number;
20 /** Radius in the coordinate system of this geometry or effect. See {@link PathBendArc}. */
21 readonly radius: number;
22 /** Angle at which the arc or slice begins. See {@link PathBendArc}. */
23 readonly startAngle: number;
24 /** Angular extent of the arc. See {@link PathBendArc}. */
25 readonly sweep: number;
26 }
27 /**
28 * Placement of the source along the beginning, center, or end of a bending guide.
29 *
30 * @see {@link BendTransformOptions}
31 */
32 export type PathBendAlign = 'start' | 'center' | 'end';
33 /**
34 * The source baseline used for bending: an edge, center, or explicit coordinate.
35 *
36 * @see {@link BendTransformOptions}
37 */
38 export type PathBendBaseline = 'center' | 'top' | 'bottom' | number;
39 /**
40 * Whether bending preserves source length or stretches it to the guide.
41 *
42 * @see {@link BendTransformOptions}
43 */
44 export type PathBendFit = 'none' | 'stretch';
45 /**
46 * Policy for source geometry extending beyond a bending guide.
47 *
48 * @see {@link BendTransformOptions}
49 */
50 export type PathBendOverflow = 'error' | 'extend' | 'wrap';
51 /**
52 * Source bounds, guide alignment, baseline, fitting, overflow, and approximation limits for path bending.
53 *
54 * @see {@link PathBendAlign}
55 * @see {@link PathBendBaseline}
56 * @see {@link PathBendFit}
57 * @see {@link PathBendOverflow}
58 */
59 export interface PathBendOptions {
60 /**
61 * Source coordinate frame used to normalize the geometry before bending. See
62 * {@link PathBendFrame}.
63 */
64 readonly source: PathBendFrame;
65 /** Placement of the source length along the guide. See {@link PathBendAlign}. */
66 readonly align?: PathBendAlign;
67 /** Source baseline mapped onto the guide. See {@link PathBendBaseline}. */
68 readonly baseline?: PathBendBaseline;
69 /** Policy for fitting content within its available box. See {@link PathBendFit}. */
70 readonly fit?: PathBendFit;
71 /** Offset along the guide. See {@link PathBendOptions}. */
72 readonly offset?: number;
73 /** Offset perpendicular to the guide. See {@link PathBendOptions}. */
74 readonly normalOffset?: number;
75 /**
76 * Policy for geometry extending beyond the guide's available length. See
77 * {@link PathBendOverflow}.
78 */
79 readonly overflow?: PathBendOverflow;
80 /** Positive maximum geometric approximation error. See {@link PathBendOptions}. */
81 readonly tolerance: number;
82 /** Upper bound on the number of output path segments. See {@link PathBendOptions}. */
83 readonly maxSegments?: number;
84 }
85 export interface BendPathAlongArcOptions extends PathBendOptions { readonly arc: PathBendArc }
86
87 // Work limits bound failed certification attempts, not just successful output.
88 const MAX_WORK = 2_000_000;
89 const MAX_DEPTH = 52;
90 interface Placement {
91 readonly x: number; readonly baseline: number; readonly normal: number;
92 readonly shift: number; readonly scale: number; readonly length: number;
93 readonly tolerance: number; readonly maxSegments: number; readonly overflow: PathBendOverflow;
94 readonly width: number; readonly fit: PathBendFit; readonly anchor: number; readonly offset: number;
95 }
96
97 /** Bends continuous geometry along an analytic circle; returns independent line geometry. */
98 export function bendPathAlongArc(source: PathGeometry, options: Readonly<BendPathAlongArcOptions>): PathGeometry {
99 if (!(source instanceof PathGeometry)) throw new TypeError('source must be a PathGeometry.');
100 object(options, 'options');
101 const input = options.arc;
102 object(input, 'arc');
103 const startAngle = finite(input.startAngle, 'arc.startAngle');
104 const arc: PathBendArc = {
105 cx: finite(input.cx, 'arc.cx'), cy: finite(input.cy, 'arc.cy'),
106 radius: positive(input.radius, 'arc.radius'), startAngle: startAngle % TAU,
107 sweep: finite(input.sweep, 'arc.sweep'),
108 };
109 if (!arc.sweep || Math.abs(arc.sweep) > TAU) throw new RangeError('arc.sweep must be nonzero and at most one revolution.');
110 const p = placement(options, positive(arc.radius * Math.abs(arc.sweep), 'guide length'));
111 if (p.overflow === 'wrap' && Math.abs(arc.sweep) !== TAU) throw new RangeError('wrap requires a closed guide.');
112 const direction = Math.sign(arc.sweep);
113 const distance = (x: number) => p.shift + p.scale * (x - p.x);
114 const displacement = (y: number) => y - p.baseline + p.normal;
115 const map = ([x, y]: BendPoint): BendPoint => {
116 const s = finite(distance(x), 'mapped guide distance'), d = finite(displacement(y), 'normal displacement');
117 if (p.overflow === 'error' && (s < 0 || s > p.length)) throw new RangeError('Source geometry extends beyond the guide.');
118 const onGuide = p.overflow === 'extend' ? Math.max(0, Math.min(p.length, s)) : s;
119 const theta = arc.startAngle + direction * ((onGuide / arc.radius) % TAU);
120 const cos = Math.cos(theta), sin = Math.sin(theta);
121 const radial = arc.radius - direction * d, extension = s - onGuide;
122 // Division/modulo can lose the phase of enormous unwrapped angles. Its
123 // output effect scales with the displaced radius (not just the guide radius).
124 checkPrecision(Math.max(Math.abs(startAngle), Math.abs(onGuide / arc.radius)) * Math.max(Math.abs(radial), Math.abs(extension)), p.tolerance);
125 return [
126 finite(arc.cx + radial * cos - direction * extension * sin, 'bent x'),
127 finite(arc.cy + radial * sin + direction * extension * cos, 'bent y'),
128 ];
129 };
130 const bound = (b: BendBounds): number => {
131 const low = distance(b.xmin), high = distance(b.xmax);
132 if (p.overflow === 'error' && (low < 0 || high > p.length)) return Infinity;
133 const d = Math.max(Math.abs(displacement(b.ymin)), Math.abs(displacement(b.ymax)));
134 const dx = p.scale * b.dx, ddx = p.scale * b.ddx;
135 if (p.overflow === 'extend') {
136 if (high <= 0 || low >= p.length) return Math.hypot(ddx, b.ddy) / 8;
137 // The normal is continuous at extension boundaries, but the derivative
138 // may jump. A Lipschitz bound remains valid across the boundary.
139 if (low < 0 || high > p.length) return (b.dy + (1 + d / arc.radius) * dx) / 2;
140 }
141 const theta1 = dx / arc.radius, theta2 = ddx / arc.radius;
142 const radial = Math.max(Math.abs(arc.radius - direction * displacement(b.ymin)), Math.abs(arc.radius - direction * displacement(b.ymax)));
143 // For F = center + rho * unit(theta), ||F''|| <= |rho''|
144 // + 2|rho'||theta'| + |rho|(|theta'|² + |theta''|).
145 // Linear interpolation on [0,1] has error at most sup ||F''|| / 8.
146 return (b.ddy + 2 * b.dy * theta1 + radial * (theta1 * theta1 + theta2)) / 8;
147 };
148 const scale = Math.max(Math.abs(arc.cx), Math.abs(arc.cy), arc.radius, p.length);
149 return approximate(source, p, map, bound, scale);
150 }
151
152 /** Bends geometry by distance along one smooth guide contour. */
153 export function bendPathAlongPath(source: PathGeometry, guide: PathGeometry, options: Readonly<PathBendOptions>): PathGeometry {
154 if (!(source instanceof PathGeometry) || !(guide instanceof PathGeometry)) throw new TypeError('source and guide must be PathGeometry values.');
155 object(options, 'options');
156 const input = placement(options, 1); // Snapshot options once; guide measurement supplies length later.
157 const prepared = prepareBendGuide(guide);
158 if (input.overflow === 'wrap' && !prepared.closed) throw new RangeError('wrap requires an explicitly closed guide.');
159 let xmin = Infinity, xmax = -Infinity, displacement = 0;
160 const normalDistance = (y: number) => y - input.baseline + input.normal;
161 for (const item of bendSpans(source)) {
162 if (item.type === 'close') continue;
163 const b = item.type === 'move' ? { xmin: item.point[0], xmax: item.point[0], ymin: item.point[1], ymax: item.point[1] } : bendSpanBounds(item.span);
164 xmin = Math.min(xmin, b.xmin); xmax = Math.max(xmax, b.xmax);
165 displacement = Math.max(displacement, Math.abs(normalDistance(b.ymin)), Math.abs(normalDistance(b.ymax)));
166 }
167 if (xmin === Infinity) xmin = xmax = input.x;
168 finite(displacement, 'normal displacement');
169 const atLength = (length: number): Placement => {
170 const scale = input.fit === 'stretch' ? positive(length / input.width, 'fit scale') : 1;
171 return { ...input, length, scale, shift: input.anchor * (length - scale * input.width) + input.offset };
172 };
173 const distance = (p: Placement, x: number) => p.shift + p.scale * (x - p.x);
174 const measured = measureBendGuide(prepared, input.tolerance, displacement, length => {
175 const p = atLength(length);
176 const sensitivity = input.fit === 'stretch' ? Math.max(Math.abs((xmin - input.x) / input.width), Math.abs((xmax - input.x) / input.width)) : input.anchor;
177 const laps = input.overflow === 'wrap' ? Math.ceil(Math.max(Math.abs(distance(p, xmin)), Math.abs(distance(p, xmax))) / length) : 0;
178 return finite(2 + sensitivity + laps, 'guide distance sensitivity');
179 });
180 const p = atLength(measured.length), upper = atLength(measured.length + measured.uncertainty);
181 const wrap = p.overflow === 'wrap';
182 const rangeCertified = (x: number) => {
183 const d = distance(p, x), u = distance(upper, x);
184 const roundoff = Number.EPSILON * 64 * Math.max(Math.abs(d), Math.abs(u), p.length);
185 return Math.min(d, u) >= -roundoff && Math.min(p.length - d, upper.length - u) >= -roundoff;
186 };
187 const map = ([x, y]: BendPoint): BendPoint => {
188 if (p.overflow === 'error' && !rangeCertified(x)) throw new RangeError('Source geometry exceeds the guide or its range cannot be certified.');
189 const field = measured.field(distance(p, x), wrap), d = normalDistance(y);
190 return [finite(field.point[0] + d * field.normal[0], 'bent x'), finite(field.point[1] + d * field.normal[1], 'bent y')];
191 };
192 const bound = (b: BendBounds, span: BendSpan): number => {
193 if (p.overflow === 'error' && (!rangeCertified(b.xmin) || !rangeCertified(b.xmax))) return Infinity;
194 const s0 = distance(p, bendSpanPoint(span, 0)[0]), s1 = distance(p, bendSpanPoint(span, 1)[0]);
195 const d = Math.max(Math.abs(normalDistance(b.ymin)), Math.abs(normalDistance(b.ymax)));
196 return measured.chordError(distance(p, b.xmin), distance(p, b.xmax), s0, s1, d, p.scale * b.dx, p.scale * b.ddx, b.dy, b.ddy, wrap);
197 };
198 return approximate(source, p, map, bound, Math.max(prepared.scale, p.length));
199 }
200
201 function approximate(source: PathGeometry, p: Placement, map: (point: BendPoint) => BendPoint, bound: (bounds: BendBounds, span: BendSpan) => number, scale: number): PathGeometry {
202 const output: PathSegment[] = [];
203 let work = 0;
204 const add = (segment: PathSegment) => {
205 if (output.length >= p.maxSegments) throw new RangeError('Path bending exceeds maxSegments.');
206 output.push(segment);
207 };
208 for (const item of bendSpans(source)) {
209 if (item.type === 'move') {
210 const [x, y] = map(item.point);
211 checkPrecision(Math.max(scale, Math.abs(x), Math.abs(y), ...item.point.map(Math.abs)), p.tolerance);
212 add({ type: 'move', x, y });
213 } else if (item.type === 'close') {
214 add({ type: 'close' });
215 } else {
216 const stack: Array<readonly [BendSpan, number]> = [[item.span, 0]];
217 while (stack.length) {
218 if (++work > MAX_WORK) throw new RangeError('Path bending exceeded its work budget.');
219 const [span, depth] = stack.pop()!;
220 const b = bendSpanBounds(span);
221 const end = map(bendSpanPoint(span, 1));
222 map(bendSpanPoint(span, 0));
223 const roundoff = checkPrecision(Math.max(scale, Math.abs(b.xmin), Math.abs(b.xmax), Math.abs(b.ymin), Math.abs(b.ymax), ...end.map(Math.abs)), p.tolerance);
224 const error = bound(b, span);
225 if (Number.isFinite(error) && error + roundoff <= p.tolerance) {
226 add({ type: 'line', x: end[0], y: end[1] });
227 continue;
228 }
229 if (depth >= MAX_DEPTH) throw new RangeError('Path bending cannot certify tolerance or guide range due to numerical nonprogress.');
230 const [left, right] = splitBendSpan(span);
231 stack.push([right, depth + 1], [left, depth + 1]);
232 }
233 }
234 }
235 const result = new PathGeometry();
236 if (output.length) result.spliceSegments(0, 0, output);
237 return result;
238 }
239
240 function placement(options: Readonly<PathBendOptions>, length: number): Placement {
241 const frame = options.source;
242 object(frame, 'source frame');
243 const x = finite(frame.x, 'source.x'), y = finite(frame.y, 'source.y');
244 const width = positive(frame.width, 'source.width'), height = finite(frame.height, 'source.height');
245 if (height < 0) throw new RangeError('source.height must be nonnegative.');
246 const align = option(options.align, ['start', 'center', 'end'], 'start', 'align');
247 const fit = option(options.fit, ['none', 'stretch'], 'none', 'fit');
248 const overflow = option(options.overflow, ['error', 'extend', 'wrap'], 'error', 'overflow');
249 const rawBaseline = options.baseline;
250 const inputBaseline = rawBaseline === undefined ? 'center' : rawBaseline;
251 const baseline = typeof inputBaseline === 'number' ? finite(inputBaseline, 'baseline')
252 : y + height * ({ top: 0, center: 0.5, bottom: 1 }[option(inputBaseline, ['top', 'center', 'bottom'], 'center', 'baseline')]);
253 const scale = fit === 'stretch' ? positive(length / width, 'fit scale') : 1;
254 const rawOffset = options.offset, rawNormal = options.normalOffset, rawMaxSegments = options.maxSegments;
255 const anchor = { start: 0, center: 0.5, end: 1 }[align], offset = finite(rawOffset === undefined ? 0 : rawOffset, 'offset');
256 const shift = finite(anchor * (length - scale * width) + offset, 'alignment');
257 const maxSegments = rawMaxSegments === undefined ? 1_000_000 : rawMaxSegments;
258 if (!Number.isSafeInteger(maxSegments) || maxSegments <= 0) throw new RangeError('maxSegments must be a positive safe integer.');
259 return {
260 x, width, fit, anchor, offset, baseline: finite(baseline, 'resolved baseline'), normal: finite(rawNormal === undefined ? 0 : rawNormal, 'normalOffset'),
261 shift, scale, length, tolerance: positive(options.tolerance, 'tolerance'), maxSegments, overflow,
262 };
263 }
264 function checkPrecision(scale: number, tolerance: number): number {
265 const roundoff = scale * Number.EPSILON * 64;
266 if (!Number.isFinite(roundoff) || roundoff >= tolerance / 4) throw new RangeError('Path bending cannot certify tolerance at this coordinate scale.');
267 return roundoff;
268 }
269 function object(value: unknown, name: string): asserts value is Record<string, unknown> {
270 if (value === null || typeof value !== 'object') throw new TypeError(`${name} must be an object.`);
271 }
272 function finite(value: number, name: string): number {
273 if (typeof value !== 'number') throw new TypeError(`${name} must be a number.`);
274 if (!Number.isFinite(value)) throw new RangeError(`${name} must be finite.`);
275 return value;
276 }
277 function positive(value: number, name: string): number {
278 finite(value, name);
279 if (value <= 0) throw new RangeError(`${name} must be positive.`);
280 return value;
281 }
282 function option<T extends string>(value: T | undefined, allowed: readonly T[], fallback: T, name: string): T {
283 const resolved = value === undefined ? fallback : value;
284 if (!allowed.includes(resolved)) throw new TypeError(`Invalid path bending ${name}.`);
285 return resolved;
286 }
287 Documentation version
Section titled “Documentation version”Documentation built with @pibbl/core 0.0.2, revision 272a94a. ALPHA — NOT FOR PRODUCTION USE.