Finds a repeat, a stair or a nearly closed figure in the newest objects and offers the next copy, the next steps or the closing sides as geometry that is added to the drawing when accepted.
How the precision is kept
Patterns are found by comparing 64-bit coordinates against tolerances scaled to the pattern: 0.4 % of the step for repeats and stairs, 0.2 % for a running line, 10⁻⁷ of the extent for joining chain ends. The offered geometry is made by adding the last measured step to stored coordinates and is not snapped or rounded. The turning direction of a figure is read from the sign of a cross product after it is rounded to 6 decimals.
Open item. Scale the rounding of the cross product in r6 to the lengths of the two sides instead of a fixed 1e-6.
Calculations under this policy
7 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.
Whether two objects are the same shape on the same layer, apart from their ids.
Every numeric field and every vertex coordinate must agree within the tolerance passed in (absolute difference); bulges must agree within a fixed 1e-3. A line's ends are put in a fixed order first, so direction does not matter.
autocomplete.js
lines 58 to 70
CadCraft 0.8.2
/** Same object, within `tol`, apart from its id? */
function sameShape(a, b, tol) {
if (a.type !== b.type || a.layer !== b.layer) return false;
const x = normal(a), y = normal(b);
for (const k of Object.keys(x)) {
if (k === 'id' || k === 'key') continue;
const u = x[k], v = y[k];
if (num(u)) { if (!num(v) || Math.abs(u - v) > tol) return false; }
else if (k === 'pts') { if (!Array.isArray(v) || v.length !== u.length || u.some((p, i) => Math.abs(p.x - v[i].x) > tol || Math.abs(p.y - v[i].y) > tol || Math.abs((p.b || 0) - (v[i].b || 0)) > 1e-3)) return false; }
else if (u !== v && JSON.stringify(u) !== JSON.stringify(v)) return false;
}
return Object.keys(y).every((k) => k === 'id' || k === 'key' || k in x);
}
Next copy of a repeat
64-bit
The next copy when the last one to four objects were copied at one step twice or more.
step = anchor(B₀) − anchor(A₀); tol = max(10⁻⁶, 0.004 × |step|); next = last group moved by step
The step is the difference between the anchors of the last two groups. Earlier groups are checked against the same step with a tolerance of 0.4 % of its length (at least 1e-6), so drift up to that is accepted and the offered copy continues with the last measured step. The step that is reported is rounded to 6 decimals; the geometry is not.
autocomplete.js
lines 87 to 107
CadCraft 0.8.2
function repeats(recent) {
const n = recent.length, out = [];
for (let m = 1; m <= MAX_PERIOD && 2 * m <= n; m++) {
const A = recent.slice(n - 2 * m, n - m), B = recent.slice(n - m);
const a0 = anchorOf(A[0]), b0 = anchorOf(B[0]);
const dx = b0.x - a0.x, dy = b0.y - a0.y, step = Math.hypot(dx, dy);
if (step < 1e-9) continue;
const tol = Math.max(1e-6, step * 0.004);
if (!A.every((e, i) => sameShape(move(e, dx, dy), B[i], tol))) continue;
let k = 2; // how many groups in a row (more = surer)
while (n - (k + 1) * m >= 0) {
const P = recent.slice(n - (k + 1) * m, n - k * m), Q = recent.slice(n - k * m, n - (k - 1) * m);
if (!P.every((e, i) => sameShape(move(e, dx, dy), Q[i], tol))) break;
k++;
}
const ghosts = B.map((e) => move(e, dx, dy));
out.push({ kind: 'repeat', score: k * 10 - m, ghosts, adds: ghosts, updates: [], step: r6(step), groups: k, size: m });
break; // the smallest period that repeats explains the rest
}
return out;
}
Next period of a stair
64-bit
The next riser and tread of an open polyline whose steps repeat.
dⱼ = pⱼ − pⱼ₋₁; repeats when |dⱼ − dⱼ₋ₚ| ≤ max(10⁻⁶, 0.004 × longest step); new vertex = last vertex + dⱼ
The steps are differences of consecutive vertices and each is compared with the step one period earlier by Math.hypot of the difference. New vertices are a running sum from the last vertex, adding the last period's steps in order, so each new vertex carries the rounding of the additions before it.
autocomplete.js
lines 111 to 136
CadCraft 0.8.2
function stairs(recent) {
const out = [];
for (let i = recent.length - 1; i >= 0 && i >= recent.length - 3; i--) {
const e = recent[i];
if (e.type !== 'poly' || e.closed || e.pts.length < 5) continue;
if (e.pts.some((p) => p.b)) continue;
const d = []; for (let j = 1; j < e.pts.length; j++) d.push({ x: e.pts[j].x - e.pts[j - 1].x, y: e.pts[j].y - e.pts[j - 1].y });
for (let p = 2; p <= MAX_PERIOD * 2; p += 2) { // a stair's period is a riser and a tread (or a multiple)
if (d.length < 2 * p) continue;
const scale = Math.max(...d.slice(-p).map((v) => Math.hypot(v.x, v.y)), 1e-9), tol = Math.max(1e-6, scale * 0.004);
let ok = true;
for (let j = d.length - p; j < d.length && ok; j++) ok = Math.hypot(d[j].x - d[j - p].x, d[j].y - d[j - p].y) <= tol;
if (!ok) continue;
let cur = e.pts[e.pts.length - 1];
const added = [];
for (let j = d.length - p; j < d.length; j++) { cur = { x: cur.x + d[j].x, y: cur.y + d[j].y, b: 0 }; added.push(cur); }
const last = e.pts[e.pts.length - 1];
const ghost = { type: 'poly', closed: false, layer: e.layer, color: e.color ?? null, pts: [{ x: last.x, y: last.y, b: 0 }, ...added] };
const pts = [...e.pts.map((q) => ({ ...q })), ...added];
out.push({ kind: 'stair', score: 12 + d.length / p, ghosts: [ghost], adds: [], updates: [{ id: e.id, entity: { ...e, pts } }], period: p });
break;
}
if (out.length) break;
}
return out;
}
Chain of segments through the newest line
64-bit
The run of connected line and polyline segments that the newest line or polyline belongs to, as an ordered list of vertices.
Two ends are joined when Math.hypot of their difference is within the tolerance passed in (closers passes max(1e-6, 10⁻⁷ × extent)). The chain's vertices are copied from the segment ends as stored; joined ends are not averaged. Polylines with arc segments are left out.
autocomplete.js
lines 140 to 170
CadCraft 0.8.2
/** The chain through the newest line or open polyline: vertices in order, and the objects it is made of. */
function chainThrough(recent, tol) {
const segs = []; // { a, b, e }
for (const e of recent) {
if (e.type === 'line') segs.push({ a: { x: e.x1, y: e.y1 }, b: { x: e.x2, y: e.y2 }, e });
else if (e.type === 'poly' && !e.pts.some((p) => p.b)) {
const n = e.pts.length;
for (let i = 0; i + 1 < n; i++) segs.push({ a: e.pts[i], b: e.pts[i + 1], e });
if (e.closed) segs.push({ a: e.pts[n - 1], b: e.pts[0], e });
}
}
if (!segs.length) return null;
const same = (p, q) => Math.hypot(p.x - q.x, p.y - q.y) <= tol;
const used = new Set();
const lastE = recent.filter((e) => e.type === 'line' || e.type === 'poly').pop();
const first = segs.findIndex((s) => s.e === lastE);
if (first < 0) return null;
let pts = [segs[first].a, segs[first].b]; used.add(first);
for (let grow = true; grow;) {
grow = false;
for (let i = 0; i < segs.length; i++) {
if (used.has(i)) continue;
const s = segs[i], h = pts[0], t = pts[pts.length - 1];
if (same(s.a, t)) { pts.push(s.b); used.add(i); grow = true; }
else if (same(s.b, t)) { pts.push(s.a); used.add(i); grow = true; }
else if (same(s.b, h)) { pts.unshift(s.a); used.add(i); grow = true; }
else if (same(s.a, h)) { pts.unshift(s.b); used.add(i); grow = true; }
}
}
return { pts: pts.map((p) => ({ x: p.x, y: p.y })), parts: [...new Set([...used].map((i) => segs[i].e))], segs: pts.length - 1 };
}
Do two segments cross
64-bit
Whether the closing side would cross another side of the figure.
cross(o, a, b) = (a.x − o.x)(b.y − o.y) − (a.y − o.y)(b.x − o.x); cross when d₁·d₂ < 0 and d₃·d₄ < 0
Four cross products of coordinate differences and two strict sign tests with no tolerance: segments that only touch at an end, or are collinear, are not counted as crossing. The products are ordinary 64-bit arithmetic, so a case within rounding of touching can go either way.
Two sides count as a right angle when the cosine of their angle is within 0.01, about 0.57° either way; the fourth corner is v₀ + (v₂ − v₁), so the figure offered is a parallelogram on the drawn sides and is not squared up. For three or more sides the turning direction is the sign of each cross product after rounding to 6 decimals, an absolute threshold in square drawing units.
autocomplete.js
lines 177 to 211
CadCraft 0.8.2
function closers(recent) {
const out = [];
const ext = boxOf(recent), size = ext ? Math.max(ext.x1 - ext.x0, ext.y1 - ext.y0, 1e-9) : 1, tol = Math.max(1e-6, size * 1e-7);
const ch = chainThrough(recent, tol);
if (!ch || ch.segs < 2) return out;
const v = ch.pts, n = v.length, h = v[0], t = v[n - 1];
if (Math.hypot(h.x - t.x, h.y - t.y) <= tol) return out; // already closed
const last = ch.parts[ch.parts.length - 1], layer = last.layer, color = last.color ?? null;
const side = (a, b) => ({ type: 'line', layer, color, x1: a.x, y1: a.y, x2: b.x, y2: b.y });
const one = ch.parts.length === 1 && ch.parts[0].type === 'poly' ? ch.parts[0] : null; // the whole chain is one polyline
let sides = null;
if (n === 3) { // two sides at a right angle: the rectangle's other two
const u = { x: v[1].x - v[0].x, y: v[1].y - v[0].y }, w = { x: v[2].x - v[1].x, y: v[2].y - v[1].y };
const dot = u.x * w.x + u.y * w.y, lu = Math.hypot(u.x, u.y), lw = Math.hypot(w.x, w.y);
if (lu < 1e-9 || lw < 1e-9 || Math.abs(dot) / (lu * lw) > 0.01) return out;
const p4 = { x: v[0].x + w.x, y: v[0].y + w.y };
sides = { pts: [t, p4], kind: 'rect' };
if (one) { const pts = [...one.pts.map((q) => ({ ...q })), { x: p4.x, y: p4.y, b: 0 }]; out.push({ kind: 'close', score: 14, ghosts: [side(t, p4), side(p4, h)], adds: [], updates: [{ id: one.id, entity: { ...one, pts, closed: true } }], sides: 2 }); }
else out.push({ kind: 'close', score: 14, ghosts: [side(t, p4), side(p4, h)], adds: [side(t, p4), side(p4, h)], updates: [], sides: 2 });
return out;
}
if (n >= 4) { // three or more sides: the closing one, if it winds one way all round (a stair's zig-zag does not) and does not cross
let sign = 0;
for (let i = 1; i + 1 < n; i++) { const c = Math.sign(r6(cross(v[i - 1], v[i], v[i + 1]))); if (c && sign && c !== sign) return out; if (c) sign = c; }
const closing = [v[n - 2], t, h]; const cc = Math.sign(r6(cross(closing[0], closing[1], closing[2]))), c0 = Math.sign(r6(cross(t, h, v[1])));
if ((cc && sign && cc !== sign) || (c0 && sign && c0 !== sign)) return out;
for (let i = 0; i + 1 < n; i++) {
if (i === 0 || i + 1 === n - 1) continue; // the sides that touch the new one
if (segsCross(t, h, v[i], v[i + 1])) return out;
}
if (one) out.push({ kind: 'close', score: 13, ghosts: [side(t, h)], adds: [], updates: [{ id: one.id, entity: { ...one, closed: true } }], sides: 1 });
else out.push({ kind: 'close', score: 13, ghosts: [side(t, h)], adds: [side(t, h)], updates: [], sides: 1 });
}
return out;
}
Next point of a running line
64-bit
The point offered after the points picked so far in LINE or PLINE: the next stair step, a rectangle's fourth corner, the first point again, or one more equal step.
tol = max(10⁻⁶, 0.002 × longest step); square when |u·v| ≤ 0.002 × |u||v|; next = last point + a stored step
Steps are compared by Math.hypot of their difference against the tolerance. Each offered point is a stored point plus a stored step, or the first point itself, so nothing is rounded into it. Cross products are rounded to 6 decimals before their sign is read, an absolute threshold of 5 × 10⁻⁷ square drawing units.
autocomplete.js
lines 297 to 330
CadCraft 0.8.2
/**
* The next point of a LINE or PLINE that is running, from the points picked so far (oldest first) → { x, y, kind } or null.
* stair three or more steps in which each step repeats the one two back (riser, tread, riser…): the step after the last
* rect two sides at a right angle: the fourth corner of the rectangle
* close a rectangle's three sides, or four or more sides that wind one way and do not cross: the first point again
* repeat the last two steps are the same: one more of them
* Rules only (rule 35); the person still clicks or presses Tab.
*/
export function nextPoint(pts) {
const n = Array.isArray(pts) ? pts.length : 0;
if (n < 3) return null;
const v = []; for (let i = 0; i + 1 < n; i++) v.push({ x: pts[i + 1].x - pts[i].x, y: pts[i + 1].y - pts[i].y });
if (v.some((q) => Math.hypot(q.x, q.y) < 1e-9)) return null;
const len = Math.max(...v.map((q) => Math.hypot(q.x, q.y)));
const tol = Math.max(1e-6, len * 0.002);
const last = pts[n - 1], at = (d, kind) => ({ x: last.x + d.x, y: last.y + d.y, kind });
const m = v.length;
if (m >= 3 && near(v[m - 1], v[m - 3], tol) && !near(v[m - 1], v[m - 2], tol)) return at(v[m - 2], 'stair');
const dot = (a, b) => a.x * b.x + a.y * b.y, mag = (a) => Math.hypot(a.x, a.y);
const square = (a, b) => Math.abs(dot(a, b)) <= 0.002 * mag(a) * mag(b);
if (n === 3 && square(v[0], v[1])) return { x: pts[0].x + v[1].x, y: pts[0].y + v[1].y, kind: 'rect' };
if (n === 4 && square(v[0], v[1]) && square(v[1], v[2]) && near(v[2], { x: -v[0].x, y: -v[0].y }, tol)) return { x: pts[0].x, y: pts[0].y, kind: 'close' };
if (m >= 2 && near(v[m - 1], v[m - 2], tol)) return at(v[m - 1], 'repeat');
if (n >= 4) { // winds one way all round, the closing side crosses nothing
let sign = 0;
for (let i = 1; i < m; i++) { const c = Math.sign(r6(v[i - 1].x * v[i].y - v[i - 1].y * v[i].x)); if (c && sign && c !== sign) return null; if (c) sign = c; }
const a = last, b = pts[0];
for (let i = 1; i + 2 < n; i++) if (segsCross(a, b, pts[i], pts[i + 1])) return null;
const cl = { x: b.x - a.x, y: b.y - a.y }, c1 = Math.sign(r6(v[m - 1].x * cl.y - v[m - 1].y * cl.x)), c2 = Math.sign(r6(cl.x * v[0].y - cl.y * v[0].x));
if ((sign && c1 && c1 !== sign) || (sign && c2 && c2 !== sign)) return null;
return { x: b.x, y: b.y, kind: 'close' };
}
return null;
}
In detail
Method
Rules only: the last one to four objects compared with the group before them at one step; a polyline's last steps compared with the steps one period earlier; a chain of segments tested for a missing closing side.
Number types
64-bit numbers.
Tolerances
Repeat: max(1e-6, 0.004 × step) on every coordinate and 1e-3 on a bulge; a step under 1e-9 is ignored. Stair: max(1e-6, 0.004 × the longest step of the period). Close: chain ends join within max(1e-6, 10⁻⁷ × the larger side of the recent objects' box); a right angle when |cos| ≤ 0.01. Running line: max(1e-6, 0.002 × the longest step); a right angle when |u·v| ≤ 0.002 × |u||v|. Cross products are rounded to 1e-6 before their sign is read.
Limits
The 1e-6 floors and the 1e-6 rounding of cross products are absolute (drawing units and square drawing units) and do not scale with the drawing. A repeat continues with the last measured step, including any drift up to the tolerance. The segment crossing test is plain 64-bit arithmetic, not an exact predicate.
Approach: 64-bit, direct
Every value is a 64-bit number from input to result. Formulas are closed form or a direct solve, and every comparison uses a stated tolerance.