Finds the circle of a given radius tangent to two picked lines or circles, and the circle tangent to three.
How the precision is kept
Tangent-tangent-radius is a closed form: the center is where the two objects, each offset by the radius, cross. Tangent-tangent-tangent is solved by Newton's method from 18 starting points for each of 8 sign choices, with a Jacobian from finite differences. Candidates are accepted when they are tangent within a tolerance scaled to the size of the picked objects.
Open item. Refuse a three-tangent result whose Newton iteration did not reach its own stopping tolerance, instead of accepting it within 1e-6 of the objects' size.
Calculations under this policy
8 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.
Reads the picked object as an endless line with a unit direction, or as a full circle.
direction = (p₂ − p₁) ÷ |p₂ − p₁|
The direction is normalized by hypot and one division each; a segment of 1e-9 or less, or a radius of 1e-9 or less, is refused (EPS of geom.js, absolute).
tancircle.js
lines 17 to 31
CadCraft 0.8.2
export function curveAt(e, pick, blocks) {
if (!e) return null;
let best = null, bd = Infinity;
for (const q of prims(e, blocks)) {
if (q.box) continue;
const d = dist(primPoint(q, primParam(q, pick)), pick);
if (d < bd) { bd = d; best = q; }
}
if (!best) return null;
if (best.k === 'L') {
const L = Math.hypot(best.x2 - best.x1, best.y2 - best.y1);
return L > EPS ? { k: 'L', x: best.x1, y: best.y1, dx: (best.x2 - best.x1) / L, dy: (best.y2 - best.y1) / L } : null;
}
return best.r > EPS ? { k: 'C', cx: best.cx, cy: best.cy, r: best.r } : null;
}
Objects offset by the radius
64-bit
A line moved to both sides by r, and a circle grown and shrunk by r.
line: p ± n·r; circle: R + r and |R − r|
One product and one sum per coordinate. An offset circle of radius 1e-9 or less, which happens when the wanted radius equals the picked circle's, is dropped.
tancircle.js
lines 50 to 57
CadCraft 0.8.2
// ---- offsets and their crossings (TTR) ----
function offsets(o, r) {
if (o.k === 'L') {
const nx = -o.dy, ny = o.dx;
return [1, -1].map((s) => ({ k: 'L', x: o.x + nx * r * s, y: o.y + ny * r * s, dx: o.dx, dy: o.dy }));
}
return [o.r + r, Math.abs(o.r - r)].filter((R) => R > EPS).map((R) => ({ k: 'C', cx: o.cx, cy: o.cy, r: R }));
}
Where two offset objects cross
64-bit
The crossing points of two lines, a line and a circle, or two circles.
line–circle: t = −B ± √(B² − C), C = |f|² − r²; circles: l = (r₁² − r₂² + d²) ÷ 2d, h = √(r₁² − l²)
Lines are parallel when |den| < 1e-12 on unit directions. For a line and a circle, C subtracts r² from the squared distance of the line's point to the center, which loses digits when that point is far from the circle. A discriminant just below zero (down to −1e-12 × max(1, r²)) is treated as a tangent, and negative values under the square roots are set to 0.
tancircle.js
lines 58 to 77
CadCraft 0.8.2
function cross(a, b) {
if (a.k === 'L' && b.k === 'L') {
const den = a.dx * b.dy - a.dy * b.dx;
if (Math.abs(den) < 1e-12) return [];
const t = ((b.x - a.x) * b.dy - (b.y - a.y) * b.dx) / den;
return [{ x: a.x + a.dx * t, y: a.y + a.dy * t }];
}
if (a.k === 'C' && b.k === 'L') return cross(b, a);
if (a.k === 'L') { // line × circle
const fx = a.x - b.cx, fy = a.y - b.cy, B = fx * a.dx + fy * a.dy, C = fx * fx + fy * fy - b.r * b.r, D = B * B - C;
if (D < -1e-12 * Math.max(1, b.r * b.r)) return [];
const s = Math.sqrt(Math.max(0, D));
return (s < 1e-12 ? [-B] : [-B + s, -B - s]).map((t) => ({ x: a.x + a.dx * t, y: a.y + a.dy * t }));
}
const dx = b.cx - a.cx, dy = b.cy - a.cy, d = Math.hypot(dx, dy);
if (d < EPS || d > a.r + b.r + 1e-9 * (a.r + b.r) || d < Math.abs(a.r - b.r) - 1e-9 * (a.r + b.r)) return [];
const l = (a.r * a.r - b.r * b.r + d * d) / (2 * d), h = Math.sqrt(Math.max(0, a.r * a.r - l * l));
const mx = a.cx + dx * l / d, my = a.cy + dy * l / d;
return h < 1e-12 ? [{ x: mx, y: my }] : [{ x: mx - dy * h / d, y: my + dx * h / d }, { x: mx + dy * h / d, y: my - dx * h / d }];
}
Is a circle tangent to an object
64-bit
Checks a candidate circle against a line or a circle.
line: | |distance to line| − r | ≤ tol; circle: |d − (R + r)| ≤ tol or |d − |R − r|| ≤ tol
The tolerance is passed in by the caller: 1e-7 × the objects' size for two tangents and ten times that for three.
tancircle.js
lines 43 to 48
CadCraft 0.8.2
/** Is circle c tangent to o (within a relative tolerance)? */
function tangent(o, c, tol) {
if (o.k === 'L') return Math.abs(Math.abs((c.cx - o.x) * o.dy - (c.cy - o.y) * o.dx) - c.r) <= tol;
const d = Math.hypot(c.cx - o.cx, c.cy - o.cy);
return Math.abs(d - (o.r + c.r)) <= tol || Math.abs(d - Math.abs(o.r - c.r)) <= tol;
}
Tangent, tangent, radius
64-bit
The circle of radius r tangent to two picked objects, nearest the picks.
center = crossing of a offset by r and b offset by r; tol = 1e-7 × max(1, size of a, b and r)
Every crossing of the offset pairs is a candidate; it is kept when both tangency checks pass within tol and its center is within 1e9 of the origin. The size used for tol is the distance of each object from the origin plus its radius, so the tolerance grows with distance from the origin.
tancircle.js
lines 89 to 98
CadCraft 0.8.2
export function circleTTR(a, pa, b, pb, r) {
if (!a || !b || !(r > EPS)) return null;
const tol = 1e-7 * scale(a, b, { k: 'C', cx: 0, cy: 0, r });
const cands = [];
for (const oa of offsets(a, r)) for (const ob of offsets(b, r)) for (const q of cross(oa, ob)) {
const c = { cx: q.x, cy: q.y, r };
if (Math.abs(q.x) < FAR && Math.abs(q.y) < FAR && tangent(a, c, tol) && tangent(b, c, tol)) cands.push(c);
}
return nearestToPicks(cands, [[a, pa], [b, pb]]);
}
Newton solve for three tangents
64-bit
Solves the three tangency equations for a circle's center and radius from one starting guess.
F(x, y, r) = 0; J by forward differences with h = 1e-7 × max(1, |x|, |y|, |r|); step = −J⁻¹F by Cramer's rule
The loop stops when every residual is under 1e-13 × max(1, |x|, |y|, r), or after 60 steps without saying which. The Jacobian is a forward difference with that step, so it is approximate; the residuals are evaluated directly in 64-bit. A step longer than 2 × max(1, |r|) is shortened, and a determinant under 1e-18 (absolute) gives up.
tancircle.js
lines 106 to 127
CadCraft 0.8.2
function solve3(os, ss, x, y, r) {
for (let it = 0; it < 60; it++) {
const F = os.map((o, i) => residual2(o, ss[i], x, y, r));
if (F.every((f) => Math.abs(f) < 1e-13 * Math.max(1, Math.abs(x), Math.abs(y), r))) break;
const h = 1e-7 * Math.max(1, Math.abs(x), Math.abs(y), Math.abs(r));
const J = os.map((o, i) => [
(residual2(o, ss[i], x + h, y, r) - F[i]) / h,
(residual2(o, ss[i], x, y + h, r) - F[i]) / h,
(residual2(o, ss[i], x, y, r + h) - F[i]) / h,
]);
const det = (m) => m[0][0] * (m[1][1] * m[2][2] - m[1][2] * m[2][1]) - m[0][1] * (m[1][0] * m[2][2] - m[1][2] * m[2][0]) + m[0][2] * (m[1][0] * m[2][1] - m[1][1] * m[2][0]);
const D = det(J);
if (!Number.isFinite(D) || Math.abs(D) < 1e-18) return null;
const col = (k) => J.map((row, i) => row.map((v, j) => (j === k ? -F[i] : v)));
let dx = det(col(0)) / D, dy = det(col(1)) / D, dr = det(col(2)) / D;
const step = Math.hypot(dx, dy, dr), lim = Math.max(1, Math.abs(r)) * 2;
if (step > lim) { dx *= lim / step; dy *= lim / step; dr *= lim / step; }
x += dx; y += dy; r += dr;
if (!Number.isFinite(x + y + r)) return null;
}
return r > EPS ? { cx: x, cy: y, r } : null;
}
Tangent, tangent, tangent
64-bit
The circle tangent to three picked objects, nearest the picks.
8 sign choices × 18 starting guesses round the picks; kept when tangent to all three within 10 × tol
Each result of solve3 is accepted when it is tangent to all three objects within 10 × tol, that is 1e-6 × the objects' size, so a result that stopped at 60 steps short of convergence can still be returned. Results within 100 × tol of one already found are treated as the same circle.
tancircle.js
lines 128 to 145
CadCraft 0.8.2
export function circleTTT(a, pa, b, pb, c, pc) {
const os = [a, b, c];
if (os.some((o) => !o)) return null;
const tol = 1e-7 * scale(a, b, c);
const seeds = [];
const P = [pa, pb, pc], m = { x: (pa.x + pb.x + pc.x) / 3, y: (pa.y + pb.y + pc.y) / 3 };
const spread = Math.max(1e-6, ...P.map((p) => dist(p, m)));
for (const k of [0.5, 1, 2]) for (let i = 0; i < 6; i++) { const t = i * Math.PI / 3; seeds.push([m.x + Math.cos(t) * spread * (k - 0.5), m.y + Math.sin(t) * spread * (k - 0.5), spread * k * 0.6]); }
const found = [];
for (const s0 of [1, -1]) for (const s1 of [1, -1]) for (const s2 of [1, -1]) {
for (const [x, y, r] of seeds) {
const sol = solve3(os, [s0, s1, s2], x, y, r);
if (!sol || !os.every((o) => tangent(o, sol, tol * 10))) continue;
if (!found.some((f) => Math.abs(f.cx - sol.cx) + Math.abs(f.cy - sol.cy) + Math.abs(f.r - sol.r) < tol * 100)) found.push(sol);
}
}
return nearestToPicks(found, [[a, pa], [b, pb], [c, pc]]);
}
Touch point and choice by the picks
64-bit
Where a circle touches an object, and which candidate circle touches nearest the picked points.
line: foot of the center on the line; circle: point of o on the line of centers
The touch point on a line is a projection with one dot product; on a circle it is the center plus the unit vector between centers times the radius, with concentric circles (under 1e-9 apart) given a fixed point. A candidate replaces the best only when its total distance to the picks is smaller by more than 1e-12 (absolute).
tancircle.js
lines 33 to 41
CadCraft 0.8.2
export function touchPoint(o, c) {
if (o.k === 'L') { const t = (c.cx - o.x) * o.dx + (c.cy - o.y) * o.dy; return { x: o.x + o.dx * t, y: o.y + o.dy * t }; }
const d = Math.hypot(c.cx - o.cx, c.cy - o.cy);
if (d < EPS) return { x: o.cx + o.r, y: o.cy };
const k = (c.cx - o.cx) / d, m = (c.cy - o.cy) / d;
// the touch point lies on o, on the line through both centres, on the side of c (outside) or away (o inside c)
const s = d > o.r || Math.abs(d - (o.r - c.r)) < Math.abs(d - (o.r + c.r)) ? 1 : -1;
return { x: o.cx + k * o.r * s, y: o.cy + m * o.r * s };
}
In detail
Method
Offset curves and their crossings (line–line, line–circle, circle–circle); Newton iteration on three signed-distance equations with Cramer's rule.
Number types
64-bit numbers.
Tolerances
tol = 1e-7 × max(1, size of the objects). Two tangents: accepted within tol. Three tangents: Newton stops when every residual is under 1e-13 × max(1, |x|, |y|, r) or after 60 steps; a result is accepted within 10 × tol and merged with another within 100 × tol. Finite-difference step 1e-7 × max(1, |x|, |y|, |r|). Jacobian determinant under 1e-18 (absolute) gives up. Line–circle: no crossing when D < −1e-12 × max(1, r²).
Limits
A three-tangent circle that has not fully converged in 60 steps is still returned when it is tangent within 1e-6 × the objects' size. Solutions the starting points do not reach are not found.
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.