# packages/core/src/lib/geometry/transform-guide.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/transform-guide.ts#L59). [Back to reference](/reference/functions/path-transforms/)
1 import type { MeshTransformOptions } from './transform-mesh.js';
2 import type { EnvelopeGuide, EnvelopeTransformOptions } from './path-transforms.js';
3 import { PathGeometry } from './path-geometry.js';
4 import {
5   bendSpans,
6   bendSpanPoint,
7   bendSpanBounds,
8   splitBendSpan,
9   type BendSpan,
10   type BendPoint,
11 } from './path-bend-spans.js';
12 import {
13   type Jet,
14   type Pair,
15   type Interval,
16   mulI,
17   addI,
18   interval,
19 } from './transform-math.js';
20 
21 /**
22  * A station mapping normalized guide position to normalized arc-length distance along its path.
23  *
24  * @see {@link PathGuideOptions}
25  */
26 export interface PathGuideStation {
27   /** Normalized station position. See {@link PathGuideStation}. */
28   readonly at: number;
29   /** Normalized arc-length distance from 0 to 1. See {@link PathGuideStation}. */
30   readonly distance: number;
31 }
32 /**
33  * Geometry and stations that define how a transformation samples a guide.
34  *
35  * @see {@link PathGeometry}
36  * @see {@link PathGuideStation}
37  * @see {@link PathGuide}
38  */
39 export interface PathGuideOptions {
40   /** Path geometry used by this operation. See {@link PathGeometry}. */
41   readonly path: PathGeometry;
42   /** Whether to reverse the direction of the mapping or guide. See {@link PathGuideOptions}. */
43   readonly reverse?: boolean;
44   /**
45    * Explicit correspondence between normalized stations and guide distance. See
46    * {@link PathGuideStation}.
47    */
48   readonly stations?: readonly PathGuideStation[];
49 }
50 /**
51  * A geometry path or a path with explicit guide-sampling configuration.
52  *
53  * @see {@link PathGeometry}
54  * @see {@link PathGuideOptions}
55  * @see {@link MeshTransformOptions}
56  * @see {@link EnvelopeTransformOptions}
57  * @see {@link EnvelopeGuide}
58  */
59 export type PathGuide = PathGeometry | PathGuideOptions;
60 export interface GuideSnapshot {
61   readonly spans: readonly BendSpan[];
62   readonly reverse: boolean;
63   readonly stations: readonly PathGuideStation[];
64 }
65 export interface SampledGuide {
66   readonly error: number;
67   readonly length: number;
68   evaluate(t: Jet): Pair;
69 }
70 export function snapshotGuide(input: PathGuide): GuideSnapshot {
71   const options = input instanceof PathGeometry ? { path: input } : input;
72   if (!(options?.path instanceof PathGeometry))
73     throw new TypeError('A guide requires PathGeometry.');
74   if (options.reverse !== undefined && typeof options.reverse !== 'boolean')
75     throw new TypeError('reverse must be boolean.');
76   const spans: BendSpan[] = [];
77   let moves = 0;
78   for (const item of bendSpans(options.path)) {
79     if (item.type === 'move') moves++;
80     else if (item.type === 'close')
81       throw new RangeError('A guide must be one open contour.');
82     else spans.push(item.span);
83   }
84   if (moves !== 1 || !spans.length)
85     throw new RangeError('A guide must be one nonempty open contour.');
86   const stations = (
87     options.stations ?? [
88       { at: 0, distance: 0 },
89       { at: 1, distance: 1 },
90     ]
91   ).map((s) => ({ at: s.at, distance: s.distance }));
92   if (
93     stations.length < 2 ||
94     stations[0].at !== 0 ||
95     stations[0].distance !== 0 ||
96     stations.at(-1)!.at !== 1 ||
97     stations.at(-1)!.distance !== 1 ||
98     stations.some(
99       (s, i) =>
100         !Number.isFinite(s.at) ||
101         !Number.isFinite(s.distance) ||
102         (i > 0 &&
103           (s.at <= stations[i - 1].at ||
104             s.distance <= stations[i - 1].distance)),
105     )
106   ) {
107     throw new RangeError(
108       'Guide stations must strictly increase from (0,0) to (1,1).',
109     );
110   }
111   return { spans, reverse: options.reverse ?? false, stations };
112 }
113 
114 interface Leaf {
115   span: BendSpan;
116   a: BendPoint;
117   b: BendPoint;
118   chord: number;
119   gap: number;
120   sag: number;
121 }
122 function leaf(span: BendSpan): Leaf {
123   const a = bendSpanPoint(span, 0),
124     b = bendSpanPoint(span, 1),
125     chord = Math.hypot(b[0] - a[0], b[1] - a[1]);
126   let upper: number;
127   if ('points' in span)
128     upper = span.points
129       .slice(1)
130       .reduce(
131         (n, p, i) =>
132           n + Math.hypot(p[0] - span.points[i][0], p[1] - span.points[i][1]),
133         0,
134       );
135   else {
136     const arc = span.arc,
137       mid = arc.startAngle + arc.sweep / 2;
138     const speed =
139       Math.abs(arc.sweep) *
140       Math.hypot(
141         -arc.ux * Math.sin(mid) + arc.vx * Math.cos(mid),
142         -arc.uy * Math.sin(mid) + arc.vy * Math.cos(mid),
143       );
144     const bounds = bendSpanBounds(span);
145     upper = speed + Math.hypot(bounds.ddx, bounds.ddy) / 4;
146   }
147   const gap = Math.max(0, upper - chord);
148   // Every point lies in the ellipse with these endpoints and total distance <= upper.
149   const sag = Math.sqrt(gap * (upper + chord)) / 2;
150   return { span, a, b, chord, gap, sag };
151 }
152 
153 export function sampleGuide(
154   snapshot: GuideSnapshot,
155   accuracy: number,
156 ): SampledGuide {
157   let leaves = snapshot.spans.map(leaf);
158   let gap: number, sag: number;
159   for (let depth = 0; ; depth++) {
160     gap = leaves.reduce((sum, p) => sum + p.gap, 0);
161     sag = leaves.reduce((max, p) => Math.max(max, p.sag), 0);
162     if (sag + 3 * gap <= accuracy) break;
163     if (depth >= 30 || leaves.length > 32768)
164       throw new RangeError('Guide approximation exceeded its work limit.');
165     const share = accuracy / (12 * leaves.length);
166     leaves = leaves.flatMap((p) =>
167       p.gap > share || p.sag > accuracy / 4
168         ? splitBendSpan(p.span).map(leaf)
169         : [p],
170     );
171   }
172   const length = leaves.reduce((sum, p) => sum + p.chord, 0);
173   if (!(length > 0) || !Number.isFinite(length))
174     throw new RangeError('Guide length must be finite and nonzero.');
175   let distance = 0;
176   const points: BendPoint[] = [leaves[0].a],
177     knots = [0];
178   for (const p of leaves) {
179     if (!p.chord) continue;
180     distance += p.chord;
181     points.push(p.b);
182     knots.push(distance / length);
183   }
184   knots[knots.length - 1] = 1;
185   if (snapshot.reverse) {
186     points.reverse();
187     knots.reverse();
188     for (let i = 0; i < knots.length; i++) knots[i] = 1 - knots[i];
189   }
190   const stations = snapshot.stations;
191   const remap = (d: number) => {
192     let i = 0;
193     while (i < stations.length - 2 && d > stations[i + 1].distance) i++;
194     const a = stations[i],
195       b = stations[i + 1];
196     return (
197       a.at + ((d - a.distance) * (b.at - a.at)) / (b.distance - a.distance)
198     );
199   };
200   // Include correspondence breaks, not just geometric polyline vertices.
201   const parameters = [...knots.map(remap), ...stations.map((s) => s.at)]
202     .sort((a, b) => a - b)
203     .filter((v, i, a) => !i || v !== a[i - 1]);
204   const values = parameters.map((t) => {
205     let j = 0;
206     while (j < stations.length - 2 && t > stations[j + 1].at) j++;
207     const a = stations[j],
208       b = stations[j + 1];
209     const d =
210       a.distance + ((t - a.at) * (b.distance - a.distance)) / (b.at - a.at);
211     const i = locate(knots, d),
212       f = (d - knots[i]) / (knots[i + 1] - knots[i]);
213     return [
214       points[i][0] + (points[i + 1][0] - points[i][0]) * f,
215       points[i][1] + (points[i + 1][1] - points[i][1]) * f,
216     ] as BendPoint;
217   });
218   return {
219     error: sag + 3 * gap,
220     length,
221     evaluate: (t) => evaluatePolyline(parameters, values, t),
222   };
223 }
224 function locate(knots: readonly number[], t: number): number {
225   let lo = 0,
226     hi = knots.length - 1;
227   while (hi - lo > 1) {
228     const mid = (lo + hi) >>> 1;
229     if (knots[mid] <= t) lo = mid;
230     else hi = mid;
231   }
232   return Math.min(lo, knots.length - 2);
233 }
234 export function evaluatePolyline(
235   knots: readonly number[],
236   points: readonly BendPoint[],
237   t: Jet,
238 ): Pair {
239   const first = locate(knots, t.v[0]),
240     last = locate(knots, t.v[1]);
241   return [0, 1].map((axis) => {
242     let low = Infinity,
243       high = -Infinity,
244       slopeLow = Infinity,
245       slopeHigh = -Infinity;
246     for (let i = first; i <= last; i++) {
247       const slope =
248         (points[i + 1][axis] - points[i][axis]) / (knots[i + 1] - knots[i]);
249       const a = i === first ? t.v[0] : knots[i],
250         b = i === last ? t.v[1] : knots[i + 1];
251       const va = points[i][axis] + (a - knots[i]) * slope,
252         vb = points[i][axis] + (b - knots[i]) * slope;
253       low = Math.min(low, va, vb);
254       high = Math.max(high, va, vb);
255       slopeLow = Math.min(slopeLow, slope);
256       slopeHigh = Math.max(slopeHigh, slope);
257     }
258     const slopes: Interval = [slopeLow, slopeHigh];
259     return {
260       v: [low, high] as Interval,
261       d: mulI(slopes, t.d),
262       dd: addI(
263         mulI(slopes, t.dd),
264         first === last || slopeLow === slopeHigh
265           ? interval(0)
266           : [-Infinity, Infinity],
267       ),
268     };
269   }) as unknown as Pair;
270 }
271
## Documentation version Documentation built with @pibbl/core 0.0.2, revision 272a94a. ALPHA — NOT FOR PRODUCTION USE.