2d:null 2e:["$","title",null,{"children":"Circle Packing in Polygons | Harry Stevens | Observable"}] 33:T7e9,{ const m = { left: 42, right: 10, top: 20, bottom: 40 }; const w = size - m.left - m.right; const h = 340 - m.top - m.bottom; const x = d3.scaleBand(circles.map(d => d.index), [0, w]); const y = d3.scaleLinear([0, maxiters], [h, 0]); const svg = d3.create("svg") .attr("font-family", "sans-serif") .attr("font-size", 14) .attr("overflow", "visible") .attr("width", w + m.left + m.right) .attr("height", h + m.top + m.bottom); const g = svg.append("g") .attr("transform", `translate(${[m.left, m.top]})`); g.append("text") .attr("y", 14) .attr("transform", `translate(${[-m.left, -m.top]})`) .text("↑ Attempts"); const xaxis = g.append("g") .attr("transform", `translate(${w})`) .call( d3.axisLeft(y) .tickSize(w + 6) .ticks(4) ); xaxis.select(".domain").remove(); xaxis.selectAll("text") .attr("font-size", 12); xaxis.selectAll("line") .attr("stroke", "#eee"); const yaxis = g.append("g") .attr("transform", `translate(0, ${h})`) .call(d3.axisBottom(x) .tickValues([...d3.range(0, N, N / 4), N - 1]) ); g.append("text") .attr("transform", `translate(0, ${h + m.bottom})`) .text("Circle index →"); yaxis.selectAll("text") .attr("font-size", 12); const label = g.append("g") .datum(circles.find(d => d.iters === maxiters)) .attr("transform", d => `translate(${[x(d.index), y(d.iters)]})`); label.append("polyline") .attr("points", [[-10, 0], [0, 0]]) .attr("stroke", "black") .attr("stroke-width", 0.5); label.append("text") .attr("dx", -2) .attr("text-anchor", "end") .attr("x", -10) .attr("y", 4) .text("Max."); g.selectAll("rect") .data(circles) .join("rect") .attr("fill", "steelblue") .attr("x", d => x(d.index)) .attr("y", d => y(d.iters)) .attr("width", 1) .attr("height", d => h - y(d.iters)); return svg.node(); }34:T63f,{ const m = { left: 42, right: 10, top: 20, bottom: 40 }; const w = size - m.left - m.right; const h = 340 - m.top - m.bottom; const x = d3.scaleBand(circles.map(d => d.index), [0, w]); const y = d3.scaleLinear([0, d3.max(circles, d => d.r)], [h, 0]); const svg = d3.create("svg") .attr("font-family", "sans-serif") .attr("font-size", 14) .attr("overflow", "visible") .attr("width", w + m.left + m.right) .attr("height", h + m.top + m.bottom); const g = svg.append("g") .attr("transform", `translate(${[m.left, m.top]})`); g.append("text") .attr("y", 14) .attr("transform", `translate(${[-m.left, -m.top]})`) .text("↑ Radius"); const xaxis = g.append("g") .attr("transform", `translate(${w})`) .call( d3.axisLeft(y) .tickSize(w + 6) .ticks(4) ); xaxis.select(".domain").remove(); xaxis.selectAll("text") .attr("font-size", 12); xaxis.selectAll("line") .attr("stroke", "#eee"); const yaxis = g.append("g") .attr("transform", `translate(0, ${h})`) .call(d3.axisBottom(x) .tickValues([...d3.range(0, N, N / 4), N - 1]) ); g.append("text") .attr("transform", `translate(0, ${h + m.bottom})`) .text("Circle index →"); yaxis.selectAll("text") .attr("font-size", 12); g.selectAll("rect") .data(circles) .join("rect") .attr("fill", "steelblue") .attr("x", d => x(d.index)) .attr("y", d => y(d.r)) .attr("width", 1) .attr("height", d => h - y(d.r)); return svg.node(); }35:[] 31:{"id":"655df0f31d1cb5b4","slug":"circle-packing-in-polygons","title":"Circle Packing in Polygons","thumbnail":"d213df07fcab3b82f51c36c07c9bdfae501131b47e471dbb4c146c557a238575","access_level":"public","create_time":"$D2021-09-22T20:42:27.897Z","update_time":"$D2022-09-22T14:03:43.578Z","view_time":null,"first_public_time":"$D2021-09-24T18:19:18.147Z","has_unpublished_edits":null,"fork":{"id":"1a1b4efd2ab9fc9e","slug":"inefficient-circle-packing","title":"Inefficient Circle Packing","owner":{"id":"be420f6a83563b92","login":"harrystevens","name":"Harry Stevens"}},"stars":29,"starred":false,"owner":{"type":"team","id":"be420f6a83563b92","login":"harrystevens","name":"Harry Stevens","avatar_url":"https://avatars-next.observableusercontent.com/bc9bae4b7e30062b343ae978a13454e29cd3f2daf3a800d0024043686ddf094b","tier":"starter_2024"},"version":642,"publish_version":642,"role":null,"authored":false,"authors":[{"type":"individual","id":"61e2153e05789733","login":"harrystevens","name":"Harry Stevens","avatar_url":"https://avatars-next.observableusercontent.com/bc9bae4b7e30062b343ae978a13454e29cd3f2daf3a800d0024043686ddf094b","tier":null}],"members":[{"type":"individual","id":"61e2153e05789733","login":"harrystevens","name":"Harry Stevens","avatar_url":"https://avatars-next.observableusercontent.com/bc9bae4b7e30062b343ae978a13454e29cd3f2daf3a800d0024043686ddf094b","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":13,"collection":null,"type":"notebook","body":{"title":"Circle Packing in Polygons","cells":[{"id":0,"value":"md`# Circle Packing in Polygons\n\nPacking circles into a polygon with brute force. Inspired by [Tyler Hobbs](https://tylerxhobbs.com/essays/2016/a-randomized-approach-to-cicle-packing).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":271,"value":"viewof sides = Inputs.radio([4, 6, 8, 10, 12], { label: \"Number of sides:\", value: 6 })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":578,"value":"viewof rmax = Inputs.range([0, round(size / 4)], { label: \"Maximum radius:\", value: round(size / 10), step: 1 })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":298,"value":"viewof showOutline = Inputs.toggle({ label: \"Show outline:\", value: false })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":139,"value":"viewof again = Inputs.button(\"Again\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"{\n const svg = d3.create(\"svg\")\n .attr(\"overflow\", \"visible\")\n .attr(\"viewBox\", `0 0 ${size} ${size}`)\n .attr(\"width\", size);\n \n svg.append(\"rect\")\n .attr(\"width\", size)\n .attr(\"height\", size)\n .attr(\"fill\", \"#f2efe6\");\n \n if (showOutline){\n svg.append(\"polygon\")\n .attr(\"stroke\", \"#888\")\n .attr(\"fill\", \"none\")\n .attr(\"points\", polygon); \n }\n \n svg.selectAll(\"circle\")\n .data(circles)\n .join(\"circle\")\n .attr(\"cx\", d => d.x)\n .attr(\"cy\", d => d.y)\n .attr(\"fill\", (d, i) => c[i % c.length])\n .attr(\"r\", d => d.r);\n \n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":445,"value":"md`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":75,"value":"md`It gets progressively harder to place random circles.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":79,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":425,"value":"md`At the same time, it gets progressively less likely you'll place a big circle.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":420,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":509,"value":"{\n const acircles = d3.sum(circles, d => pi * pow(d.r, 2));\n const apolygon = geometric.polygonArea(polygon);\n const adiff = apolygon - acircles;\n const radius = sqrt(adiff / pi);\n return md`The sum of the area of the circles is ${f(round(acircles))} pixels, while the area of the polygon is ${f(round(apolygon))} pixels. That leaves an area of ${f(round(adiff))} pixels, from which you can make a circle of radius ${round(radius)} pixels, which is ${radius > rmax ? \"larger\" : \"Smaller\"} than the maximum radius we started with.`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":437,"value":"md`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":195,"value":"polygon = geometric.polygonRegular(sides, size ** 2 / (\n sides === 4 ? 1.1 :\n sides === 6 ? 1.6 :\n sides === 8 ? 1.3 :\n sides === 10 ? 1.4 :\n 1.3\n), [size / 2, size / 2]);","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":596,"value":"rmin = 1.5; // Increasing this can kill your browser","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":614,"value":"pad = 1; // Increasing this can kill your browser","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":99,"value":"N = {\n again;\n return 2000;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":113,"value":"c = [\"#181818\", \"#59354b\", \"#436098\", \"#97acd7\", \"#2d42de\", \"#2c7f2c\", \"#6ab469\", \"#f2d51a\", \"#bf3226\", \"#f3a9aa\"]\n .map(d => d3.cubehelix(d))\n .sort((a, b) => d3.ascending(a.h, b.h))\n .map(d => d.hex())","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":539,"value":"html`

${c.map(color => `

`).join(\"\")}

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":40,"value":"size = min(width, 640)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"circles = {\n const circles = [];\n for (let i = 0; i < N; i++){\n pack(polygon, circles, rmin, rmax, pad);\n }\n return circles;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":149,"value":"maxiters = d3.max(circles, d => d.iters)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":431,"value":"md`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"pack = (polygon, circles, rmin = 1, rmax = 20, pad = 1) => {\n const [[x1, y1], [x2, y2]] = geometric.polygonBounds(polygon),\n width = x2 - x1,\n height = y2 - y1;\n \n let r, x, y;\n \n let safe = false,\n iters = 0;\n \n while (!safe){\n let intersection = false;\n r = max(rmin, random() * rmax);\n x = x1 + r + random() * (width - (r * 2));\n y = y1 + r + random() * (height - (r * 2));\n \n const p = [x, y];\n\n if (geometric.pointInPolygon(p, polygon) && circleInPolygon(x, y, r, polygon)){\n for (let i = 0, l = circles.length; i < l; i++){\n const c = circles[i];\n const l = geometric.lineLength([p, [c.x, c.y]]);\n if (l < (r + c.r + pad)){\n intersection = true;\n break;\n }\n }\n safe = !intersection;\n }\n else {\n safe = false;\n }\n \n iters++;\n }\n \n if (safe) {\n circles.push({ x, y, r, iters, index: circles.length });\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":245,"value":"function circleInPolygon(x, y, r, polygon){\n let inside = true;\n for (let i = 0, l = polygon.length; i < l; i++){\n const line = [polygon[i], polygon[i + 1] || polygon[0]];\n const point = [x, y];\n if (geometric.lineLength([point, pointToLine(point, line)]) < r){\n inside = false;\n break;\n }\n }\n return inside;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":239,"value":"// https://observablehq.com/@mbostock/closest-point-on-line\nfunction pointToLine(point, line){\n const [[x1, y1], [x2, y2]] = line;\n const [x3, y3] = point;\n const x21 = x2 - x1;\n const y21 = y2 - y1;\n const x31 = x3 - x1\n const y31 = y3 - y1;\n const t = max(0, min(1, (x31 * x21 + y31 * y21) / (x21 * x21 + y21 * y21)));\n\n return [x1 + (x2 - x1) * t, y1 + (y2 - y1) * t];\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":434,"value":"md`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":512,"value":"f = d3.format(\",\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":241,"value":"min = Math.min","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":243,"value":"max = Math.max","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":635,"value":"pi = Math.PI","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":638,"value":"pow = Math.pow","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":590,"value":"random = Math.random","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":628,"value":"round = Math.round","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":632,"value":"sqrt = Math.sqrt","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":8,"value":"geometric = require(\"geometric@2\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 32:"$31:body"