Circle packing / Thomas Oide

chart = {

// Specify the dimensions of the chart.

const width = 928;

const height = width;

const margin = 1; // to avoid clipping the root circle stroke

// Specify the number format for values.

const format = d3.format(",d");

// Create the pack layout.

const pack = d3.pack()

.size([width - margin * 2, height - margin * 2])

.padding(3);

// Compute the hierarchy from the JSON data; recursively sum the

// values for each node; sort the tree by descending value; lastly

// apply the pack layout.

const root = pack(d3.hierarchy(data_new)

.sum(d => d.value)

.sort((a, b) => b.value - a.value));

// Create the SVG container.

const svg = d3.create("svg")

.attr("width", width)

.attr("height", height)

.attr("viewBox", [-margin, -margin, width, height])

.attr("style", "width: 100%; height: auto; font: 10px sans-serif;")

.attr("text-anchor", "middle");

// Place each node according to the layout’s x and y values.

const node = svg.append("g")

.selectAll()

.data(root.descendants())

.join("g")

.attr("transform", d => `translate(${d.x},${d.y})`);

// Add a title.

node.append("title")

.text(d => `${d.ancestors().map(d => d.data.club_country).reverse().join("/")}\n${format(d.count)}`);

// Add a filled or stroked circle.

node.append("circle")

.attr("fill", d => d.children ? "#fff" : "#ddd")

.attr("stroke", d => d.children ? "#bbb" : null)

.attr("r", d => d.r);

// Add a label to leaf nodes.

const text = node

.filter(d => !d.children && d.r > 10)

.append("text")

.attr("clip-path", d => `circle(${d.r})`);

// Add a tspan for each CamelCase-separated word.

text.selectAll()

.data(d => d.data.club_country.split(/(?=[A-Z][a-z])|\s+/g))

.join("tspan")

.attr("x", 0)

.attr("y", (d, i, nodes) => `${i - nodes.length / 2 + 0.35}em`)

.text(d => d);

// Add a tspan for the node’s value.

text.append("tspan")

.attr("x", 0)

.attr("y", d => `${d.data.club_country.split(/(?=[A-Z][a-z])|\s+/g).length / 2 + 0.35}em`)

.attr("fill-opacity", 0.7)

.text(d => format(d.value));

return svg.node();

}

// The triangle force

