31:T85b,{ const sz = 600; const margin = 40; const circles = mesh.circles; const svg = d3 .create("svg") .attr("width", sz + margin * 2) .attr("height", sz + margin * 2) .attr("viewBox", [-margin, -margin, sz + margin * 2, sz + margin * 2]), link = showTriangulation ? svg .selectAll(".link") .data(graph.links) .join("line") .classed("link", true) .classed("border", (d) => d.etype[0] === "border") .attr("stroke", (d) => d.etype[0] === "border" ? "black" : d.etype[0] === "rigid" ? "blue" : "red" ) : null, node = showTriangulation ? svg .selectAll(".node") .data(graph.nodes) .join("circle") .attr("r", 2) .classed("node", true) .classed("fixed", (d) => d.fx !== undefined) : null, polygons = showTriangulation ? null : svg .selectAll(".poly") .data(circles.slice(1)) .join("polygon") .classed("poly", true); yield svg.node(); function tick() { if (showTriangulation) { link .attr("x1", (d) => d.source.x * sz) .attr("y1", (d) => d.source.y * sz) .attr("x2", (d) => d.target.x * sz) .attr("y2", (d) => d.target.y * sz); node.attr("cx", (d) => d.x * sz).attr("cy", (d) => d.y * sz); } else { polygons.attr("points", (d) => { let { ivtx, nvtx } = d; let pts = []; for (let i = ivtx; i < ivtx + nvtx; i++) { pts.push([graph.nodes[i].x * sz, graph.nodes[i].y * sz]); } return `${pts.flat()}`; }); } } tick(); await Promises.delay(1000); const simulation = d3 .forceSimulation() .nodes(graph.nodes) .force( "link", d3 .forceLink(graph.links) .distance((d) => d.dist) .strength((d) => (d.dist == 0 ? 1 : 0.03)) ) .force( "triangle", forceTriangle(graph.triplets).area((t, a0, a) => a0 * t.areaRatio) ) .on("tick", tick); }32:T6d1,mesh = { let vertices = []; let constraints = []; let circles = []; let vtype = []; const edgeSz = Math.min(0.02, ...packed.children.map((c) => c.r)); for (let d of [packed, ...packed.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; } } if (emptySpacePoints || icircle > 0) { vertices.push(p); vtype.push(["internal", icircle]); } } // 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 }; }33:T4c7,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; }34:T566,graph = { constrained; resetSimulation; showTriangulation; const { vertices, vtype, edges, etype, circles, triangles } = mesh; const nhull = circles[0].nvtx; let nodes = vertices.map(([x, y], i) => { let obj = { x, y, vtype: vtype[i] }; if (i < nhull) { [obj.fx, obj.fy] = [obj.x, obj.y]; } return obj; }); let links = edges.map(([isrc, idst], iedge) => { let obj = { source: nodes[isrc], target: nodes[idst], etype: etype[iedge] }; obj.esize = Math.hypot( obj.source.x - obj.target.x, obj.source.y - obj.target.y ); if ( obj.etype[0] === "rigid" || (obj.etype[0] === "border" && obj.etype[0][1] > 0) ) { let icircle = obj.etype[1]; obj.dist = (obj.esize * circles[icircle].newR) / circles[icircle].r; } else { obj.dist = 0; } return obj; }); // Add area constraints to make sure triangles do not flip let triplets = []; for (let i = 0, n = triangles.length; i < n; i += 3) { const v = [i, i + 1, i + 2].map((j) => nodes[triangles[j]]); const icircle = v[0].vtype[1]; if (icircle > 0 && icircle == v[1].vtype[1] && icircle == v[2].vtype[1]) { v.areaRatio = (circles[icircle].newR / circles[icircle].r) ** 2; triplets.push(v); } else { v.areaRatio = 0.01; triplets.push(v); } } return { nodes, links, triplets }; }35:T7a2,// 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; }36:T696,{ let height = (width * 9) / 16; const canvas = DOM.canvas(width, height); const ctx = canvas.getContext("2d"); const trianglePoints = [ [100, 100], [300, 100], [300, 300] ]; let refresh = () => { const vcolor = ["yellow", "magenta", "cyan"]; let tri = new Triangle(...trianglePoints.map((p) => [...p])); tri.setArea(tri.area() * areaRatio); ctx.clearRect(0, 0, width, height); ctx.lineWidth = 4; ctx.strokeStyle = "green"; ctx.beginPath(); for (let q of tri.p) ctx.lineTo(...q); ctx.closePath(); ctx.stroke(); let i = 0; for (let p of tri.p) { ctx.beginPath(); ctx.arc(...p, 5, 0, Math.PI * 2); ctx.fillStyle = vcolor[i++]; ctx.fill(); } ctx.lineWidth = 2; ctx.strokeStyle = "black"; tri = new Triangle(...trianglePoints); ctx.beginPath(); for (let q of tri.p) ctx.lineTo(...q); ctx.closePath(); ctx.stroke(); i = 0; for (let p of trianglePoints) { ctx.beginPath(); ctx.arc(...p, 5, 0, Math.PI * 2); ctx.fillStyle = vcolor[i++]; ctx.fill(); } }; let selPoint = null; let mouse = null; canvas.onmousedown = (e) => { let [px, py] = [e.offsetX, e.offsetY]; selPoint = null; for (let q of trianglePoints) { let [x, y] = q; if (Math.hypot(x - px, y - py) < 10) selPoint = q; } mouse = [px, py]; }; canvas.onmousemove = (e) => { if (selPoint && e.buttons) { let p = [e.offsetX, e.offsetY]; let d = [p[0] - mouse[0], p[1] - mouse[1]]; selPoint[0] += d[0]; selPoint[1] += d[1]; refresh(); mouse = p; } }; refresh(); return canvas; }37:Tc5b,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; } }38:[] 2f:{"title":"Squished circle packing","cells":[{"id":0,"value":"# Squished circle packing\n\nAs we know, [circle packing](https://observablehq.com/@d3/pack) layouts \"waste\" space. Here's my attempt to ameliorate the situation by expanding the circles until they almost cover the parent circle. The algorithm uses [d3.force](https://observablehq.com/@d3/force-directed-graph) on a graph created from a Delaunay triangulation of the circles and employing a custom _\"triangle\"_ force that tries to set triangle areas to a prescribed value. ","pinned":false,"hidden":false,"mode":"md"},{"id":388,"value":"viewof nCircles = Inputs.radio([5, 10, 20, 30], { label: \"Circles\", value: 10 })","pinned":false,"hidden":false,"mode":"ojs"},{"id":157,"value":"viewof resetSimulation = Inputs.button(\"reset simulation\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":320,"value":"viewof showTriangulation = Inputs.toggle({\n label: \"Show Triangulation\",\n value: true\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":139,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":5,"value":"
\n#### Data given as an array of pairs name/value","pinned":false,"hidden":false,"mode":"md"},{"id":8,"value":"data = {\n let data = [];\n const n = nCircles;\n for (let i = 0; i < n; i++) {\n data.push([`name ${i}`, Math.random() * 100 + 1]);\n }\n return data;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":12,"value":"
\n#### Make a hierarchy for the `d3.pack` circle packing layout","pinned":false,"hidden":false,"mode":"md"},{"id":19,"value":"hier = d3.hierarchy({name:\"root\", children: data.map(([name,value]) =>({name,value}))}).sum(d=>d.value)","pinned":true,"hidden":false,"mode":"ojs"},{"id":31,"value":"
\n#### Circle packing","pinned":false,"hidden":false,"mode":"md"},{"id":35,"value":"packed = d3.pack().padding(0.02)(hier)","pinned":true,"hidden":false,"mode":"ojs"},{"id":38,"value":"{\n const sz = 500;\n const chart = d3.select(svg`
\n#### Polygonize circles","pinned":false,"hidden":false,"mode":"md"},{"id":161,"value":"viewof emptySpacePoints = Inputs.toggle({\n label: \"add empty space points\",\n value: false\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":52,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":59,"value":"{\n const sz = 500;\n const chart = d3.select(svg`
\n#### Add additional points and create a constrained Delaunay triangulation","pinned":false,"hidden":false,"mode":"md"},{"id":68,"value":"import {poissonSampling} from \"@esperanc/flow-fields\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":71,"value":"Constrainautor = require(\"@kninnug/constrainautor\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":73,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":76,"value":"{ \n // Draws the constrained delaunay triangulation \n constrained;\n const sz = 600;\n const context = DOM.context2d(sz,sz)\n const {edges, etype, vertices} = mesh;\n for (let iedge = 0; iedge\n#### Creates a data structure containing nodes and links for a force simulation","pinned":false,"hidden":false,"mode":"md"},{"id":119,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":256,"value":"## A triangle area force","pinned":false,"hidden":false,"mode":"md"},{"id":192,"value":"$35","pinned":true,"hidden":false,"mode":"ojs"},{"id":196,"value":"## A Triangle class","pinned":false,"hidden":false,"mode":"md"},{"id":414,"value":"viewof areaRatio = Inputs.range([-2, 2], { label: \"Area ratio\", value: 1 })","pinned":false,"hidden":false,"mode":"ojs"},{"id":409,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":421,"value":"mutable debug = 0","pinned":true,"hidden":false,"mode":"ojs"},{"id":198,"value":"$37","pinned":true,"hidden":false,"mode":"ojs"},{"id":394,"value":"testTriangle = {\n let t = new Triangle([0, 0], [1, 1], [1, 0]);\n let a = t.area();\n let result = {\n original: t.p.map((d) => [...d]),\n originalArea: a,\n originalBary: t.barycenter()\n };\n t.setArea(a * 2);\n result.after = t.p;\n result.afterArea = t.area();\n result.afterBary = t.barycenter();\n return result;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":145,"value":"html``","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W38","stdlib":"1","titling":"auto"}