Turns the outline of a flat part in a photo, or the lines of a pen drawing, into sketch lines, arcs and circles in millimeters.
How the precision is kept
The input is a pixel image, so the outline is known to about a pixel and the fitting tolerance (1.5 pixels by default) sets the accuracy of every line, arc and circle. The fits themselves are 64-bit: sums centered on the mean of the points, closed-form solutions, no iteration. The scale is one division of the stated length by the pixel extent, and every coordinate is then one subtraction and one multiplication.
Open item. In pen-drawing mode, measure the extent used for the scale over each arc's real bounding box and refuse a zero extent before dividing by it.
Calculations under this policy
9 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.
Tells an outer outline from a hole and gives the hole size used to drop specks.
a = ½ × Σ (xᵢ·yᵢ₊₁ − xᵢ₊₁·yᵢ); hole kept when 2 × √(|a| ÷ π) ≥ minHole
The corners are whole pixel coordinates, so every term of the sum is a whole number held in a 64-bit number, and the halving is exact. The terms are added in order with no compensation.
photo-sketch.js
line 66
PartCraft 0.8.1
const areaOf = (P) => { let a = 0; for (let i = 0; i < P.length; i++) { const p = P[i], q = P[(i + 1) % P.length]; a += p[0] * q[1] - q[0] * p[1]; } return a / 2; }; // screen y down: clockwise > 0
Outline simplification
64-bit
Keeps only the outline points that lie farther than the tolerance from the chord between their neighbors.
d = |dx·(Qy − Ay) − dy·(Qx − Ax)| ÷ L; keep the farthest point when d > tol
Distances are one 64-bit cross product divided by the chord length from Math.hypot. A chord shorter than 1e-9 pixels falls back to the point-to-point distance, so the division is guarded.
photo-sketch.js
lines 70 to 96
PartCraft 0.8.1
/** Douglas-Peucker on a closed polyline; returns the indices of the vertices kept (at least 3 when it can). */
function simplifyClosed(P, tol) {
const n = P.length;
if (n < 4) return P.map((_, i) => i);
// split at the point farthest from the first, so both halves are open runs
let far = 0, fd = -1;
for (let i = 1; i < n; i++) { const d = (P[i][0] - P[0][0]) ** 2 + (P[i][1] - P[0][1]) ** 2; if (d > fd) { fd = d; far = i; } }
const keep = new Set([0, far]);
const run = (i0, i1) => { // indices on the closed ring from i0 to i1 (inclusive, going forward)
const stack = [[i0, i1]];
while (stack.length) {
const [a, b] = stack.pop();
const len = (b - a + n) % n;
if (len < 2) continue;
const A = P[a], B = P[b], dx = B[0] - A[0], dy = B[1] - A[1], L = Math.hypot(dx, dy);
let best = -1, bi = -1;
for (let k = 1; k < len; k++) {
const i = (a + k) % n, Q = P[i];
const d = L > 1e-9 ? Math.abs(dx * (Q[1] - A[1]) - dy * (Q[0] - A[0])) / L : Math.hypot(Q[0] - A[0], Q[1] - A[1]);
if (d > best) { best = d; bi = i; }
}
if (best > tol) { keep.add(bi); stack.push([a, bi], [bi, b]); }
}
};
run(0, far); run(far, 0);
return [...keep].sort((a, b) => a - b);
}
Circle through outline points
64-bit
The center and radius of the circle that best fits a run of outline points, with its largest and root-mean-square deviation.
u = x − x̄, v = y − ȳ; solve [Σu² Σuv; Σuv Σv²]·(u_c, v_c) = ½·(Σu³ + Σuv², Σv³ + Σvu²); r = mean distance to the center
The points are shifted to their mean before the squares and cubes are summed, which keeps the sums small. The 2 × 2 system is solved by its determinant, and the fit is refused when |det| is under 1e-12; that threshold is absolute, not scaled to the spread of the points. The radius is the mean of the Math.hypot distances to the fitted center.
photo-sketch.js
lines 98 to 117
PartCraft 0.8.1
/** Circle through points by the algebraic (Kåsa) fit: { c: [x, y], r, rms, max } or null. */
export function fitCircle(pts) {
const n = pts.length;
if (n < 3) return null;
let mx = 0, my = 0;
for (const p of pts) { mx += p[0]; my += p[1]; }
mx /= n; my /= n;
let suu = 0, suv = 0, svv = 0, suuu = 0, svvv = 0, suvv = 0, svuu = 0;
for (const p of pts) { const u = p[0] - mx, v = p[1] - my; suu += u * u; suv += u * v; svv += v * v; suuu += u * u * u; svvv += v * v * v; suvv += u * v * v; svuu += v * u * u; }
const det = suu * svv - suv * suv;
if (Math.abs(det) < 1e-12) return null;
const uc = (svv * (suuu + suvv) - suv * (svvv + svuu)) / (2 * det), vc = (suu * (svvv + svuu) - suv * (suuu + suvv)) / (2 * det);
const cx = mx + uc, cy = my + vc;
let r = 0;
for (const p of pts) r += Math.hypot(p[0] - cx, p[1] - cy);
r /= n;
let ss = 0, max = 0;
for (const p of pts) { const d = Math.abs(Math.hypot(p[0] - cx, p[1] - cy) - r); ss += d * d; if (d > max) max = d; }
return { c: [cx, cy], r, rms: Math.sqrt(ss / n), max };
}
Line through outline points
64-bit
The direction of the straight line that best fits a run of outline points, through their centroid.
θ = ½ × atan2(2·Σuv, Σu² − Σv²); d = (cos θ, sin θ)
A closed form on sums taken about the centroid. atan2 takes the two sums directly, so no division is needed and a vertical line is not a special case.
photo-sketch.js
lines 119 to 130
PartCraft 0.8.1
/** Total-least-squares line through points: { p: [x, y] (centroid), d: unit direction, max (largest distance) }. */
export function fitLine(pts) {
let mx = 0, my = 0;
for (const p of pts) { mx += p[0]; my += p[1]; }
mx /= pts.length; my /= pts.length;
let sxx = 0, sxy = 0, syy = 0;
for (const p of pts) { const u = p[0] - mx, v = p[1] - my; sxx += u * u; sxy += u * v; syy += v * v; }
const th = 0.5 * Math.atan2(2 * sxy, sxx - syy), d = [Math.cos(th), Math.sin(th)];
let max = 0;
for (const p of pts) max = Math.max(max, Math.abs(-d[1] * (p[0] - mx) + d[0] * (p[1] - my)));
return { p: [mx, my], d, max };
}
Corner where two fitted lines meet
64-bit
Places a corner of the sketch at the intersection of the two fitted lines on either side of it.
den = u_d × v_d; t = ((v_p − u_p) × v_d) ÷ den; corner = u_p + t·u_d
The directions are unit vectors, so den is the sine of the angle between the lines. Lines closer than 8° are not intersected, which bounds the division. The caller keeps the old corner when the intersection lies more than 3 × tol (4 × tol for a removed sliver) away.
Extends each arc along the outline while the points stay on its circle, fits the circle again and puts the two end points on it.
grow while | |P − c| − r | ≤ min(0.75, tol ÷ 2); end = c + r·(P − c) ÷ |P − c|
The growth test and the projection onto the circle use Math.hypot distances in 64-bit. The projection divides by the distance to the center and replaces a zero distance by 1, so it cannot divide by zero.
photo-sketch.js
lines 203 to 222
PartCraft 0.8.1
const near = Math.min(0.75, tol * 0.5);
const between = (a, b) => { const out = []; for (let k = a, c = 0; c <= n; k = (k + 1) % n, c++) { out.push(P[k]); if (k === b) break; } return out; };
for (const p of pieces) {
if (p.type !== 'arc') continue;
let ia = idx[p.from], ib = idx[p.to % m], cf = fitCircle(p.dense);
const prevV = idx[(p.from + m - 1) % m], nextV = idx[(p.to + 1) % m];
for (const dir of [-1, 1]) {
for (let k = 0; k < n; k++) {
const j = dir < 0 ? (ia - 1 + n) % n : (ib + 1) % n;
if (j === (dir < 0 ? prevV : nextV)) break;
if (Math.abs(Math.hypot(P[j][0] - cf.c[0], P[j][1] - cf.c[1]) - cf.r) > near) break;
if (dir < 0) ia = j; else ib = j;
}
}
p.dense = between(ia, ib);
const cf2 = fitCircle(p.dense);
if (cf2) { p.c = cf2.c; p.r = cf2.r; }
const onCircle = (q) => { const d = Math.hypot(q[0] - p.c[0], q[1] - p.c[1]) || 1; return [p.c[0] + p.r * (q[0] - p.c[0]) / d, p.c[1] + p.r * (q[1] - p.c[1]) / d]; };
V[p.from] = onCircle(P[ia]); V[p.to % m] = onCircle(P[ib]);
}
Squaring of near-horizontal and near-vertical lines
64-bit
Makes a line that is within the squaring angle of horizontal or vertical exactly so, by giving both ends the same coordinate.
angle = |atan2(B_y − A_y, B_x − A_x)| in degrees; shared y = (A_y + B_y) ÷ 2 or shared x = (A_x + B_x) ÷ 2
This changes the fitted geometry on purpose: an end moves to the mean of the values its lines ask for. The angle is converted with π ÷ 180 from Math.PI and compared with the squaring angle (2° by default, 0 turns it off).
photo-sketch.js
lines 304 to 313
PartCraft 0.8.1
if (sq > 0) {
const px = V.map(() => []), py = V.map(() => []);
for (const p of pieces) {
if (p.type !== 'line') continue;
const A = V[p.from], B = V[p.to % V.length], ang = Math.abs(Math.atan2(B[1] - A[1], B[0] - A[0]) / RAD);
if (ang < sq || ang > 180 - sq) { const y = (A[1] + B[1]) / 2; py[p.from].push(y); py[p.to % V.length].push(y); }
else if (Math.abs(ang - 90) < sq) { const x = (A[0] + B[0]) / 2; px[p.from].push(x); px[p.to % V.length].push(x); }
}
V.forEach((v, i) => { if (px[i].length) v[0] = px[i].reduce((s, q) => s + q, 0) / px[i].length; if (py[i].length) v[1] = py[i].reduce((s, q) => s + q, 0) / py[i].length; });
}
Scale of a silhouette
64-bit
Millimeters per pixel from one stated length, and the mapping of pixel coordinates to sketch coordinates.
mm = stated length ÷ pixel extent; X = (x − x₀) × mm; Y = (y₁ − y) × mm
The extent is the width, height or longer side of the outer outline in whole pixel edges, so the scale is one 64-bit division. Each coordinate is one subtraction and one multiplication. The object must be at least 25 pixels, so the extent is not zero here.
Millimeters per pixel for traced pen lines, from one stated length and the extent of the traced lines and arcs.
extent from line ends, arc ends and arc centers; mm = stated length ÷ extent
The extent grows by each arc's start, end and center; the term a.cx − a.r × 0 multiplies the radius by zero, so the bulge of an arc is not counted. The division by the extent is not guarded: a drawing whose traced points share one x (or y) gives an extent of zero.
photo-sketch.js
lines 341 to 347
PartCraft 0.8.1
const grow = (x, y) => { if (x < x0) x0 = x; if (x > x1) x1 = x; if (y < y0) y0 = y; if (y > y1) y1 = y; };
for (const l of tr.lines) { grow(l.x1, l.y1); grow(l.x2, l.y2); }
for (const a of tr.arcs) { grow(a.sx, a.sy); grow(a.ex, a.ey); grow(a.cx - a.r * 0, a.cy); }
const ext = { w: x1 - x0, h: y1 - y0 };
if (typeof opts.mmPerPx === 'number' && opts.mmPerPx > 0) { mm = opts.mmPerPx; scaled = true; }
else if (opts.known && opts.known.mm > 0) { const e = opts.known.of === 'height' ? ext.h : opts.known.of === 'longest' ? Math.max(ext.w, ext.h) : ext.w; mm = opts.known.mm / e; scaled = true; }
const X = (x) => (x - x0) * mm, Y = (y) => (y1 - y) * mm;
In detail
Method
Threshold, largest 8-connected piece, pixel-edge outlines, Douglas-Peucker simplification, corners where the direction turns, circle fit by the algebraic (Kåsa) method, total-least-squares line fit (the file header names these).
Number types
64-bit numbers in plain arrays for all coordinates and sums; Uint8Array and Int32Array only for the pixel mask and the flood-fill stack.
Tolerances
tolPx 1.5 by default, clamped to 0.5 to 20 pixels. Circle fit refused when the determinant is under 1e-12 (absolute, pixel units). A whole outline is one circle when the largest deviation is at most max(tol, 0.9) + 0.5 pixels and the radius is at least 6 pixels. An arc is accepted when the largest deviation is at most tol + 0.35 pixels and the radius at least 2 × tol. Two fitted lines are not intersected when the sine of their angle is under sin 8°. Lines within 2° of horizontal or vertical are squared by default. Zero-length guard 1e-9 pixels in the simplification.
Limits
Accuracy is that of the picture: pixel size, lens distortion and perspective are not corrected. In pen-drawing mode the extent used for the scale takes arc ends and centers, not the bulge of an arc.
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.