Public
Edited
Feb 22, 2024
5 forks
65 stars
Also listed in…
Gallery
Algorithms
Insert cell
Insert cell
circles = Array.from({length: 20}, () => ({
x: ((Math.random() - 0.5) / 2 + 0.5) * width,
y: ((Math.random() - 0.5) / 2 + 0.5) * height,
r: (Math.random() + 0.5) * 20
}))
Insert cell
enclosingCircle = d3.packEnclose(circles)
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
// Given two circles a and b, returns true iff b ⊆ a.
function encloses(a, b) {
const dr = a.r - b.r;
const dx = b.x - a.x;
const dy = b.y - a.y;
return dr >= 0 && dr * dr > dx * dx + dy * dy;
}
Insert cell
Insert cell
// Given a circle a and set B, returns true iff b ⊆ a for every b ∈ B.
function enclosesAll(a, B) {
for (var i = 0; i < B.length; ++i) {
if (!encloses(a, B[i])) {
return false;
}
}
return true;
}
Insert cell
Insert cell
function enclosesWeak(a, b) {
const dr = a.r - b.r + 1e-6;
const dx = b.x - a.x;
const dy = b.y - a.y;
return dr > 0 && dr * dr > dx * dx + dy * dy;
}
Insert cell
function enclosesWeakAll(a, B) {
for (var i = 0; i < B.length; ++i) {
if (!enclosesWeak(a, B[i])) {
return false;
}
}
return true;
}
Insert cell
Insert cell
// Given the set L = {a}, returns the enclosing circle.
function enclose1(a) {
return encloseBasis1(a);
}
Insert cell
// Given the basis B = {a}, returns the enclosing circle.
function encloseBasis1(a) {
return {x: a.x, y: a.y, r: a.r};
}
Insert cell
Insert cell
Insert cell
Insert cell
// Given the basis B = {a, b}, returns the enclosing circle.
function encloseBasis2(a, b) {
const x1 = a.x, y1 = a.y, r1 = a.r;
const x2 = b.x, y2 = b.y, r2 = b.r;
const x21 = x2 - x1, y21 = y2 - y1, r21 = r2 - r1;
const l = Math.sqrt(x21 * x21 + y21 * y21);
return {
x: (x1 + x2 + x21 / l * r21) / 2,
y: (y1 + y2 + y21 / l * r21) / 2,
r: (l + r1 + r2) / 2
};
}
Insert cell
Insert cell
// Returns true iff the set {a, b} forms a basis.
function isBasis2(a, b) {
return !encloses(a, b)
&& !encloses(b, a);
}
Insert cell
Insert cell
// Given the set L = {a, b}, returns the enclosing circle.
function enclose2(a, b) {
return encloses(a, b) ? a
: encloses(b, a) ? b
: encloseBasis2(a, b);
}
Insert cell
Insert cell
// Returns true iff the set {a, b, c} forms a basis.
function isBasis3(a, b, c) {
return isBasis2(a, b) && !encloses(encloseBasis2(a, b), c)
&& isBasis2(a, c) && !encloses(encloseBasis2(a, c), b)
&& isBasis2(b, c) && !encloses(encloseBasis2(b, c), a);
}
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
function encloseBasis3(a, b, c) {
const x1 = a.x, y1 = a.y, r1 = a.r;
const x2 = b.x, y2 = b.y, r2 = b.r;
const x3 = c.x, y3 = c.y, r3 = c.r;
const a2 = x1 - x2;
const a3 = x1 - x3;
const b2 = y1 - y2;
const b3 = y1 - y3;
const c2 = r2 - r1;
const c3 = r3 - r1;
const d1 = x1 * x1 + y1 * y1 - r1 * r1;
const d2 = d1 - x2 * x2 - y2 * y2 + r2 * r2;
const d3 = d1 - x3 * x3 - y3 * y3 + r3 * r3;
const ab = a3 * b2 - a2 * b3;
const xa = (b2 * d3 - b3 * d2) / (ab * 2) - x1;
const xb = (b3 * c2 - b2 * c3) / ab;
const ya = (a3 * d2 - a2 * d3) / (ab * 2) - y1;
const yb = (a2 * c3 - a3 * c2) / ab;
const A = xb * xb + yb * yb - 1;
const B = 2 * (r1 + xa * xb + ya * yb);
const C = xa * xa + ya * ya - r1 * r1;
const r = -(A ? (B + Math.sqrt(B * B - 4 * A * C)) / (2 * A) : C / B);
return {
x: x1 + xa + xb * r,
y: y1 + ya + yb * r,
r: r
};
}
Insert cell
Insert cell
// Given a basis B, returns the enclosing circle.
function encloseBasis(B) {
switch (B.length) {
case 1: return encloseBasis1(B[0]);
case 2: return encloseBasis2(B[0], B[1]);
case 3: return encloseBasis3(B[0], B[1], B[2]);
}
}
Insert cell
Insert cell
// Given a basis B and a circle p ⊈ B, returns the new basis Bʹ.
function extendBasis(B, p) {
var i, j;

if (enclosesWeakAll(p, B)) return [p];

// If we get here then B must have at least one element.
for (i = 0; i < B.length; ++i) {
if (!encloses(p, B[i])
&& enclosesWeakAll(encloseBasis2(B[i], p), B)) {
return [B[i], p];
}
}

// If we get here then B must have at least two elements.
for (i = 0; i < B.length - 1; ++i) {
for (j = i + 1; j < B.length; ++j) {
if (!encloses(encloseBasis2(B[i], B[j]), p)
&& !encloses(encloseBasis2(B[i], p), B[j])
&& !encloses(encloseBasis2(B[j], p), B[i])
&& enclosesWeakAll(encloseBasis3(B[i], B[j], p), B)) {
return [B[i], B[j], p];
}
}
}

// If we get here then something is very wrong.
throw new Error;
}
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
function enclose(L) {
var i = 0, n = d3.shuffle(L = L.slice()).length, B = [], p, e;

while (i < n) {
p = L[i];
if (e && enclosesWeak(e, p)) ++i;
else e = encloseBasis(B = extendBasis(B, p)), i = 0;
}

return e.basis = B, e;
}
Insert cell
Insert cell
Insert cell
function* encloseStar(L) {
var i = 0, n = d3.shuffle(L = L.slice()).length, B = [], p, e;

while (i < n) {
p = L[i];
yield {p: p, e: e, i: i, B: B, L: L.slice(0, i)};
if (e && enclosesWeak(e, p)) ++i;
else e = encloseBasis(B = extendBasis(B, p)), i = 0;
}

yield {e: e, i: i, B: B, L: L};
return e;
}
Insert cell
path = "M0,-300l100,100h-50v150h150v-50L300,0l-100,100v-50h-150v150h50L0,300l-100,-100h50v-150h-150v50L-300,0l100,-100v50h150v-150h-50z"
Insert cell
width = 640
Insert cell
height = 400
Insert cell

One platform to build and deploy the best data apps

Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.
Learn more