function forceTriangle(triangles = []) {

let area = (t, a0, aCurrent) => a0; // Default function that maps triplet to triangle area

let strength = (t) => 1; // Default function that maps triplet to force strength

let iterations = 1; // Default number of iterations

let nodes; // Array of nodes

let areas; // Array of initial triangle areas

const makeTriangle = (

triplet // Creates a Triangle object from a node triplet

) =>

new Triangle(

...triplet.map((node) => [node.x + node.vx, node.y + node.vy])

);

function force(alpha) {

for (let k = 0; k < iterations; ++k) {

for (let itriangle = 0; itriangle < triangles.length; itriangle++) {

let triplet = triangles[itriangle];

let a0 = areas[itriangle];

let t = makeTriangle(triplet);

let q = t.p.map(([x, y]) => [x, y]); // Clone vertices

let newArea = area(triplet, a0, t.area());

t.setArea(newArea);

let s = strength(triplet);

for (let i = 0; i < 3; i++) {

let node = triplet[i];

node.vx += (t.p[i][0] - q[i][0]) * alpha * s;

node.vy += (t.p[i][1] - q[i][1]) * alpha * s;

}

function initialize(_nodes, _random) {

nodes = _nodes;

areas = [];

for (let triplet of triangles) {

areas.push(makeTriangle(triplet).area());

}

force.initialize = initialize;

force.triangles = function (_) {

return arguments.length ? ((triangles = +_), force) : triangles;

};

force.iterations = function (_) {

return arguments.length ? ((iterations = +_), force) : iterations;

};

force.strength = function (_) {

return arguments.length

? ((strength = typeof _ === "function" ? _ : () => _), force)

: strength;

};

force.area = function (_) {

return arguments.length

? ((area = typeof _ === "function" ? _ : () => _), force)

: area;

};

return force;

}

class Triangle {

constructor(a, b, c) {

this.p = [a, b, c];

}

area() {

let total = 0;

let [px, py] = this.p[2];

for (let [x, y] of this.p) {

total += (px - x) * (y + py);

[px, py] = [x, y];

}

return total / 2;

}

sideLength(i) {

const j = (i + 1) % 3;

return Math.hypot(this.p[i][0] - this.p[j][0], this.p[i][1] - this.p[j][1]);

}

sideHeight(i) {

const j = (i + 1) % 3,

k = (i + 2) % 3;

const u = [this.p[j][0] - this.p[i][0], this.p[j][1] - this.p[i][1]];

const v = [this.p[k][0] - this.p[j][0], this.p[k][1] - this.p[j][1]];

const ulen = Math.hypot(...u) || 0.0001;

const uhat = [u[0] / ulen, u[1] / ulen];

const uhatDotV = uhat[0] * v[0] + uhat[1] * v[1];

return [v[0] - uhatDotV * uhat[0], v[1] - uhatDotV * uhat[1]];

}

barycenter() {

const sum = this.p.reduce((a, b) => [a[0] + b[0], a[1] + b[1]]);

return [sum[0] / 3, sum[1] / 3];

}

setArea(a) {

let factor = a / this.area();

if (Math.abs(factor) < 1) return this.setArea1(factor);

return this.setArea2(factor);

}

setArea1(factor) {

// Use scaling towards barycenter

//let formerArea = this.area();

let f = Math.sqrt(Math.abs(factor));

let bary = this.barycenter();

let v = [];

this.p.forEach((q) => {

let u = [(q[0] - bary[0]) * f, (q[1] - bary[1]) * f];

v.push(u);

q[0] = bary[0] + u[0];

q[1] = bary[1] + u[1];

});

if (factor < 0) {

// Reflect wrt barycenter using the smallest height as an axis

let { i, h, hgt } = [0, 1, 2]

.map((i) => {

let hgt = this.sideHeight(i);

let h = Math.hypot(...hgt);

return { i, h, hgt };

})

.reduce((a, b) => (a.h < b.h ? a : b));

let j = (i + 1) % 3;

let k = (i + 2) % 3;

let n = [hgt[0] / h, hgt[1] / h];

let a = v[k][0] * n[0] + v[k][1] * n[1];

let b = h - a;

this.p[i] = [this.p[i][0] + n[0] * b * 2, this.p[i][1] + n[1] * b * 2];

this.p[j] = [this.p[j][0] + n[0] * b * 2, this.p[j][1] + n[1] * b * 2];

this.p[k] = [this.p[k][0] - n[0] * a * 2, this.p[k][1] - n[1] * a * 2];

// mutable debug = { hgt, ratio: this.area() / formerArea };

}

setArea2(factor) {

const h = [0, 1, 2].map((i) => this.sideHeight(i));

const hlen = h.map(([x, y]) => Math.hypot(x, y));

let i =

Math.abs(factor) < 1

? // Shrink

hlen[0] > hlen[1]

? hlen[0] > hlen[2]

? 0

: 2

: hlen[1] > hlen[2]

? 1

: 2

: // Expand

hlen[0] < hlen[1]

? hlen[0] < hlen[2]

? 0

: 2

: hlen[1] < hlen[2]

? 1

: 2;

let u = h[i],

v = [0, 0];

if (factor < 0) {

factor = -factor;

v = [...u];

u = [-u[0], -u[1]];

}

u = [v[0] + (-u[0] * (factor - 1)) / 3, v[1] + (-u[1] * (factor - 1)) / 3];

const j = (i + 1) % 3,

k = (i + 2) % 3;

this.p[i][0] += u[0];

this.p[i][1] += u[1];

this.p[j][0] += u[0];

this.p[j][1] += u[1];

this.p[k][0] -= u[0] * 2;

this.p[k][1] -= u[1] * 2;

}

[data_new, ...data_new.children]

mesh = {

let vertices = [];

let constraints = [];

let circles = [];

let vtype = [];

const edgeSz = Math.min(0.02, ...data_new.children.map((c) => c.count));

for (let d of [data_new, ...data_new.children]) {

let { x, y, r } = d;

const n = Math.max(12, Math.round((Math.PI * 2 * r) / edgeSz));

let prev = vertices.length + n - 1;

let icircle = circles.length;

circles.push({ x, y, r, ivtx: vertices.length, nvtx: n });

for (let i = 0; i < n; i++) {

const ang = (i * Math.PI * 2) / n;

let px = r * Math.cos(ang) + x;

let py = r * Math.sin(ang) + y;

constraints.push([prev, vertices.length]);

prev = vertices.length;

vertices.push([px, py]);

vtype.push(["border", icircle]);

}

// Add a few random vertices

let { x, y, r } = circles[0]; // The outer circle

for (let p of poissonSampling((1 / edgeSz) ** 2, 1, 1)) {

if (Math.hypot(p[0] - x, p[1] - y) > r) continue; // Outside outer circle

let icircle = 0;

for (let i = 1; i < circles.length; i++) {

let { x, y, r } = circles[i];

if (Math.hypot(p[0] - x, p[1] - y) < r) {

icircle = i;

break;

}

// compute the inner circles desired size

let totalArea = 0;

for (let c of circles) {

c.area = Math.PI * c.r ** 2;

totalArea += c.area;

}

let hullArea = circles[0].area;

let innerArea = totalArea - hullArea;

let areaEnlargement = hullArea / innerArea;

for (let c of circles.slice(1)) {

c.newArea = c.area * areaEnlargement;

c.newR = Math.sqrt(c.newArea / Math.PI);

}

return { vertices, constraints, circles, vtype };

}

data = FileAttachment("flare-2.json").json()

data_new = FileAttachment("regions@2.json").json()

import {poissonSampling} from "@esperanc/flow-fields"

Constrainautor = require("@kninnug/constrainautor")

constrained = {

// Creates a constrained triangulation, and populates the mesh with fields 'edges' and 'etype'

const { vertices, vtype, constraints, circles } = mesh;

const del = d3.Delaunay.from(vertices);

const con = new Constrainautor(del._delaunator);

const conEdge = [];

for (const [v1, v2] of constraints) {

con.constrainOne(v1, v2);

conEdge[v1] = v2;

}

con.delaunify();

const { points, halfedges, triangles } = del;

let edges = [];

let etype = [];

for (let i = 0, n = halfedges.length; i < n; ++i) {

let j = halfedges[i];

if (j < i) continue;

const vi = triangles[i];

const vj = triangles[j];

edges.push([vi, vj]);

if (vtype[vi][0] === "border" && vtype[vj][0] === "border") {

if (vtype[vi][1] == vtype[vj][1]) {

etype.push([

conEdge[vi] == vj || conEdge[vj] == vi ? "border" : "rigid",

vtype[vi][1]

]);

} else etype.push(["shrink", 0]);

} else {

let ivertex = vtype[vi][0] == "internal" ? vtype[vi][1] : vtype[vj][1];

if (ivertex == 0) etype.push(["shrink", 0]);

else etype.push(["rigid", ivertex]);

}

Object.assign(mesh, { edges, etype, triangles, circles });

return del;

}

Purpose-built for displays of data