Turns the black-and-white pixels of a scanned drawing into lines and arcs, cleans them up, and offers their ends, middles, centers and crossings as snap points.
How the precision is kept
The fitting arithmetic is 64-bit, in pixel coordinates with pixel centers at half-integers. What the result means is set by the tolerances: a fitted line or arc may lie up to the trace tolerance (1.5 pixels by default) from the thinned center line, and the clean-up steps move lines by up to similar amounts to join, square and close them.
Open item. Scale the parallel test in the snap crossing (|d| < 1e-9) to the two segment lengths, as the corner-closing step already does.
Calculations under this policy
10 calculations in 2 source files. 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.
The best straight line through a run of center-line pixels, and how far the worst pixel lies from it.
θ = ½ × atan2(2·Sxy, Sxx − Syy); ends = feet of the first and last points on the line through the centroid
Sums are taken about the centroid, so the squares stay small and the pixel offset of the window does not enter. The direction comes from one Math.atan2. The deviation reported is the largest perpendicular distance.
raster/trace.js
lines 205 to 229
CadCraft 0.8.2
// ------------------------------------------------------------------------------------------------ fitting
function lineFit(P, i, j) {
const n = j - i + 1;
let mx = 0, my = 0;
for (let k = i; k <= j; k++) { mx += P[k][0]; my += P[k][1]; }
mx /= n; my /= n;
let sxx = 0, sxy = 0, syy = 0;
for (let k = i; k <= j; k++) { const dx = P[k][0] - mx, dy = P[k][1] - my; sxx += dx * dx; sxy += dx * dy; syy += dy * dy; }
const th = 0.5 * Math.atan2(2 * sxy, sxx - syy), ux = Math.cos(th), uy = Math.sin(th);
let dev = 0, t0 = Infinity, t1 = -Infinity;
for (let k = i; k <= j; k++) {
const dx = P[k][0] - mx, dy = P[k][1] - my, t = dx * ux + dy * uy, d = Math.abs(-dx * uy + dy * ux);
if (d > dev) dev = d;
if (t < t0) t0 = t; if (t > t1) t1 = t;
}
// orient from the first point to the last
const f = (P[j][0] - P[i][0]) * ux + (P[j][1] - P[i][1]) * uy;
const s = f < 0 ? -1 : 1;
const a = s > 0 ? t0 : -t1, b = s > 0 ? t1 : -t0;
const dxu = ux * s, dyu = uy * s;
// the ends are the first and last points' feet on the line
const tf = (P[i][0] - mx) * dxu + (P[i][1] - my) * dyu, tl = (P[j][0] - mx) * dxu + (P[j][1] - my) * dyu;
void a; void b;
return { type: 'L', dev, x1: mx + dxu * tf, y1: my + dyu * tf, x2: mx + dxu * tl, y2: my + dyu * tl, ux: dxu, uy: dyu, mx, my };
}
Circle fit
64-bit
The best circle through a run of center-line pixels, its sweep and the angles of an arc.
Kåsa: solve the 2 × 2 system for the center about the centroid, r = √(uc² + vc² + (Suu + Svv) ÷ n); then Gauss-Newton on d − r
The algebraic fit is refused when its determinant is below 1e-9, an absolute value in pixel units to the fourth power. It is followed by a fixed 6 Gauss-Newton steps solved by Cramer's rule, with no convergence test. The fit is rejected when any point lies beyond the tolerance, when the sweep is under 0.12 rad, or when the arc rises less than 2.5 × tolerance above its chord.
raster/trace.js
lines 231 to 290
CadCraft 0.8.2
function circleFit(P, i, j, tol, maxR) {
const n = j - i + 1;
if (n < 5) return null;
let mx = 0, my = 0;
for (let k = i; k <= j; k++) { mx += P[k][0]; my += P[k][1]; }
mx /= n; my /= n;
let suu = 0, suv = 0, svv = 0, suuu = 0, svvv = 0, suvv = 0, svuu = 0;
for (let k = i; k <= j; k++) {
const u = P[k][0] - mx, v = P[k][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-9) return null;
const b1 = 0.5 * (suuu + suvv), b2 = 0.5 * (svvv + svuu);
const uc = (b1 * svv - b2 * suv) / det, vc = (b2 * suu - b1 * suv) / det;
let cx = mx + uc, cy = my + vc, r = Math.sqrt(uc * uc + vc * vc + (suu + svv) / n);
if (!(r > 2 * tol) || r > maxR || !Number.isFinite(r)) return null;
// Kåsa's fit leans on short arcs: a few Gauss–Newton steps on the true distances (cx, cy, r)
for (let it = 0; it < 6; it++) {
let a11 = 0, a12 = 0, a13 = 0, a22 = 0, a23 = 0, a33 = 0, g1 = 0, g2 = 0, g3 = 0;
for (let k = i; k <= j; k++) {
const dx = P[k][0] - cx, dy = P[k][1] - cy, d = Math.hypot(dx, dy) || 1e-9, ux = dx / d, uy = dy / d, e = d - r;
a11 += ux * ux; a12 += ux * uy; a13 += ux; a22 += uy * uy; a23 += uy; a33 += 1;
g1 += -ux * e; g2 += -uy * e; g3 += e;
}
// J = [-ux, -uy, -1]; normal equations (JᵀJ) δ = −Jᵀe
const D = a11 * (a22 * a33 - a23 * a23) - a12 * (a12 * a33 - a23 * a13) + a13 * (a12 * a23 - a22 * a13);
if (Math.abs(D) < 1e-12) break;
const b1 = -g1, b2 = -g2, b3 = -g3; // −Jᵀe = (Σ ux·e, Σ uy·e, Σ e)
const dcx = (b1 * (a22 * a33 - a23 * a23) - a12 * (b2 * a33 - a23 * b3) + a13 * (b2 * a23 - a22 * b3)) / D;
const dcy = (a11 * (b2 * a33 - a23 * b3) - b1 * (a12 * a33 - a23 * a13) + a13 * (a12 * b3 - b2 * a13)) / D;
const dr = (a11 * (a22 * b3 - b2 * a23) - a12 * (a12 * b3 - b2 * a13) + b1 * (a12 * a23 - a22 * a13)) / D;
if (!Number.isFinite(dcx + dcy + dr)) break;
cx += dcx; cy += dcy; r += dr;
}
if (!(r > 2 * tol) || r > maxR || !Number.isFinite(r)) return null;
let dev = 0, prev = Math.atan2(P[i][1] - cy, P[i][0] - cx), total = 0, neg = 0, pos = 0;
const back = 2 * tol / r;
const steps = [];
for (let k = i; k <= j; k++) {
const d = Math.abs(Math.hypot(P[k][0] - cx, P[k][1] - cy) - r);
if (d > dev) dev = d;
if (dev > tol) return null;
if (k > i) {
let da = Math.atan2(P[k][1] - cy, P[k][0] - cx) - prev;
while (da > Math.PI) da -= 2 * Math.PI;
while (da < -Math.PI) da += 2 * Math.PI;
steps.push(da); total += da; prev += da;
if (da > 0) pos++; else if (da < 0) neg++;
}
}
const sgn = total < 0 ? -1 : 1, sweep = Math.abs(total);
for (const da of steps) if (da * sgn < -back) return null; // doubles back: not one arc
if (sweep < 0.12 || sweep > 2 * Math.PI + 0.35) return null;
if (r * (1 - Math.cos(Math.min(sweep, Math.PI) / 2)) < 2.5 * tol) return null; // barely bent: that is a line with a ragged end, not an arc
void pos; void neg;
const a0 = Math.atan2(P[i][1] - cy, P[i][0] - cx);
const ang = sgn > 0 ? [a0, a0 + sweep] : [a0 - sweep, a0];
return { type: 'A', dev, cx, cy, r, a0: ang[0], a1: ang[1], sweep };
}
Corner detection
64-bit
Where a chain of pixels turns sharply, so it can be cut there before fitting.
turn = |atan2(r − q) − atan2(q − p)| over ± w steps; corner when turn ≥ 0.6 rad and largest nearby
Turning angles are stored in a Float64Array and wrapped to (−π, π]. The threshold of 0.6 rad and the window of 3 × tolerance + 2 steps (at least 5) are fixed choices.
raster/trace.js
lines 292 to 316
CadCraft 0.8.2
/** Indices where a chain turns sharply (more than `minTurn` radians over ±w steps), the sharpest of each bunch. */
function findCorners(P, w, minTurn, loop) {
const n = loop ? P.length - 1 : P.length, out = [];
if (n < 2 * w + 1) return out;
const at = (k) => P[loop ? ((k % n) + n) % n : k];
const turn = new Float64Array(n);
for (let k = loop ? 0 : w; k < (loop ? n : n - w); k++) {
const p = at(k - w), q = at(k), r = at(k + w);
let d = Math.atan2(r[1] - q[1], r[0] - q[0]) - Math.atan2(q[1] - p[1], q[0] - p[0]);
while (d > Math.PI) d -= 2 * Math.PI;
while (d < -Math.PI) d += 2 * Math.PI;
turn[k] = Math.abs(d);
}
for (let k = loop ? 0 : w; k < (loop ? n : n - w); k++) {
if (turn[k] < minTurn) continue;
let best = true;
for (let m = -w; m <= w && best; m++) {
const j = loop ? ((k + m) % n + n) % n : k + m;
if (j < 0 || j >= n || j === k) continue;
if (turn[j] > turn[k] || (turn[j] === turn[k] && j < k)) best = false;
}
if (best) out.push(k);
}
return out;
}
Splitting a chain into lines and arcs
64-bit
Fits a line, else an arc, else splits the chain at the point farthest from its chord, and joins neighbors that fit as one.
distance to chord = |(P − A) × (B − A)| ÷ |B − A|
A piece is accepted when its largest deviation is at or below the tolerance. The chord distance uses a cross product divided by the chord length, with a point-distance fallback when the chord is shorter than 1e-9.
raster/trace.js
lines 318 to 355
CadCraft 0.8.2
/** Fit chain points P[i..j] (inclusive) as lines and arcs → pieces [{ ...fit, i, j }]. */
function fitRange(P, i, j, tol, arcs, maxR, out) {
const stack = [[i, j]];
const pieces = [];
while (stack.length) {
const [a, b] = stack.pop();
if (b - a < 1) continue;
if (b - a === 1) { const f = lineFit(P, a, b); f.i = a; f.j = b; pieces.push(f); continue; }
const lf = lineFit(P, a, b);
if (lf.dev <= tol) { lf.i = a; lf.j = b; pieces.push(lf); continue; }
if (arcs) { const cf = circleFit(P, a, b, tol, maxR); if (cf) { cf.i = a; cf.j = b; pieces.push(cf); continue; } }
// split at the point farthest from the chord
const cx = P[b][0] - P[a][0], cy = P[b][1] - P[a][1], cl = Math.hypot(cx, cy) || 1;
let m = a + 1, md = -1;
for (let k = a + 1; k < b; k++) {
const d = cl > 1e-9 ? Math.abs((P[k][0] - P[a][0]) * cy - (P[k][1] - P[a][1]) * cx) / cl : Math.hypot(P[k][0] - P[a][0], P[k][1] - P[a][1]);
if (d > md) { md = d; m = k; }
}
stack.push([m, b], [a, m]);
}
pieces.sort((p, q) => p.i - q.i);
// neighbours that fit as one: join them (an arc cut in two by a noisy split, a line cut by a bump)
let again = true;
while (again && pieces.length > 1) {
again = false;
for (let k = 0; k + 1 < pieces.length; k++) {
const p = pieces[k], q = pieces[k + 1];
if (p.type === 'L' && q.type === 'L' && false) continue;
const lf = lineFit(P, p.i, q.j);
if (lf.dev <= tol) { lf.i = p.i; lf.j = q.j; pieces.splice(k, 2, lf); again = true; break; }
if (arcs && (p.type === 'A' || q.type === 'A')) {
const cf = circleFit(P, p.i, q.j, tol, maxR);
if (cf) { cf.i = p.i; cf.j = q.j; pieces.splice(k, 2, cf); again = true; break; }
}
}
}
for (const p of pieces) out.push(p);
}
Joining collinear lines
64-bit
Merges two lines that lie on the same straight line and nearly touch.
Lines merge when their directions differ by at most 0.026 rad, two ends are within the join gap, and both ends of one lie within 1.5 × tolerance of the other's line. The merged line runs between the two extreme end points as they are; it is not fitted again. At most 50 passes.
raster/trace.js
lines 514 to 558
CadCraft 0.8.2
// ------------------------------------------------------------------------------------------------ clean-up of the vector result
function joinCollinear(L, tol, gap) {
const angOf = (l) => Math.atan2(l.y2 - l.y1, l.x2 - l.x1);
let changed = true, guard = 0;
while (changed && guard++ < 50) {
changed = false;
const cell = Math.max(32, gap * 4), grid = new Map();
const key = (x, y) => Math.floor(x / cell) + ',' + Math.floor(y / cell);
L.forEach((l, k) => { for (const [x, y] of [[l.x1, l.y1], [l.x2, l.y2]]) { const s = key(x, y); if (!grid.has(s)) grid.set(s, []); grid.get(s).push(k); } });
const dead = new Set();
for (let a = 0; a < L.length; a++) {
if (dead.has(a)) continue;
const la = L[a];
let merged = false;
for (const [ex, ey] of [[la.x1, la.y1], [la.x2, la.y2]]) {
const cx0 = Math.floor((ex - gap) / cell), cx1 = Math.floor((ex + gap) / cell), cy0 = Math.floor((ey - gap) / cell), cy1 = Math.floor((ey + gap) / cell);
for (let gx = cx0; gx <= cx1 && !merged; gx++) for (let gy = cy0; gy <= cy1 && !merged; gy++) for (const b of grid.get(gx + ',' + gy) || []) {
if (b <= a || dead.has(b)) continue;
const lb = L[b];
let da = Math.abs(angOf(la) - angOf(lb)) % Math.PI; if (da > Math.PI / 2) da = Math.PI - da;
if (da > 0.026) continue; // 1.5°
// close ends?
const ends = [[la.x1, la.y1], [la.x2, la.y2]], ends2 = [[lb.x1, lb.y1], [lb.x2, lb.y2]];
let near = false;
for (const p of ends) for (const q of ends2) if (Math.hypot(p[0] - q[0], p[1] - q[1]) <= gap) near = true;
if (!near) continue;
// same line? every end of b within tol of a's line
const ux = Math.cos(angOf(la)), uy = Math.sin(angOf(la));
const off = (p) => Math.abs((p[0] - la.x1) * -uy + (p[1] - la.y1) * ux);
if (off(ends2[0]) > tol * 1.5 || off(ends2[1]) > tol * 1.5) continue;
const pts = [...ends, ...ends2], t = pts.map((p) => (p[0] - la.x1) * ux + (p[1] - la.y1) * uy);
let lo = 0, hi = 0;
t.forEach((v, i) => { if (v < t[lo]) lo = i; if (v > t[hi]) hi = i; });
la.x1 = pts[lo][0]; la.y1 = pts[lo][1]; la.x2 = pts[hi][0]; la.y2 = pts[hi][1];
dead.add(b); merged = true; changed = true;
break;
}
if (merged) break;
}
if (merged) a--; // look again: it may now reach another
}
if (dead.size) L = L.filter((_, k) => !dead.has(k));
}
return L;
}
Squaring level and plumb lines
64-bit
Makes nearly horizontal and vertical lines exactly so, and gives lines of one wall the same coordinate.
A line within 2° (by default) of level or plumb has both ends set to the mean of its two coordinates. Lines whose coordinates lie within 0.75 × tolerance are then all moved to their length-weighted mean. Both steps change the fitted geometry on purpose, by up to those tolerances.
raster/trace.js
lines 560 to 584
CadCraft 0.8.2
function squareLines(L, tol, deg) {
const lim = deg * Math.PI / 180;
const H = [], V = [];
for (const l of L) {
const dx = l.x2 - l.x1, dy = l.y2 - l.y1, len = Math.hypot(dx, dy);
if (len < 1e-9) continue;
const a = Math.atan2(dy, dx), ah = Math.min(Math.abs(a), Math.PI - Math.abs(a)), av = Math.abs(Math.abs(a) - Math.PI / 2);
if (ah <= lim) { const y = (l.y1 + l.y2) / 2; l.y1 = l.y2 = y; if (l.x1 > l.x2) { const t = l.x1; l.x1 = l.x2; l.x2 = t; } H.push(l); }
else if (av <= lim) { const x = (l.x1 + l.x2) / 2; l.x1 = l.x2 = x; if (l.y1 > l.y2) { const t = l.y1; l.y1 = l.y2; l.y2 = t; } V.push(l); }
}
// one coordinate for lines that lie within tolerance of each other (a long line cut into pieces stays one line)
const align = (list, get, set) => {
list.sort((p, q) => get(p) - get(q));
let i = 0;
while (i < list.length) {
let j = i, sum = 0, w = 0;
while (j < list.length && get(list[j]) - get(list[i]) <= tol * 0.75) { const len = Math.abs(list[j].x2 - list[j].x1) + Math.abs(list[j].y2 - list[j].y1); sum += get(list[j]) * len; w += len; j++; }
const m = sum / (w || 1);
for (let k = i; k < j; k++) set(list[k], m);
i = j;
}
};
align(H, (l) => l.y1, (l, v) => { l.y1 = l.y2 = v; });
align(V, (l) => l.x1, (l, v) => { l.x1 = l.x2 = v; });
}
Closing corners
64-bit
Moves a line end to the point where its line meets a nearby line.
s = ((B₁ − E) × v) ÷ (u × v); new end = E + s·u
A line-line intersection with the moving line's direction as a unit vector. It is skipped when the cross product is below 0.05 of the other line's length (about 3° from parallel), which is scaled to the input. The end moves only when the crossing is within the join gap.
raster/trace.js
lines 586 to 617
CadCraft 0.8.2
function closeCorners(L, gap) {
if (!L.length) return;
const cell = Math.max(32, gap * 6), grid = new Map();
const push = (cx, cy, k) => { const s = cx + ',' + cy; let a = grid.get(s); if (!a) grid.set(s, (a = [])); a.push(k); };
L.forEach((l, k) => {
const x0 = Math.floor((Math.min(l.x1, l.x2) - gap) / cell), x1 = Math.floor((Math.max(l.x1, l.x2) + gap) / cell), y0 = Math.floor((Math.min(l.y1, l.y2) - gap) / cell), y1 = Math.floor((Math.max(l.y1, l.y2) + gap) / cell);
for (let x = x0; x <= x1; x++) for (let y = y0; y <= y1; y++) push(x, y, k);
});
for (let a = 0; a < L.length; a++) {
const la = L[a];
for (const end of [1, 2]) {
const ex = end === 1 ? la.x1 : la.x2, ey = end === 1 ? la.y1 : la.y2, fx = end === 1 ? la.x2 : la.x1, fy = end === 1 ? la.y2 : la.y1;
const dl = Math.hypot(ex - fx, ey - fy);
if (dl < 1e-9) continue;
const ux = (ex - fx) / dl, uy = (ey - fy) / dl;
let best = null;
for (const b of grid.get(Math.floor(ex / cell) + ',' + Math.floor(ey / cell)) || []) {
if (b === a) continue;
const lb = L[b], vx = lb.x2 - lb.x1, vy = lb.y2 - lb.y1, vl = Math.hypot(vx, vy);
if (vl < 1e-9) continue;
const den = ux * vy - uy * vx;
if (Math.abs(den) < 0.05 * vl) continue; // parallel (within ~3°): no corner
// the point on a's line (e + s·u) that lies on b's line
const s = ((lb.x1 - ex) * vy - (lb.y1 - ey) * vx) / den, t = ((lb.x1 - ex) * uy - (lb.y1 - ey) * ux) / den;
if (Math.abs(s) > gap) continue; // the end must be near the crossing
if (t < -gap / vl || t > 1 + gap / vl) continue; // and the crossing near b's length
if (!best || Math.abs(s) < best.s) best = { s: Math.abs(s), x: ex + s * ux, y: ey + s * uy };
}
if (best) { if (end === 1) { la.x1 = best.x; la.y1 = best.y; } else { la.x2 = best.x; la.y2 = best.y; } }
}
}
}
Lines and arcs in image coordinates
64-bit
The traced lines and arcs with the window offset added and the arc end points worked out.
The integer window offset is added to every coordinate, and the arc ends come from the center, radius and angles with Math.cos and Math.sin. Nothing is rounded.
d = (a₂ − a₁) × (b₂ − b₁); t = ((b₁ − a₁) × (b₂ − b₁)) ÷ d; point = a₁ + t·(a₂ − a₁)
The parallel test is |d| < 1e-9, an absolute value in square pixels that is not scaled to the segment lengths. A crossing up to 1.5 px beyond either segment's end is accepted.
raster/snap.js
lines 29 to 36
CadCraft 0.8.2
const segCross = (a, b) => { // two segments → the crossing point strictly inside both, else null
const d = (a.x2 - a.x1) * (b.y2 - b.y1) - (a.y2 - a.y1) * (b.x2 - b.x1);
if (Math.abs(d) < 1e-9) return null;
const t = ((b.x1 - a.x1) * (b.y2 - b.y1) - (b.y1 - a.y1) * (b.x2 - b.x1)) / d, u = ((b.x1 - a.x1) * (a.y2 - a.y1) - (b.y1 - a.y1) * (a.x2 - a.x1)) / d;
const la = Math.hypot(a.x2 - a.x1, a.y2 - a.y1), lb = Math.hypot(b.x2 - b.x1, b.y2 - b.y1), ea = 1.5 / la, eb = 1.5 / lb;
if (t < -ea || t > 1 + ea || u < -eb || u > 1 + eb) return null;
return { x: a.x1 + t * (a.x2 - a.x1), y: a.y1 + t * (a.y2 - a.y1), ta: t, tb: u, la, lb };
};
Snap points of a trace
64-bit
The ends, middles, arc centers, corners and crossings offered for snapping.
middle = (p₁ + p₂) ÷ 2; arc middle at angle (a₀ + a₁) ÷ 2; corner = mean of the ends within 3 px
Ends closer than the join distance (3 px by default) are replaced by their average, so a corner snap point is the mean of the line ends and not their intersection. Middles and arc points are plain 64-bit expressions.
raster/snap.js
lines 38 to 78
CadCraft 0.8.2
/** The snap points of a trace result: [{ x, y, kind }]. `joinDist` = how close two ends are to count as one corner. */
export function snapPointsOf(result, joinDist = 3, cutBox = null) {
const pts = [];
const ends = []; // every end of every line or arc
// a line that runs out of the traced window was cut by it: its end there is not an end, and its middle is not the line's middle
const cutAt = (x, y) => !!cutBox && ((cutBox[0] > 0 && x <= cutBox[0] + 2) || (cutBox[1] > 0 && y <= cutBox[1] + 2) || (cutBox[2] < cutBox[4] && x >= cutBox[2] - 2) || (cutBox[3] < cutBox[5] && y >= cutBox[3] - 2));
for (const l of result.lines) {
const c1 = cutAt(l.x1, l.y1), c2 = cutAt(l.x2, l.y2);
if (!c1) ends.push([l.x1, l.y1]);
if (!c2) ends.push([l.x2, l.y2]);
if (!c1 && !c2) pts.push({ x: (l.x1 + l.x2) / 2, y: (l.y1 + l.y2) / 2, kind: 'mid' });
}
for (const a of result.arcs) {
const c1 = cutAt(a.sx, a.sy), c2 = cutAt(a.ex, a.ey);
if (!c1) ends.push([a.sx, a.sy]);
if (!c2) ends.push([a.ex, a.ey]);
if (c1 || c2) continue;
const m = (a.a0 + a.a1) / 2;
pts.push({ x: a.cx + a.r * Math.cos(m), y: a.cy + a.r * Math.sin(m), kind: 'mid' }, { x: a.cx, y: a.cy, kind: 'cen' });
}
const used = new Array(ends.length).fill(false);
for (let i = 0; i < ends.length; i++) {
if (used[i]) continue;
const grp = [i];
for (let j = i + 1; j < ends.length; j++) if (!used[j] && Math.hypot(ends[i][0] - ends[j][0], ends[i][1] - ends[j][1]) <= joinDist) grp.push(j);
for (const g of grp) used[g] = true;
let x = 0, y = 0;
for (const g of grp) { x += ends[g][0]; y += ends[g][1]; }
pts.push({ x: x / grp.length, y: y / grp.length, kind: grp.length > 1 ? 'int' : 'end' });
}
// crossings and T meetings: an end on another line's body, and lines that cross
const L = result.lines;
for (let i = 0; i < L.length; i++) for (let j = i + 1; j < L.length; j++) {
const c = segCross(L[i], L[j]);
if (!c) continue;
const nearEnd = (c.ta * c.la < joinDist || (1 - c.ta) * c.la < joinDist) && (c.tb * c.lb < joinDist || (1 - c.tb) * c.lb < joinDist);
if (nearEnd) continue; // a corner: already there
pts.push({ x: c.x, y: c.y, kind: 'int' });
}
return pts;
}
In detail
Method
Thinning to center lines (Zhang and Suen, as the file states), least-squares line through the centroid along the principal axis, Kåsa circle fit refined by Gauss-Newton steps, recursive splitting at the farthest point, then joining, squaring and corner closing.
Number types
64-bit numbers for all coordinates and sums; typed integer arrays only for pixel labels.
Tolerances
Fit tolerance 1.5 px (minimum 0.5). Circle: at least 5 points, determinant above 1e-9, 6 Gauss-Newton steps, radius above 2 × tolerance. Join: 1.5° (0.026 rad) and 1.5 × tolerance. Square: 2° and 0.75 × tolerance. Corner: no closing when lines are within about 3° of parallel. Snap crossings: denominator above 1e-9, 1.5 px beyond a segment end.
Limits
Results are in pixels of the scan; real-world size depends on the scale a person sets for the image. Text-sized pieces and hatching are set aside, not traced.
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.