Decides what a freehand stroke was meant to be (a line, circle, arc, rectangle or polyline) and makes that exact shape, then joins nearby ends.
How the precision is kept
The arithmetic is 64-bit, but the result follows rules of thumb scaled to the size of the stroke: how straight, how round, how close to level or square. A circle is fitted by least squares about the mean of the points. Lines within a few degrees of level or plumb are made exactly so.
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.
The circle that best fits the stroke's points, with its root-mean-square error.
u = x − x̄, v = y − ȳ; solve [Σu² Σuv; Σuv Σv²]·(u_c, v_c) = ½(Σu³ + Σuv², Σv³ + Σvu²); r² = u_c² + v_c² + (Σu² + Σv²) ÷ n
Coordinates are taken about their mean before the sums are formed, which keeps the sums small wherever the stroke is in the drawing. The 2 × 2 system is refused when |det| < 1e-12, an absolute value that does not scale with the stroke's size. The error is measured afterwards from the fitted circle.
sketch.js
lines 51 to 63
CadCraft 0.8.2
/** Circle through the points by least squares (Kåsa): { cx, cy, r, rms }. */
export function fitCircle(pts) {
let mx = 0, my = 0; for (const p of pts) { mx += p.x; my += p.y; } mx /= pts.length; my /= pts.length;
let suu = 0, svv = 0, suv = 0, suuu = 0, svvv = 0, suvv = 0, svuu = 0;
for (const p of pts) { const u = p.x - mx, v = p.y - my; suu += u * u; svv += v * v; suv += u * 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 a = (suuu + suvv) / 2, b = (svvv + svuu) / 2;
const uc = (a * svv - b * suv) / det, vc = (b * suu - a * suv) / det;
const cx = mx + uc, cy = my + vc, r = Math.sqrt(uc * uc + vc * vc + (suu + svv) / pts.length);
let s = 0; for (const p of pts) { const e = Math.hypot(p.x - cx, p.y - cy) - r; s += e * e; }
return { cx, cy, r, rms: Math.sqrt(s / pts.length) };
}
Turn of a stroke about a center
64-bit
How far the stroke goes round the fitted center, signed.
Σ (aᵢ − aᵢ₋₁) with each step brought into (−π, π]
A sum of atan2 differences added in stroke order, each unwrapped by whole turns.
sketch.js
lines 65 to 74
CadCraft 0.8.2
/** Total turning of the stroke around (cx, cy), radians (signed: + anticlockwise). */
function sweepAround(pts, c) {
let s = 0, prev = Math.atan2(pts[0].y - c.cy, pts[0].x - c.cx);
for (let i = 1; i < pts.length; i++) {
const a = Math.atan2(pts[i].y - c.cy, pts[i].x - c.cx);
let d = a - prev; while (d > Math.PI) d -= TAU; while (d < -Math.PI) d += TAU;
s += d; prev = a;
}
return s;
}
Squaring a direction
64-bit
Makes a direction level or plumb when it is within a few degrees of it.
The squared direction is a whole multiple of π ÷ 2 as a 64-bit number, whose cosine or sine is about 6e-17 and not exactly 0; cleanStroke gives level and plumb lines one shared coordinate instead of using that cosine.
sketch.js
lines 76 to 80
CadCraft 0.8.2
/** A direction (radians) squared to level / plumb when it is within `deg` of one. */
function squareAngle(a, deg) {
const q = Math.round(a / (Math.PI / 2)) * (Math.PI / 2);
return Math.abs(a - q) <= deg * Math.PI / 180 ? q : a;
}
Where two sides meet
64-bit
The corner where two straight sides cross.
det = l × m; t = ((m₀ − l₀) × m) ÷ det; point = l₀ + l·t
Directions are unit vectors from cosine and sine, so the parallel test |det| < 1e-9 is an angle of about 1e-9 rad. When sides are parallel the stroke's own vertex is kept.
sketch.js
lines 83 to 88
CadCraft 0.8.2
function meet(l, m) {
const det = l.dx * m.dy - l.dy * m.dx;
if (Math.abs(det) < 1e-9) return null;
const t = ((m.x - l.x) * m.dy - (m.y - l.y) * m.dx) / det;
return { x: l.x + l.dx * t, y: l.y + l.dy * t };
}
Distance from a point to a segment
64-bit
How far a pen point is from the straight line between two others.
t = ((p − a)·(b − a)) ÷ |b − a|², held to [0, 1]; distance = |p − (a + t(b − a))|
One division, skipped for a zero-length segment, and one hypot.
sketch.js
lines 31 to 35
CadCraft 0.8.2
function distToSeg(p, a, b) {
const dx = b.x - a.x, dy = b.y - a.y, L2 = dx * dx + dy * dy;
const t = L2 ? Math.max(0, Math.min(1, ((p.x - a.x) * dx + (p.y - a.y) * dy) / L2)) : 0;
return Math.hypot(p.x - (a.x + t * dx), p.y - (a.y + t * dy));
}
Straight sides and rectangles
64-bit
Cuts a stroke at its corners, squares each side, and rebuilds the corners where the sides cross.
Each side is a line through the middle of its two corner points at the squared direction. A closed stroke of four sides whose angles are within 12° of right angles is rebuilt with exact multiples of π ÷ 2 from the first side. Corners are recomputed as crossings, so they move off the pen's points.
sketch.js
lines 91 to 125
CadCraft 0.8.2
/**
* Cut a stroke into straight sides and square them. `closed` joins the last side to the first.
* Returns the vertices (closed: without repeating the first).
*/
function sides(pts, eps, o, closed) {
const idx = simplify(pts, eps);
let v = idx.map((i) => pts[i]);
if (closed && v.length > 2) v = v.slice(0, -1); // the last point is the first again
const n = closed ? v.length : v.length - 1;
if (n < 1) return null;
const lines = [];
for (let i = 0; i < n; i++) {
const a = v[i], b = v[(i + 1) % v.length];
const ang = squareAngle(Math.atan2(b.y - a.y, b.x - a.x), o.orthoDeg);
lines.push(lineThrough({ x: (a.x + b.x) / 2, y: (a.y + b.y) / 2 }, ang));
}
// a rectangle drawn crooked keeps its tilt: right angles within rightDeg are made exact against the first side
if (closed && n === 4) {
const a0 = Math.atan2(lines[0].dy, lines[0].dx);
const right = [1, 2, 3].every((k) => { const d = Math.atan2(lines[k].dy, lines[k].dx) - a0; const m = Math.abs(((d % (Math.PI / 2)) + Math.PI / 2) % (Math.PI / 2)); return Math.min(m, Math.PI / 2 - m) <= o.rightDeg * Math.PI / 180; });
if (right) {
for (let k = 1; k < 4; k++) { const q = a0 + Math.round((Math.atan2(lines[k].dy, lines[k].dx) - a0) / (Math.PI / 2)) * (Math.PI / 2); lines[k] = lineThrough(lines[k], q); }
// opposite sides are one distance apart: the middle of each pair
return { rect: true, pts: [0, 1, 2, 3].map((k) => meet(lines[(k + 3) % 4], lines[k]) || v[k]) };
}
}
const out = [];
if (closed) for (let i = 0; i < n; i++) out.push(meet(lines[(i + n - 1) % n], lines[i]) || { ...v[i] });
else {
out.push(project(v[0], lines[0]));
for (let i = 1; i < n; i++) out.push(meet(lines[i - 1], lines[i]) || { ...v[i] });
out.push(project(v[n], lines[n - 1]));
}
return { rect: false, pts: out };
}
A stroke as a line
64-bit
Makes a nearly straight stroke a line, exactly level or plumb when it is close to it.
straight when max distance ≤ max(eps, 3.5 % of the gap) and gap > 90 % of the length
A level or plumb line gets one shared coordinate, the mean of the two ends, so it is exactly level or plumb and not off by the 6e-17 of a rounded cosine. Other squared lines are rebuilt about the midpoint with half the end-to-end distance; lines that are not squared keep the pen's end points.
sketch.js
lines 139 to 148
CadCraft 0.8.2
if (!closed) { // a straight line?
let worst = 0; for (const p of pts) worst = Math.max(worst, distToSeg(p, first, last));
if (worst <= Math.max(eps, gap * 0.035) && gap > L * 0.9) {
const ang = squareAngle(Math.atan2(last.y - first.y, last.x - first.x), o.orthoDeg);
const sq = ang !== Math.atan2(last.y - first.y, last.x - first.x);
const mid = { x: (first.x + last.x) / 2, y: (first.y + last.y) / 2 }, h = gap / 2;
const e = sq ? { type: 'line', x1: mid.x - Math.cos(ang) * h, y1: mid.y - Math.sin(ang) * h, x2: mid.x + Math.cos(ang) * h, y2: mid.y + Math.sin(ang) * h } : { type: 'line', x1: first.x, y1: first.y, x2: last.x, y2: last.y };
if (sq && (Math.abs(Math.cos(ang)) < 1e-9)) { e.x1 = e.x2 = (first.x + last.x) / 2; e.y1 = first.y; e.y2 = last.y; }
else if (sq && (Math.abs(Math.sin(ang)) < 1e-9)) { e.y1 = e.y2 = (first.y + last.y) / 2; e.x1 = first.x; e.x2 = last.x; }
return { kind: 'line', entity: e, score: 1 - worst / Math.max(gap, 1e-9) };
A stroke as a circle or an arc
64-bit
Makes a round stroke a circle, or an arc from the stroke's first point to its last.
accepted when rms ÷ r < 0.07 and r < 3 × box diagonal; circle when |turn| > 0.85 × 2π
Center and radius are the least-squares fit. An arc's end angles are atan2 of the first and last pen points about that center, so the arc's ends lie on the fitted circle in the direction of those points, not on the points themselves.
Pulls each loose end onto the nearest corner of another stroke or of the drawing.
nearest corner with distance ≤ tol; tol = 6 % of the sketch's box diagonal unless given
The end takes the target's coordinates exactly, so joined ends are equal to the last bit. Only the newest 400 visible objects of the drawing are searched unless set otherwise.
sketch.js
lines 206 to 214
CadCraft 0.8.2
made.forEach((m, i) => {
for (const end of endsOf(m.entity)) {
let best = null, bd = tol;
for (let j = 0; j < made.length; j++) {
if (j === i) continue;
for (const c of cornersOf(made[j].entity)) { const d = dist(end.p, c); if (d <= bd) { bd = d; best = c; } }
}
for (const c of targets) { const d = dist(end.p, c); if (d < bd) { bd = d; best = c; } }
if (best) { end.set(best.x, best.y); report[i].joined++; }
In detail
Method
Douglas–Peucker simplification; least-squares circle (Kåsa, named in the code's comment); line crossing by a 2 × 2 determinant; snapping angles to multiples of 90°.
Number types
64-bit numbers.
Tolerances
Defaults: level or plumb within 8°, right angles within 12°, corner tolerance 1.5 % of the stroke's box diagonal, closed when the gap is under 18 % of its length, points thinned at 0.2 % of the diagonal. Circle accepted when rms ÷ r < 0.07. Circle fit refused when |det| < 1e-12 (absolute). Lines parallel when |det| < 1e-9 on unit directions. Ends joined within 6 % of the sketch's diagonal.
Limits
The shape made is a best guess from fixed rules; fitted circles and squared sides do not pass through the pen's points.
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.