Sketch splines: length, nearest point, polyline and offset
The length of a sketch spline, the point on it nearest a given point, its points within a chord tolerance, and its offset curve.
How the precision is kept
These results have no closed form for a cubic spline, so each is computed to a stated rule or tolerance in 64-bit arithmetic. Length is a fixed Gauss rule, the nearest point is a sampled start refined by Newton's method, and an offset is a new fit spline checked against sampled points of the true offset.
Calculations under this policy
4 calculations in 1 source file. The code is read from the released app when this page loads. It is the calculation people run, not a copy kept for this page.
Points along a spline such that every chord stays within a tolerance of the curve.
split a piece while the curve at ¼, ½ or ¾ of it is farther than tol from its chord
The deviation is checked at three points of each piece, not at its true maximum, and the recursion stops at depth 14 even if the tolerance is not met. Each span starts as 4 pieces.
sketch-spline.js
lines 252 to 271
PartCraft 0.8.1
/** Points with every chord within `tol` of the curve (checked at chord quarter points), ends included. */
export function tessellateTol(c, tol) {
const out = [];
const rec = (u0, p0, u1, p1, depth) => {
let worst = 0;
for (const f of [0.25, 0.5, 0.75]) {
const q = pointAt(c, u0 + (u1 - u0) * f);
const dx = p1[0] - p0[0], dy = p1[1] - p0[1], l = Math.hypot(dx, dy);
const d = l > 0 ? Math.abs(dx * (q[1] - p0[1]) - dy * (q[0] - p0[0])) / l : Math.hypot(q[0] - p0[0], q[1] - p0[1]);
worst = Math.max(worst, d);
}
if (worst <= tol || depth > 14) { out.push(p1); return; }
const um = (u0 + u1) / 2, pm = pointAt(c, um);
rec(u0, p0, um, pm, depth + 1); rec(um, pm, u1, p1, depth + 1);
};
const sp = spans(c);
out.push(pointAt(c, sp[0][0]));
for (const [u0, u1] of sp) for (let i = 0; i < 4; i++) { const a = u0 + (u1 - u0) * i / 4, b = u0 + (u1 - u0) * (i + 1) / 4; rec(a, pointAt(c, a), b, pointAt(c, b), 0); }
return out;
}
Length of a spline
64-bit
The arc length of a spline.
L = Σ over 8 pieces per span of Σ wᵢ × h × |C′(uᵢ)| (5-point Gauss–Legendre)
The nodes and weights are computed from their closed forms with Math.sqrt, not typed as rounded decimals. The speed of a cubic is not a polynomial, so the rule has a method error that depends on how sharply the curve bends within a piece.
sketch-spline.js
lines 285 to 294
PartCraft 0.8.1
/** Arc length (Gauss–Legendre, 5 points per span; not exact — a cubic's speed is not a polynomial). */
export function arcLength(c) {
const G5 = [[0, 128 / 225], [Math.sqrt(5 - 2 * Math.sqrt(10 / 7)) / 3, (322 + 13 * Math.sqrt(70)) / 900], [Math.sqrt(5 + 2 * Math.sqrt(10 / 7)) / 3, (322 - 13 * Math.sqrt(70)) / 900]];
let s = 0;
for (const [u0, u1] of spans(c)) for (let i = 0; i < 8; i++) {
const a = u0 + (u1 - u0) * i / 8, b = u0 + (u1 - u0) * (i + 1) / 8, h = (b - a) / 2, m = (a + b) / 2;
for (const [g, w] of G5) for (const sg of g ? [-1, 1] : [1]) { const d = derivsAt(c, m + sg * h * g, 1)[1]; s += w * h * Math.hypot(d[0], d[1]); }
}
return s;
}
Nearest point on a spline
64-bit
The parameter of the point on a spline nearest a given point.
start at the nearest of 13 samples per span; Newton: u ← u − ((C − p) · C′) ÷ (C′ · C′ + (C − p) · C″)
Newton runs at most 30 steps and stops when the step is under 1e-15 × max(1, |u|); it also stops when the denominator is not positive. On an open curve the parameter is clamped to the ends.
sketch-spline.js
lines 296 to 316
PartCraft 0.8.1
/** Parameter of the point on the curve nearest p (sampled, then Newton on (C − p)·C′ = 0). */
export function closestParam(c, p, perSpan = 12) {
const [lo, hi] = domain(c);
let best = lo, bd = Infinity;
for (const [u0, u1] of spans(c)) for (let i = 0; i <= perSpan; i++) {
const u = u0 + (u1 - u0) * i / perSpan, q = pointAt(c, u), d = (q[0] - p[0]) ** 2 + (q[1] - p[1]) ** 2;
if (d < bd) { bd = d; best = u; }
}
let u = best;
for (let it = 0; it < 30; it++) {
const [q, d1, d2] = derivsAt(c, u, 2);
const r = [q[0] - p[0], q[1] - p[1]];
const f = r[0] * d1[0] + r[1] * d1[1], df = d1[0] * d1[0] + d1[1] * d1[1] + r[0] * d2[0] + r[1] * d2[1];
if (!(df > 0)) break;
let un = u - f / df;
if (c.periodic) { const T = hi - lo; while (un < lo) un += T; while (un > hi) un -= T; } else un = Math.max(lo, Math.min(hi, un));
if (Math.abs(un - u) < 1e-15 * Math.max(1, Math.abs(u))) { u = un; break; }
u = un;
}
return u;
}
Offset of a spline
64-bit
A new fit spline that follows a spline at a fixed distance, with the largest gap found.
true offset point = C(u) + d × n(u); err = max over 40 points per span of the distance to the fitted curve; accept when err ≤ tol
The offset is an approximation by design: the number of fit points per span is doubled from 2 to 64 until the gap at the checked points is within the tolerance, else an error is raised. The unit normal divides by the curve's speed, which is not checked for zero. The gap that was reached is returned with the result.
sketch-spline.js
lines 388 to 422
PartCraft 0.8.1
/**
* Offset of c by d to its left (d < 0: right), approximated by a fit spline through points on the true
* offset, ends tangent to it. Doubles the samples until the largest gap (closest-point distance from 400+
* points of the true offset) is within tol. → { Q, a0, a1, closed, err, curve } or throws (the bend is too
* tight for d, or the tolerance cannot be met).
*/
export function offsetFit(c, d, tol) {
const sp = spans(c);
const off = (u) => {
const [q, t] = derivsAt(c, u, 1), l = Math.hypot(t[0], t[1]);
return [q[0] - d * t[1] / l, q[1] + d * t[0] / l];
};
// the tightest bend on the offset side
for (const [u0, u1] of sp) for (let i = 0; i <= 32; i++) {
const k = curvatureAt(c, u0 + (u1 - u0) * i / 32);
if (k * d > 0 && Math.abs(d) >= 1 / Math.abs(k) - 1e-12) throw new Error(tr('model.sketch_spline.offset_too_big', { r: +(1 / Math.abs(k)).toFixed(3) }));
}
const closed = !!c.periodic;
const truth = [];
for (const [u0, u1] of sp) for (let i = 0; i < 40; i++) truth.push(off(u0 + (u1 - u0) * (i + 0.5) / 40));
const angle = (u) => { const t = derivsAt(c, u, 1)[1]; return Math.atan2(t[1], t[0]); };
const [lo, hi] = domain(c);
for (let per = 2; per <= 64; per *= 2) {
const Q = [];
for (const [u0, u1] of sp) for (let i = 0; i < per; i++) Q.push(off(u0 + (u1 - u0) * i / per));
if (!closed) Q.push(off(hi));
const opts = closed ? { closed: true } : { a0: angle(lo), a1: angle(hi) };
let fit;
try { fit = interpFit(Q, opts); } catch { continue; }
let err = 0;
for (const p of truth) { const q = pointAt(fit, closestParam(fit, p, 6)); err = Math.max(err, Math.hypot(q[0] - p[0], q[1] - p[1])); }
if (err <= tol) return { Q, a0: opts.a0 ?? null, a1: opts.a1 ?? null, closed, err, curve: fit };
}
throw new Error(tr('model.sketch_spline.offset_tolerance', { tol }));
}
In detail
Method
5-point Gauss–Legendre on 8 pieces per knot span for length; sampling plus Newton on (C − p) · C′ = 0 for the nearest point; recursive halving with the chord checked at quarter points; offset by fitting through 2 to 64 points per span of the true offset.
Number types
64-bit numbers in plain arrays.
Tolerances
Nearest point: Newton stops when the step is under 1e-15 × max(1, |u|) or after 30 steps. Polyline: recursion depth capped at 14. Offset: accepted when the largest gap at the checked points is within the tolerance given (0.001 mm from the sketch offset tool); refused when the offset reaches the radius of curvature less 1e-12.
Limits
Length is not exact; the code comment says so. The offset error is measured at 40 points per span, not everywhere. The nearest point can be a local one when the start sample lands near another part of the curve.
Approach: 64-bit, stated limit
The arithmetic is 64-bit, but the method or the data sets the accuracy: a solver tolerance, a mesh, a step size, a datum shift, a table. The limit is stated where the result is shown.