Public
Edited
Feb 22, 2024
5 forks
65 stars
Pseudo-Blue NoiseVariations on Symmetric Nearest Neighbour smoothingPhyllotaxis explainedDelaunay.findTriangleFast Distance TransformFast and simple prime generatorBest-First SearchSimple rectangle packingNearest Neighbor GraphMinimum Spanning TreeLloyd’s AlgorithmUnderstanding point-in-polygonPrim’s AlgorithmBridson’s AlgorithmThe Delaunay’s DualTo Infinity and Back AgainSutherland–Hodgman Clipping
d3.packEnclose
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
}))
enclosingCircle = d3.packEnclose(circles)
// 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;
}
// 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;
}
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;
}
function enclosesWeakAll(a, B) {
for (var i = 0; i < B.length; ++i) {
if (!enclosesWeak(a, B[i])) {
return false;
}
}
return true;
}
// Given the set L = {a}, returns the enclosing circle.
function enclose1(a) {
return encloseBasis1(a);
}
// Given the basis B = {a}, returns the enclosing circle.
function encloseBasis1(a) {
return {x: a.x, y: a.y, r: a.r};
}
// 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
};
}
// Returns true iff the set {a, b} forms a basis.
function isBasis2(a, b) {
return !encloses(a, b)
&& !encloses(b, a);
}
// 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);
}
// 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);
}
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
};
}
// 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]);
}
}
// 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;
}
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;
}
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;
}
path = "M0,-300l100,100h-50v150h150v-50L300,0l-100,100v-50h-150v150h50L0,300l-100,-100h50v-150h-150v50L-300,0l100,-100v50h150v-150h-50z"
width = 640
height = 400
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
