Breaks every drawing object into straight segments and arcs and works out points, parameters, lengths, bounds, tangent points and snap points on them.
How the precision is kept
A line keeps its end coordinates and an arc its center, radius and two angles as 64-bit numbers. A polyline's arc segment is rebuilt from its two vertices and the bulge each time it is needed. Decisions use fixed tolerances: 1e-9 on lengths and angles, 1e-12 on bulges, and 1e-7 when deciding whether an intersection lies on a piece.
Calculations under this policy
12 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 center, radius and angles of a polyline's arc segment from its two vertices and its bulge.
θ = 4·atan(b); r = |c ÷ (2·sin(θ ÷ 2))|; h = r·cos(θ ÷ 2); center = chord midpoint ± h along the chord's normal
The start and end angles are taken with atan2 from each vertex minus the computed center. For a nearly flat arc the radius is much larger than the chord, so that subtraction, and any point later computed from center, radius and angle, carries rounding in proportion to the radius and not to the chord. The function divides by the chord length without a guard; polyPrims only calls it for a chord longer than 1e-9.
geom.js
lines 39 to 54
CadCraft 0.8.2
/** The arc between p and q for bulge b (tan of a quarter of the included angle; + = CCW). */
export function bulgeArc(p, q, b) {
const theta = 4 * Math.atan(b);
const c = dist(p, q);
const r = Math.abs(c / (2 * Math.sin(theta / 2)));
const mid = { x: (p.x + q.x) / 2, y: (p.y + q.y) / 2 };
const h = r * Math.cos(theta / 2); // centre distance from the chord (signed by bulge)
const ux = (q.x - p.x) / c, uy = (q.y - p.y) / c;
const s = b > 0 ? 1 : -1;
const cx = mid.x - uy * h * s, cy = mid.y + ux * h * s;
let a0 = Math.atan2(p.y - cy, p.x - cx), a1 = Math.atan2(q.y - cy, q.x - cx);
if (b < 0) [a0, a1] = [a1, a0]; // stored CCW either way
a0 = normAngle(a0); a1 = normAngle(a1);
if (a1 <= a0) a1 += TAU;
return { k: 'A', cx, cy, r, a0, a1, rev: b < 0 };
}
Angle on an arc
64-bit
Whether an angle lies on the counter-clockwise sweep of an arc.
d = (a − a0) mod 2π; on the arc when d ≤ sweep + tol or d ≥ 2π − tol
The tolerance is 1e-9 rad by default and absolute. A sweep within the tolerance of a full turn accepts every angle.
geom.js
lines 28 to 34
CadCraft 0.8.2
/** Is angle `a` on the CCW sweep a0 → a1 (with a small tolerance)? */
export function onSweep(a, a0, a1, tol = 1e-9) {
const sweep = a1 - a0;
if (sweep >= TAU - tol) return true;
const d = normAngle(a - a0);
return d <= sweep + tol || d >= TAU - tol;
}
Arc angle range
64-bit
Puts an arc's two stored angles in counter-clockwise order with the end after the start.
a0, a1 reduced to [0, 2π); a1 += 2π when a1 ≤ a0 + 1e-9
Angles are reduced with the % operator on 2π (Math.PI × 2). An end angle within 1e-9 rad after the start angle gets a full turn added, so an arc with a sweep under 1e-9 rad is handled as a full circle.
The straight and arc pieces of a polyline, one per pair of vertices.
A segment is an arc when |bulge| > 1e-12 and its chord is longer than 1e-9 drawing units; otherwise it is the straight segment between the two vertices, copied without arithmetic.
geom.js
lines 212 to 221
CadCraft 0.8.2
export function polyPrims(e) {
const v = e.pts, n = v.length, out = [];
const segs = e.closed ? n : n - 1;
for (let i = 0; i < segs; i++) {
const p = v[i], q = v[(i + 1) % n];
if (Math.abs(p.b || 0) > 1e-12 && dist(p, q) > EPS) out.push({ ...bulgeArc(p, q, p.b), seg: i });
else out.push({ k: 'L', x1: p.x, y1: p.y, x2: q.x, y2: q.y, seg: i });
}
return out;
}
Point at a parameter
64-bit
The point a fraction t of the way along a line or arc.
line: p₁ + (p₂ − p₁)·t; arc: c + r·(cos a, sin a), a = a0 + (a1 − a0)·t
One 64-bit expression per coordinate. On a line, p₁ + (p₂ − p₁) is rounded twice, so t = 1 does not return the stored end point bit for bit in every case.
The parameter of the point on a line or arc closest to a given point.
line: t = (q − p₁)·(p₂ − p₁) ÷ |p₂ − p₁|²; arc: t = ((atan2(q − c) − a0) mod 2π) ÷ sweep
A line whose squared length is under 1e-18 returns t = 0 instead of dividing. On an arc, an angle more than 1e-9 rad past the sweep is clamped to the nearer end, or extrapolated when clamping is off.
geom.js
lines 429 to 444
CadCraft 0.8.2
/** Parameter of the point on p closest to q (clamped to [0, 1]). */
export function primParam(p, q, clamp = true) {
if (p.k === 'L') {
const dx = p.x2 - p.x1, dy = p.y2 - p.y1, L = dx * dx + dy * dy;
let t = L < EPS * EPS ? 0 : ((q.x - p.x1) * dx + (q.y - p.y1) * dy) / L;
return clamp ? Math.max(0, Math.min(1, t)) : t;
}
const a = Math.atan2(q.y - p.cy, q.x - p.cx), sweep = p.a1 - p.a0;
let d = normAngle(a - p.a0);
if (d > sweep + EPS) { // outside the sweep: nearest end (or extrapolate)
if (!clamp) return d / sweep;
const after = d - sweep, before = TAU - d;
return after < before ? 1 : 0;
}
return d / sweep;
}
Length of a piece
64-bit
The length of a straight segment or an arc.
line: √(Δx² + Δy²); arc: r × (a1 − a0)
The line uses Math.hypot, a sum of squares, so nothing cancels. The arc is one product of the radius and the stored sweep.
The points where two pieces meet, limited to the pieces themselves unless one is to be treated as unbounded.
Picks the line and line, line and circle or circle and circle solver, then keeps a point only if it lies on each piece within 1e-7 (drawing units along a line plus 1e-9 of its length; radians round an arc). The tolerance is absolute and does not scale with the coordinates.
geom.js
lines 450 to 459
CadCraft 0.8.2
/** Intersections of two primitives (on both). `ext1`/`ext2`: treat as unbounded (line / full circle). */
export function intersect(p, q, ext1 = false, ext2 = false) {
let pts;
if (p.k === 'L' && q.k === 'L') pts = llInter(p, q);
else if (p.k === 'L') pts = lcInter(p, q);
else if (q.k === 'L') pts = lcInter(q, p);
else pts = ccInter(p, q);
const tol = 1e-7;
return pts.filter((x) => (ext1 || onPrim(p, x, tol)) && (ext2 || onPrim(q, x, tol)));
}
Bounds of a piece
64-bit
The smallest box round a line or arc, used for the drawing's extents.
arc: its two ends and each of the points at 0, π ÷ 2, π, 3π ÷ 2 that is on the sweep
A quadrant point counts when its angle is on the sweep within 1e-9 rad. Its coordinates are c + r·cos(k·π ÷ 2) and c + r·sin(k·π ÷ 2); cos(π ÷ 2) evaluates to about 6.1 × 10⁻¹⁷ rather than 0, which moves the other coordinate of that point by about r × 6 × 10⁻¹⁷.
geom.js
lines 506 to 515
CadCraft 0.8.2
export function primBounds(p, b = emptyBounds()) {
if (p.k === 'L') { growPt(b, p.x1, p.y1); growPt(b, p.x2, p.y2); return b; }
const s = primPoint(p, 0), e = primPoint(p, 1);
growPt(b, s.x, s.y); growPt(b, e.x, e.y);
for (let k = 0; k < 4; k++) {
const a = k * Math.PI / 2;
if (onSweep(a, p.a0, p.a1)) growPt(b, p.cx + p.r * Math.cos(a), p.cy + p.r * Math.sin(a));
}
return b;
}
Tangent points from a point
64-bit
The points on a circle where a line from a given point touches it.
a = atan2(p − c); b = acos(r ÷ d); touch points = c + r·(cos(a ± b), sin(a ± b))
A point within 1e-9 drawing units of the circle is returned as its own touch point, and a point more than 1e-9 inside gives none. acos is reached only when d > r + 1e-9, so its argument stays below 1 without a clamp. When the point is close to the circle, r ÷ d is close to 1 and acos of it keeps fewer digits.
geom.js
lines 604 to 610
CadCraft 0.8.2
export function tangentFrom(p, c) {
const dx = p.x - c.cx, dy = p.y - c.cy, d = Math.hypot(dx, dy);
if (d < c.r - EPS) return [];
if (d <= c.r + EPS) return [{ x: p.x, y: p.y }];
const a = Math.atan2(dy, dx), b = Math.acos(c.r / d);
return [a + b, a - b].map((t) => ({ x: c.cx + c.r * Math.cos(t), y: c.cy + c.r * Math.sin(t) }));
}
Lines tangent to two circles
64-bit
The outer and inner lines that touch two circles, as pairs of touch points.
k = (r₁ − s·r₂) ÷ d, s = +1 outer, −1 inner; g = acos(k); n = (cos(base ± g), sin(base ± g)); points = c₁ + r₁·n and c₂ + s·r₂·n
k is clamped to [−1, 1] before acos, and a pair is skipped when |k| > 1 + 1e-12. Centers closer than 1e-9 give no tangents. When the circles nearly touch, k is close to ±1 and acos keeps fewer digits.
geom.js
lines 611 to 625
CadCraft 0.8.2
export function commonTangents(c1, c2) {
const dx = c2.cx - c1.cx, dy = c2.cy - c1.cy, d = Math.hypot(dx, dy);
if (d < EPS) return [];
const out = [], base = Math.atan2(dy, dx);
for (const sgn of [1, -1]) { // 1: outer (same side), −1: inner (crossing between)
const k = (c1.r - sgn * c2.r) / d;
if (Math.abs(k) > 1 + 1e-12) continue;
const g = Math.acos(Math.max(-1, Math.min(1, k)));
for (const t of [base + g, base - g]) {
const n = { x: Math.cos(t), y: Math.sin(t) };
out.push([{ x: c1.cx + c1.r * n.x, y: c1.cy + c1.r * n.y }, { x: c2.cx + sgn * c2.r * n.x, y: c2.cy + sgn * c2.r * n.y }]);
}
}
return out;
}
Object snap points
64-bit
The end, middle, center, quadrant, perpendicular, tangent and nearest points of an object that a new point can be placed on.
middle of a line = (p₁ + p₂) ÷ 2; arc points = c + r·(cos a, sin a)
Line ends are the stored coordinates. Arc ends, the arc's middle and the quadrant points are computed from center, radius and angle with cos and sin. The perpendicular foot on a line is accepted only for a parameter in [0, 1] with no tolerance; the search radius r filters candidates and does not change their coordinates.
geom.js
lines 639 to 678
CadCraft 0.8.2
/** Snap candidates of one entity near q (within r world units). */
export function snapPoints(e, q, r, kinds, blocks, base) {
const out = [];
const add = (kind, p) => { if (kinds.has(kind) && Math.abs(p.x - q.x) <= r && Math.abs(p.y - q.y) <= r) out.push({ kind, x: p.x, y: p.y }); };
if (e.type === 'point') { add('node', e); return out; }
if (e.type === 'text') { add('ins', e); return out; }
if (e.type === 'insert') add('ins', e);
if (UNBOUNDED.has(e.type)) { // no end or mid: only nearest and perpendicular here (intersections come from view.snap)
const p = prims(e)[0];
if (base && kinds.has('perp')) { const t = primParam(p, base, false); if (t >= 0 && t <= 1) add('perp', primPoint(p, t)); }
if (kinds.has('near')) { const n = primPoint(p, primParam(p, q)); if (dist(n, q) <= r) out.push({ kind: 'near', x: n.x, y: n.y }); }
return out;
}
const ps = prims(e, blocks);
for (const p of ps) {
if (p.box) continue;
if (p.k === 'L') {
add('end', { x: p.x1, y: p.y1 }); add('end', { x: p.x2, y: p.y2 });
add('mid', { x: (p.x1 + p.x2) / 2, y: (p.y1 + p.y2) / 2 });
} else {
add('cen', { x: p.cx, y: p.cy });
if (!p.full) { add('end', primPoint(p, 0)); add('end', primPoint(p, 1)); add('mid', primPoint(p, 0.5)); }
for (let k = 0; k < 4; k++) { const a = k * Math.PI / 2; if (onSweep(a, p.a0, p.a1)) add('quad', { x: p.cx + p.r * Math.cos(a), y: p.cy + p.r * Math.sin(a) }); }
}
if (base && kinds.has('perp')) {
if (p.k === 'L') { const t = primParam(p, base, false); if (t >= 0 && t <= 1) add('perp', primPoint(p, t)); }
else { const a = Math.atan2(base.y - p.cy, base.x - p.cx); if (onSweep(a, p.a0, p.a1)) add('perp', { x: p.cx + p.r * Math.cos(a), y: p.cy + p.r * Math.sin(a) }); }
}
if (kinds.has('tan') && p.k === 'A') { // DR.3: from the base point, the touch points on the arc; no base yet: deferred
const c = { cx: p.cx, cy: p.cy, r: p.r };
if (base) { for (const q of tangentFrom(base, c)) if (onSweep(Math.atan2(q.y - p.cy, q.x - p.cx), p.a0, p.a1)) add('tan', q); }
else {
const a = Math.atan2(q.y - p.cy, q.x - p.cx), n = { x: p.cx + p.r * Math.cos(a), y: p.cy + p.r * Math.sin(a) };
if (onSweep(a, p.a0, p.a1) && Math.abs(Math.hypot(q.x - p.cx, q.y - p.cy) - p.r) <= r) out.push({ kind: 'tan', x: n.x, y: n.y, defer: c });
}
}
if (kinds.has('near')) { const n = primPoint(p, primParam(p, q)); if (dist(n, q) <= r) out.push({ kind: 'near', x: n.x, y: n.y }); }
}
return out;
}
In detail
Method
An arc runs counter-clockwise from angle a0 to a1 in radians. A bulge is the tangent of a quarter of the arc's included angle.
Number types
64-bit numbers throughout.
Tolerances
EPS = 1e-9, absolute: drawing units for lengths, radians for angles. A bulge of 1e-12 or less counts as straight. An intersection counts as on a line within 1e-7 drawing units plus 1e-9 of the line's length, and on an arc within 1e-7 rad. Common tangents allow |k| up to 1 + 1e-12.
Limits
The tolerances are absolute, so they do not grow or shrink with the size of the coordinates. An arc shorter than 1e-9 rad is read as a full turn.
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.