40:null 41:["$","title",null,{"children":"Packing Circles inside a Rectangle | Daniel Wood | Observable"}] 47:T6d8,function pack(circles) { const n = circles.length; if (!n) return circles; let a, b, c; // Place the first circle. a = circles[0], a.x = 0, a.y = 0; if (!(n > 1)) return circles; // Place the second circle. b = circles[1], a.x = -b.r, b.x = a.r, b.y = 0; if (!(n > 2)) return circles; // Place the third circle. place(b, a, c = circles[2]); // Initialize the front-chain using the first three circles a, b and c. a = new Node(a), b = new Node(b), c = new Node(c); a.next = c.previous = b; b.next = a.previous = c; c.next = b.previous = a; // Attempt to place each remaining circle… pack: for (let i = 3; i < n; ++i) { place(a._, b._, c = circles[i]), c = new Node(c); // Find the closest intersecting circle on the front-chain, if any. // “Closeness” is determined by linear distance along the front-chain. // “Ahead” or “behind” is likewise determined by linear distance. let j = b.next, k = a.previous, sj = b._.r, sk = a._.r; do { if (sj <= sk) { if (intersects(j._, c._)) { b = j, a.next = b, b.previous = a, --i; continue pack; } sj += j._.r, j = j.next; } else { if (intersects(k._, c._)) { a = k, a.next = b, b.previous = a, --i; continue pack; } sk += k._.r, k = k.previous; } } while (j !== k.next); // Success! Insert the new circle c between a and b. c.previous = a, c.next = b, a.next = b.previous = b = c; // Compute the new closest circle pair to the centroid. let aa = score(a), ca; while ((c = c.next) !== b) { if ((ca = score(c)) < aa) { a = c, aa = ca; } } b = a.next; } return circles; }48:[] 45:{"id":"d32183cb0bfca5d8","slug":null,"title":"Packing Circles inside a Rectangle","thumbnail":"49e3b8e7b5c25c76853ac31b4ed41e895e2facb91573182f4e68e995d0ccb899","access_level":"public","create_time":"$D2023-09-30T12:58:58.845Z","update_time":"$D2023-09-30T14:04:48.639Z","view_time":null,"first_public_time":"$D2023-09-30T12:58:58.845Z","has_unpublished_edits":null,"fork":{"id":"0e831d393fe73509","slug":"packing-circles-inside-a-rectangle","title":"Packing Circles inside a Rectangle","owner":{"id":"8c2e47252fd4995c","login":"mbostock","name":"Mike Bostock"}},"stars":0,"starred":false,"owner":{"type":"team","id":"3e625d3fdbdc0d0a","login":"danieljwood","name":"Daniel Wood","avatar_url":"https://avatars-next.observableusercontent.com/37aea67dccef4e009d2709aca1700a64df2eb6b1d78ff8a345b3b2bc3bcc8f2f","tier":"starter_2024","bio":"Maps and Chartjunk for @nprapps","following":false},"version":133,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"319e840dacaee022","login":"danieljwood","name":"Daniel Wood","avatar_url":"https://avatars-next.observableusercontent.com/37aea67dccef4e009d2709aca1700a64df2eb6b1d78ff8a345b3b2bc3bcc8f2f","tier":null,"bio":"Maps and Chartjunk for @nprapps","following":false}],"members":[{"type":"individual","id":"319e840dacaee022","login":"danieljwood","name":"Daniel Wood","avatar_url":"https://avatars-next.observableusercontent.com/37aea67dccef4e009d2709aca1700a64df2eb6b1d78ff8a345b3b2bc3bcc8f2f","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Packing Circles inside a Rectangle","cells":[{"id":0,"value":"md`# Packing Circles inside a Rectangle\n\nExploring a variant on Wang et al.’s [circle-packing algorithm](https://github.com/d3/d3-hierarchy/blob/master/README.md#pack).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":86,"value":"viewof n = {\n const form = html``;\n form.oninput = () => form.value = form.i.valueAsNumber;\n form.value = form.i.valueAsNumber;\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":98,"value":"viewof score = {\n const form = html``;\n form.oninput = () => form.value = [scoreRectangle, scoreCircle][form.i.selectedIndex];\n form.oninput();\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"{\n const circles = pack(Array.from({length: n}, () => ({r: 1 })));\n const root = html``;\n yield root;\n const g = root.firstElementChild;\n console.log(circles)\n var svg = d3.select(\"svg\")\n svg.selectAll('circle')\n .data(circles).join(\n enter => enter.append(\"circle\")\n .attr(\"cx\",d=>d.x)\n .attr(\"cy\",d=>d.y)\n .attr(\"r\",d=>d.r)\n );\n yield root;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":36,"value":"height = 500","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":43,"value":"function bounds(circles, pad = 10) {\n const x0 = circles.reduce((v, {x, r}) => Math.min(v, x - r - pad), +Infinity);\n const x1 = circles.reduce((v, {x, r}) => Math.max(v, x + r + pad), -Infinity);\n const y0 = circles.reduce((v, {y, r}) => Math.min(v, y - r - pad), +Infinity);\n const y1 = circles.reduce((v, {y, r}) => Math.max(v, y + r + pad), -Infinity);\n return [x0, y0, x1 - x0, y1 - y0];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"function scoreRectangle(node) {\n const a = node._;\n const b = node.next._;\n const ab = a.r + b.r;\n const cx = (a.x * b.r + b.x * a.r) / ab;\n const cy = (a.y * b.r + b.y * a.r) / ab;\n return Math.max(Math.abs(cx * height), Math.abs(cy * width));\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":101,"value":"function scoreCircle(node) {\n const a = node._;\n const b = node.next._;\n const ab = a.r + b.r;\n const cx = (a.x * b.r + b.x * a.r) / ab;\n const cy = (a.y * b.r + b.y * a.r) / ab;\n return cx * cx + cy * cy;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"$47","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"function place(b, a, c) {\n const dx = b.x - a.x;\n const dy = b.y - a.y;\n const d2 = dx * dx + dy * dy;\n if (d2) {\n const a2 = (a.r + c.r) ** 2;\n const b2 = (b.r + c.r) ** 2;\n if (a2 > b2) {\n const x = (d2 + b2 - a2) / (2 * d2);\n const y = Math.sqrt(Math.max(0, b2 / d2 - x * x));\n c.x = b.x - x * dx - y * dy;\n c.y = b.y - x * dy + y * dx;\n } else {\n const x = (d2 + a2 - b2) / (2 * d2);\n const y = Math.sqrt(Math.max(0, a2 / d2 - x * x));\n c.x = a.x + x * dx - y * dy;\n c.y = a.y + x * dy + y * dx;\n }\n } else {\n c.x = a.x + c.r;\n c.y = a.y;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"function intersects(a, b) {\n const dr = a.r + b.r - 1e-6;\n const dx = b.x - a.x;\n const dy = b.y - a.y;\n return dr > 0 && dr * dr > dx * dx + dy * dy;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"class Node {\n constructor(circle) {\n this._ = circle;\n this.next = null;\n this.previous = null;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W48","stdlib":"1"}} 46:"$45:body"