2f:T8be,# Quad Tree Grid Packing The goal is to take items distributed arbitrarily in a Cartesian space, and place them in a grid such that those items maintain approximate relative locations to each-other. The algorithm: 1. Create a quad tree from the input data. 1. Use the smallest leaf square in the tree as the "grid size". 1. Use the grid size to quantize the original positions of data to establish the grid. 1. Remove empty rows and columns from the grid. This appears to produce grid where no two items appear in the same cell. ## Some Ideas - A similar algorithm with [hexbins](https://www.uber.com/blog/h3/) for a different look and feel. - Use the grid positions as input to a force directed layout to reduce initial "explosions" when items are very close and thus reduce sensitivity to initial conditions. - Use the grid positions as input into something like [london-tube-map](https://github.com/johnwalley/d3-tube-map) style layout. - Use something [A\*](https://observablehq.com/@rossmills99/a-search-algorithm) to find paths through the grid to connect nodes. - To further compact the grid: - If a two adjacent rows have no overlapping items, these rows could be collapsed into each other. This could be attempted for all rows and columns. Order likely effects the result. - Look for and remove empty diagonals. - Apply rotation transform, maybe every 10 or 45 degrees, to input positions and see what produces the tightest grid. Note: this loses the "north is up" property. - To evaluate different options, calculate distortion: the difference distance between original pairs and the final grid pairs. ## Recursive Clusters If the data is especially clumpy, this algorithm distributes the points in a way that feels too uniform, and thus loses the clumpy structure. Perhaps apply the the algorithm to leaves which appear at higher levels of the quad tree - the less clumpy items - and then recursively apply the algorithm to the deeper items in the tree. Then place the smaller "cluster" grids inside single cell of the lager "containing" grid. I think the quad tree clearly identifies where these smaller cluster grids would go. That said, there are better ways identify clusters. 30:T1839,function ForceGraph( { nodes, // an iterable of node objects (typically [{id}, …]) links // an iterable of link objects (typically [{source, target}, …]) }, { nodeId = (d) => d.id, // given d in nodes, returns a unique identifier (string) nodeGroup, // given d in nodes, returns an (ordinal) value for color nodeGroups, // an array of ordinal values representing the node groups nodeTitle, // given d in nodes, a title string nodeFill = "currentColor", // node stroke fill (if not using a group color encoding) nodeStroke = "#fff", // node stroke color nodeStrokeWidth = 1.5, // node stroke width, in pixels nodeStrokeOpacity = 1, // node stroke opacity nodeRadius = 5, // node radius, in pixels nodeStrength, linkSource = ({ source }) => source, // given d in links, returns a node identifier string linkTarget = ({ target }) => target, // given d in links, returns a node identifier string linkDistance = () => 30, linkStroke = "#999", // link stroke color linkStrokeOpacity = 0.6, // link stroke opacity linkStrokeWidth = 1.5, // given d in links, returns a stroke width in pixels linkStrokeLinecap = "round", // link stroke linecap linkStrength, colors = d3.schemeTableau10, // an array of color strings, for the node groups width = 640, // outer width, in pixels height = 400, // outer height, in pixels collisionStrength = 0, gridStrength = 0, originalPositionStrength = 0, center = true, alphaTarget = 0.3, // when this promise resolves, stop the simulation, invalidation } = {} ) { // Compute values. const N = d3.map(nodes, nodeId).map(intern); const LS = d3.map(links, linkSource).map(intern); const LT = d3.map(links, linkTarget).map(intern); if (nodeTitle === undefined) nodeTitle = (_, i) => N[i]; const T = nodeTitle == null ? null : d3.map(nodes, nodeTitle); const G = nodeGroup == null ? null : d3.map(nodes, nodeGroup).map(intern); const W = typeof linkStrokeWidth !== "function" ? null : d3.map(links, linkStrokeWidth); const L = typeof linkStroke !== "function" ? null : d3.map(links, linkStroke); // Replace the input nodes and links with mutable objects for the simulation. nodes = d3.map(nodes, (d, i) => ({ id: N[i], ...d })); links = d3.map(links, (_, i) => ({ source: LS[i], target: LT[i] })); // Compute default domains. if (G && nodeGroups === undefined) nodeGroups = d3.sort(G); // Construct the scales. const color = nodeGroup == null ? null : d3.scaleOrdinal(nodeGroups, colors); // Construct the forces. const forceNode = d3.forceManyBody(); const forceLink = d3 .forceLink(links) .id(({ index: i }) => N[i]) .distance(linkDistance); if (nodeStrength !== undefined) forceNode.strength(nodeStrength); if (linkStrength !== undefined) forceLink.strength(linkStrength); const simulation = d3 .forceSimulation(nodes) .force("link", forceLink) .force("charge", forceNode) .force("orderX", new forceOrderX()) .force("orderY", new forceOrderY()) .force("center", center ? d3.forceCenter() : null) .force("rect-collide", forceCollide(0, collisionStrength)) .force( "circ-collide", d3 .forceCollide() .radius((d) => d.width / 2) .iterations(3) ) .force("grid", forceGrid(gridStrength)) .force("original", forceOriginal(originalPositionStrength)) .alphaTarget(alphaTarget) .on("tick", ticked); const svg = d3 .create("svg") .attr("width", width) .attr("height", height) .attr("viewBox", [-width / 2, -height / 2, width, height]) .attr("style", "max-width: 100%; height: auto; height: intrinsic;"); const link = svg .append("g") .attr("stroke", typeof linkStroke !== "function" ? linkStroke : null) .attr("stroke-opacity", linkStrokeOpacity) .attr( "stroke-width", typeof linkStrokeWidth !== "function" ? linkStrokeWidth : null ) .attr("stroke-linecap", linkStrokeLinecap) .selectAll("line") .data(links) .join("line"); const node = svg .append("g") .attr("fill", nodeFill) .attr("stroke", nodeStroke) .attr("stroke-opacity", nodeStrokeOpacity) .attr("stroke-width", nodeStrokeWidth) .selectAll("g") .data(nodes) .join("g") .call(drag(simulation)); node.append("rect").style("fill", (d, i) => color(i % 10)); node .append("text") .style("pointer-events", "none") .style("stroke", "black") .attr("text-anchor", "middle") .attr("dy", "0.34em") .text(nodeTitle); if (W) link.attr("stroke-width", ({ index: i }) => W[i]); if (L) link.attr("stroke", ({ index: i }) => L[i]); if (G) node.attr("fill", ({ index: i }) => color(G[i])); if (T) node.append("title").text(({ index: i }) => T[i]); if (invalidation != null) invalidation.then(() => simulation.stop()); function intern(value) { return value !== null && typeof value === "object" ? value.valueOf() : value; } function ticked() { link .attr("x1", (d) => d.source.x) .attr("y1", (d) => d.source.y) .attr("x2", (d) => d.target.x) .attr("y2", (d) => d.target.y); node .attr("transform", ({ x, y, width, height }) => `translate(${[x, y]})`) .selectAll("rect") .attr("x", (d) => -d.width / 2) .attr("y", (d) => -d.height / 2) .attr("width", (d) => d.width) .attr("height", (d) => d.height); } function drag(simulation) { function dragstarted(event) { // if (!event.active) simulation.alphaTarget(0.3).restart(); event.subject.fx = event.subject.x; event.subject.fy = event.subject.y; } function dragged(event) { event.subject.fx = event.x; event.subject.fy = event.y; } function dragended(event) { // if (!event.active) simulation.alphaTarget(0); event.subject.fx = null; event.subject.fy = null; } return d3 .drag() .on("start", dragstarted) .on("drag", dragged) .on("end", dragended); } return Object.assign(svg.node(), { scales: { color }, simulation }); }31:T5cf,function forceCollide(padding = 10, strength = 1) { let nodes; function force(alpha) { if (strength === 0) return; const quad = d3.quadtree( nodes, (d) => d.x, (d) => d.y ); for (const d of nodes) { quad.visit((q, x1, y1, x2, y2) => { let updated = false; if (q.data && q.data !== d) { let x = d.x - q.data.x, y = d.y - q.data.y, xSpacing = padding + (q.data.width + d.width) / 2, ySpacing = padding + (q.data.height + d.height) / 2, absX = Math.abs(x), absY = Math.abs(y), l, lx, ly; if (absX < xSpacing && absY < ySpacing) { l = Math.sqrt(x * x + y * y); lx = (absX - xSpacing) / l; ly = (absY - ySpacing) / l; // the one that's barely within the bounds probably triggered the collision if (Math.abs(lx) > Math.abs(ly)) { lx = 0; } else { ly = 0; } d.x -= x *= lx * strength * alpha; d.y -= y *= ly * strength * alpha; q.data.x += x; q.data.y += y; updated = true; } } return updated; }); } } force.initialize = (_) => (nodes = _); force.strength = (...args) => { if (args.length > 0) { strength = args[0]; return force; } return strength; }; return force; }32:T764,renderTree = (data, links, { width = 500, height = 500, zoomToData = false, radius = 8 } = {}) => { const tree = d3.quadtree(data); const [[x0, y0], [x1, y1]] = tree.extent(); const x = d3 .scaleLinear() .domain(zoomToData ? d3.extent(data, (d) => d[0]) : [x0, x1]) .range([0, width]); const y = d3 .scaleLinear() .domain(zoomToData ? d3.extent(data, (d) => d[1]) : [y0, y1]) .range([0, height]); const svg = d3 .create("svg") .style("background-color", "white") .attr("width", width) .attr("height", height) .attr("viewBox", [-radius, -radius, width + (2 * radius), height + (2 * radius)]); svg .append("g") .selectAll("line") .data(links) .join("line") .attr("stroke", "#bbb") .attr("stroke-width", 1) .attr("x1", (d) => x(d.source.datum[0])) .attr("y1", (d) => y(d.source.datum[1])) .attr("x2", (d) => x(d.target.datum[0])) .attr("y2", (d) => y(d.target.datum[1])); svg .append("g") .attr("fill", "none") .attr("stroke", "#ddd") .selectAll("rect") .data(extractNodes(tree)) .join("rect") .attr("class", "node") .attr("x", (d) => x(d.x0)) .attr("y", (d) => y(d.y0)) .attr("height", (d) => y(d.y1) - y(d.y0)) .attr("width", (d) => x(d.x1) - x(d.x0)); const point = svg .append("g") .attr("fill-opacity", 1) .selectAll("circle") .data(data) .join(enterDatum); function enterDatum(selection) { const groups = selection .append("g") .attr("transform", ([cx, cy]) => `translate(${[x(cx), y(cy)]})`); groups .append("circle") .attr("fill", "black") .attr("opacity", 0.3) .attr("r", radius); groups .append("text") .attr("font-size", "0.8em") .attr("text-anchor", "middle") .attr("dy", "0.34em") .text((d) => d[2]); } return svg.node(); }33:[{"id":"36a341b580810faa30fb66561e9cbd3a7c214695dc8d7083184e1919373a6ed8b14ebd9168e3750b20601d9922ebc6637628bf1ebc5ac1d4b0eda3a1f11d7ca8","href":"https://static.observableusercontent.com/files/36a341b580810faa30fb66561e9cbd3a7c214695dc8d7083184e1919373a6ed8b14ebd9168e3750b20601d9922ebc6637628bf1ebc5ac1d4b0eda3a1f11d7ca8","name":"us-states.json","type":"application/json","lastModified":1743267012724.328,"size":89263},{"id":"0333cef5f692ef62215df1b30b90e0d5fa059146797b3c79d759ab2b86bd9fba4d117a6d92cb8ab8ea781a92a8e08ff6bc06a72e911486f1467b6d64ce9787c1","href":"https://static.observableusercontent.com/files/0333cef5f692ef62215df1b30b90e0d5fa059146797b3c79d759ab2b86bd9fba4d117a6d92cb8ab8ea781a92a8e08ff6bc06a72e911486f1467b6d64ce9787c1","name":"stateData.json","type":"application/json","lastModified":1695402558550.506,"size":5504}] 2d:{"title":"Quad Tree Grid Packing","cells":[{"id":0,"value":"$2f","pinned":false,"hidden":false,"mode":"md"},{"id":323,"value":"viewof count = Inputs.range([5, 100], {label: \"Item Count\", step: 5, value: 15})","pinned":false,"hidden":false,"mode":"ojs"},{"id":886,"value":"viewof percentLinked = Inputs.range([0, 100], {\n label: \"Precent Linked\",\n step: 5,\n value: 0\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":522,"value":"viewof distribution = Inputs.select(DISTRIBUTIONS, {\n label: \"Distribution\",\n format: (d) => d.title,\n value: DISTRIBUTIONS[2]\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1020,"value":"viewof zoomToData = Inputs.toggle({label: \"Zoom To Data\", value: false})","pinned":false,"hidden":false,"mode":"ojs"},{"id":430,"value":"viewof regenerate = Inputs.button(\"Regenerate Data\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":249,"value":"htl.html`\n

Input + Quad Tree

\n ${renderTree(data, links, { zoomToData })}\n

Output Grid

\n ${renderGrid(nodes, links)}\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1270,"value":"viewof condense = Inputs.toggle({label: \"Condense Grid\", value: false})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1069,"value":"## US States","pinned":false,"hidden":false,"mode":"md"},{"id":1103,"value":"htl.html`\n

US States

\n ${renderGrid((condense ? condenseGrid : (d) => d)(usGrid), [], {\n getName: (d) => d.datum.state,\n width\n })}\n

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1381,"value":"htl.html`\n

US States Rotated

\n ${renderGrid((condense ? condenseGrid : (d) => d)(usGrid2), [], { getName: d => d.datum.datum.datum.state, width })}\n

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1440,"value":"viewof degrees = Inputs.range([-180, 180], {label: \"Degrees\", step: 1, value: 0})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1357,"value":"usGrid2 = constructPackedGrid(rotateItems(constructPackedGrid(rotateItems(usGrid, degrees), d => d.x, d => d.y), -degrees), d => d.x, d => d.y)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1672,"value":"fatGrid = usGrid.map((d) => ({\n ...d,\n x: d.x * 10,\n y: d.y * 10,\n width: 30,\n height: 30\n}))","pinned":false,"hidden":false,"mode":"ojs"},{"id":1850,"value":"ungrid = US_STATES.map((datum) => ({\n x: datum.longitude * 5,\n y: datum.latitude * -8,\n width: 30,\n height: 30,\n datum\n}))","pinned":false,"hidden":false,"mode":"ojs"},{"id":2405,"value":"viewof center = Inputs.toggle({label: \"Center\", value: true})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1831,"value":"viewof alphaTarget = Inputs.range([0, 1], {\n label: \"Alpha Target\",\n step: 0.05,\n value: 0.30\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":2614,"value":"viewof nodeAttract = Inputs.range([0, 10], {\n label: \"Node Attract\",\n step: 0.01,\n value: 0\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":2556,"value":"viewof nodeRepel = Inputs.range([0, 10], {\n label: \"Node Repel\",\n step: 0.01,\n value: 0\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1885,"value":"viewof linkStrength = Inputs.range([0, 0.5], {\n label: \"Link Strength\",\n step: 0.01,\n value: 0\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1881,"value":"viewof linkDistance = Inputs.range([0, 200], {\n label: \"Link Distance\",\n step: 1,\n value: 30\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":2708,"value":"viewof linkDistanceFactor = Inputs.range([0, 1], {\n label: \"Link Distance Factor\",\n step: 0.01,\n value: 0\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":2429,"value":"viewof originalPositionStrength = Inputs.range([0, 1], {\n label: \"Original Position\",\n step: 0.01,\n value: 0\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1976,"value":"viewof rectCollisionStrength = Inputs.range([0, 2], {\n label: \"Rectangular Collision Strength\",\n step: 0.1,\n value: 0\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":2631,"value":"viewof circeCollisionStrength = Inputs.range([0, 2], {\n label: \"Circular Collision Strength\",\n step: 0.1,\n value: 0\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":2334,"value":"viewof gridStrength = Inputs.range([0, 2], {\n label: \"Grid Strength\",\n step: 0.01,\n value: 0\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":2656,"value":"viewof orderXStrength = Inputs.range([0, 1], {\n label: \"Order X Strength\",\n step: 0.01,\n value: 0\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":2690,"value":"viewof orderYStrength = Inputs.range([0, 1], {\n label: \"Order Y Strength\",\n step: 0.01,\n value: 0\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":2237,"value":"viewof redraw = Inputs.button(\"Reset\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":1531,"value":"chart = (redraw, console.clear(), renderForce(US_STATES.map(d => ({...d, y: -d.y}))))","pinned":false,"hidden":false,"mode":"ojs"},{"id":2450,"value":"{\n const { force } = chart.simulation;\n\n chart.simulation.alphaTarget(alphaTarget);\n force(\"grid\").strength(gridStrength);\n force(\"rect-collide\").strength(rectCollisionStrength);\n force(\"circ-collide\").strength(circeCollisionStrength);\n force(\"original\").strength(originalPositionStrength);\n force(\"orderX\").strength(orderXStrength);\n force(\"orderY\").strength(orderYStrength);\n force(\"link\").strength(() => linkStrength);\n if (linkDistanceFactor === 0) {\n force(\"link\").distance(() => linkDistance);\n } else {\n force(\"link\").distance((d) => oDistance(d.source, d.target) * linkDistanceFactor);\n }\n force(\"charge\").strength(() => nodeAttract - nodeRepel);\n \n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1496,"value":"getLinks = (nodes, getId) => {\n const { halfedges, triangles } = d3.Delaunay.from(\n nodes,\n (d) => d.x,\n (d) => d.y\n );\n const linkMap = {};\n const links = [];\n const addLink = (i, j) => {\n const key = [Math.min(i, j).toString(), Math.max(i, j).toString()].join(\n \"-\"\n );\n if (!linkMap[key]) {\n const source = nodes[triangles[i]];\n const target = nodes[triangles[j]];\n \n links.push({\n source: getId(source),\n target: getId(target),\n });\n linkMap[key] = true;\n }\n };\n\n halfedges.forEach((j, i) => {\n if (j >= i) {\n addLink(i, j);\n }\n });\n\n return links;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3035,"value":"getLinksByState = (nodes, getId) => {\n const { halfedges, triangles } = d3.Delaunay.from(\n nodes,\n (d) => d.x,\n (d) => d.y\n );\n const linkMap = {};\n const links = [];\n const addLink = (i, j) => {\n const key = [Math.min(i, j).toString(), Math.max(i, j).toString()].join(\n \"-\"\n );\n if (!linkMap[key]) {\n const source = nodes[triangles[i]];\n const target = nodes[triangles[j]];\n \n links.push({\n source: getId(source),\n target: getId(target),\n });\n linkMap[key] = true;\n }\n };\n\n halfedges.forEach((j, i) => {\n if (j >= i) {\n addLink(i, j);\n }\n });\n\n return links;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1870,"value":"renderForce = (_data, size = 30) => {\n const height = 400;\n\n const xScale = d3\n .scaleLinear()\n .domain(d3.extent(_data, (d) => d.x))\n .range([-width / 2 + size, width / 2 - size]);\n\n const yScale = d3\n .scaleLinear()\n .domain(d3.extent(_data, (d) => d.y))\n .range([-height / 2 + size, height / 2 - size]);\n\n const data = _.cloneDeep(_data).map((d) => ({\n ...d,\n x: xScale(d.x),\n y: yScale(d.y),\n ox: xScale(d.x),\n oy: yScale(d.y),\n width: size,\n height: size\n }));\n\n const links = getLinks(data, (d) => d.state);\n\n return ForceGraph(\n { nodes: data, links },\n {\n nodeId: (d) => d.state,\n nodeGroup: (d) => d.group,\n nodeTitle: (d) => d.abbr,\n width,\n height,\n// linkStrength: () => 0,\n linkDistance: () => 0,\n nodeStrength: () => 0,\n collisionStrength: 0,\n gridStrength: 0,\n originalPositionStrength: 0,\n center,\n invalidation\n }\n );\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1557,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":1682,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":2192,"value":"function forceGrid(strength) {\n let nodes;\n const blend = (v1, v2, strength) => v1 * (1 - strength) + v2 * strength;\n\n function force(alpha) {\n if (strength === 0) return;\n const { cellWidth, cellHeight } = estabishGridProperties(nodes);\n\n nodes.forEach((node) => {\n// node.width = blend(node.width, cellWidth, strength);\n// node.height = blend(node.height, cellHeight, strength);\n const width = node.width;\n const height = node.height;\n\n \n node.x = blend(\n node.x,\n Math.floor(node.x / width) * width + width / 2,\n strength * alpha\n );\n node.y = blend(\n node.y,\n Math.floor(node.y / height) * height + height / 2,\n strength * alpha\n );\n });\n }\n\n force.initialize = (_) => (nodes = _);\n force.strength = (...args) => {\n if (args.length > 0) {\n strength = args[0];\n return force;\n }\n\n return strength;\n };\n \n return force;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2422,"value":"function forceOriginal(strength = 0) {\n let nodes;\n\n const blend = (v1, v2, strength) => v1 * (1 - strength) + v2 * strength;\n\n function force(alpha) {\n nodes.forEach((node) => {\n node.x = blend(node.x, node.ox, strength * alpha);\n node.y = blend(node.y, node.oy, strength * alpha);\n });\n }\n\n force.initialize = (_) => (nodes = _);\n force.strength = (...args) => {\n if (args.length > 0) {\n strength = args[0];\n return force;\n }\n\n return strength;\n }\n \n return force;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2643,"value":"function forceOrderX(strength = 0) {\n let nodes;\n\n const blend = (v1, v2, strength) => v1 * (1 - strength) + v2 * strength;\n\n function force(alpha) {\n nodes.forEach((target, i) => {\n nodes.slice(i + 1).forEach(test => {\n if (target.ox > test.ox && target.x < test.x) {\n target.x += (test.x - target.x) * strength * alpha;\n }\n });\n });\n }\n\n force.initialize = (_) => (nodes = _);\n force.strength = (...args) => {\n if (args.length > 0) {\n strength = args[0];\n return force;\n }\n\n return strength;\n }\n \n return force;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2687,"value":"function forceOrderY(strength = 0) {\n let nodes;\n\n const blend = (v1, v2, strength) => v1 * (1 - strength) + v2 * strength;\n\n function force(alpha) {\n nodes.forEach((target, i) => {\n nodes.slice(i + 1).forEach(test => {\n if (target.oy > test.oy && target.y < test.y) {\n target.y += (test.y - target.y) * strength * alpha;\n }\n });\n });\n }\n\n force.initialize = (_) => (nodes = _);\n force.strength = (...args) => {\n if (args.length > 0) {\n strength = args[0];\n return force;\n }\n\n return strength;\n }\n \n return force;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":375,"value":"## Data","pinned":false,"hidden":false,"mode":"md"},{"id":86,"value":"nodes = (condense ? condenseGrid : d => d)(constructPackedGrid(data))","pinned":false,"hidden":false,"mode":"ojs"},{"id":757,"value":"links = createLinks(nodes, percentLinked / 100)","pinned":false,"hidden":false,"mode":"ojs"},{"id":15,"value":"data = regenerate, createRandomPoints(count, distribution.getDist())","pinned":false,"hidden":false,"mode":"ojs"},{"id":1720,"value":"US_STATES = FileAttachment(\"stateData.json\")\n .json()\n .then((rows) => rows.map((d) => ({ ...d, x: d.longitude, y: d.latitude })))","pinned":false,"hidden":false,"mode":"ojs"},{"id":1898,"value":"Plot.plot({\n height: 500,\n width,\n x: { _axis: null, grid: true },\n y: { _axis: null, grid: true },\n marks: [\n Plot.dot(US_STATES, { x: (d) => d.x, y: (d) => d.y, fill: \"#c88\", r: 10 }),\n Plot.text(US_STATES, {\n x: (d) => d.x,\n y: (d) => d.y,\n text: (d) => d.abbr,\n tip: true,\n fontWeight: \"bold\"\n })\n ]\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":2666,"value":"byOrder = {\n const ordered = [...US_STATES]\n .sort((a, b) => d3.ascending(a.x, b.x))\n .map((d, i) => ({ ...d, x: i }))\n .sort((a, b) => d3.ascending(a.y, b.y))\n .map((d, i) => ({ ...d, y: i }));\n return ordered;\n return constructPackedGrid(\n ordered,\n (d) => d.x,\n (d) => d.y\n ).map(({ datum, ...rest }) => ({ ...datum, ...rest }));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2665,"value":"Plot.plot({\n height: 500,\n width,\n x: { _axis: null, grid: true },\n y: { _axis: null, grid: true },\n marks: [\n Plot.dot(byOrder, { x: (d) => d.x, y: (d) => d.y, fill: \"#c88\", r: 10 }),\n Plot.text(byOrder, {\n x: (d) => d.x,\n y: (d) => d.y,\n text: (d) => d.abbr,\n tip: true,\n fontWeight: \"bold\"\n })\n ]\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1151,"value":"usGrid = constructPackedGrid(\n _.cloneDeep(US_STATES),\n (d) => d.x,\n (d) => d.y\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1377,"value":"function rotateItems(grid, degrees) {\n const radians = (degrees * Math.PI) / 180;\n\n return grid.map(({ x, y, ...rest }) => ({\n ...rest,\n x: x * Math.cos(radians) - y * Math.sin(radians),\n y: x * Math.sin(radians) + y * Math.cos(radians)\n }));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2776,"value":"## Neighbors","pinned":false,"hidden":false,"mode":"md"},{"id":3058,"value":"neighbors = computeNeighbors(await FileAttachment(\"us-states.json\") .json()\n .then((d) => d.features))","pinned":true,"hidden":false,"mode":"ojs"},{"id":3098,"value":"usStates = await FileAttachment(\"us-states.json\") .json()\n .then((d) => d.features)","pinned":true,"hidden":false,"mode":"ojs"},{"id":3100,"value":"usStates.map(d => d.properties.name)","pinned":true,"hidden":false,"mode":"ojs"},{"id":3066,"value":"neighbors.map(([a, b]) => [a.properties.name, b.properties.name]).filter(d => d.includes(\"California\"))","pinned":true,"hidden":false,"mode":"ojs"},{"id":3094,"value":"neighborMap = computeNeighborMap(neighbors)","pinned":true,"hidden":false,"mode":"ojs"},{"id":3086,"value":"computeNeighborMap = (neighbors, getId = (d) => d.properties.name) => {\n const bothWays = [...neighbors, ...neighbors.map(([a, b]) => [b, a])].sort(\n ([a, b]) => d3.ascending(getId(a), getId(b))\n );\n\n return bothWays;\n \n const map = d3.group(bothWays, (d) => getId(d[0]));\n\n [...map.keys()].forEach((key) =>\n map.set(\n key,\n map.get(key).map((d) => getId(d[1]))\n )\n );\n\n return map;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3056,"value":"computeNeighbors = shapes => {\n\n return shapes.map((shape1, i) =>\n shapes\n .slice(i + 1)\n .filter((state2) => areNeighbors(shape1, state2))\n .map((state2) => [shape1, state2])\n ).flat();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":3083,"value":"areNeighbors = (shape1, shape2) =>\n turf.booleanTouches(\n turf.multiPolygon(shape1).geometry.coordinates,\n turf.multiPolygon(shape2).geometry.coordinates\n )","pinned":false,"hidden":false,"mode":"ojs"},{"id":2596,"value":"## Notes\n\n### Normalize Map\n\n```js\nPlot.map(\n { x: Plot.normalize(\"extent\"), y: Plot.normalize(\"extent\") },\n { x: (d) => d.x, y: (d) => d.y, fill: \"#c88\", r: 10 }\n)\n```","pinned":false,"hidden":false,"mode":"md"},{"id":11,"value":"## Code","pinned":false,"hidden":false,"mode":"md"},{"id":1289,"value":"// use quad tree to identify duplicates, rathar than this non-sense.\n\nperterbateDuplicates = (rawData, xDim, yDim) => {\n const data = _.cloneDeep(rawData);\n\n const perterbation = () => Number.EPSILON * d3.randomUniform(100, 101)();\n\n data.forEach((d1, i) =>\n data.forEach((d2, j) => {\n if (i !== j && d1[xDim] === d2[xDim] && d1[yDim] === d2[yDim]) {\n d1[xDim] += perterbation();\n d1[yDim] += perterbation();\n }\n })\n );\n\n return data;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":139,"value":"constructPackedGrid = (data, getX = (d) => d[0], getY = (d) => d[1]) => {\n const { cellWidth, cellHeight } = estabishGridProperties(data, getX, getY);\n\n const fluffyGrid = data.map((datum) => ({\n x: Math.floor(getX(datum) / cellWidth),\n y: Math.floor(getY(datum) / cellHeight),\n datum\n }));\n \n return packDimension(packDimension(fluffyGrid, \"x\"), \"y\");\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":76,"value":"estabishGridProperties = (data, getX = d => d.x, getY = d => d.y) => {\n const tree = d3.quadtree().x(getX).y(getY).addAll(data);\n \n let cellWidth = Infinity;\n let cellHeight = Infinity;\n extractNodes(tree).map(({ x0, y0, x1, y1 }) => {\n cellWidth = Math.min(cellWidth, x1 - x0);\n cellHeight = Math.min(cellHeight, y1 - y0);\n })\n\n const [[x0, y0], [x1, y1]] = tree.extent();\n\n return { cellWidth, cellHeight, cols: (x1 - x0) / cellWidth, rows: (y1 - y0) / cellHeight };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1139,"value":"condenseGrid = (rawGrid, xDim = \"x\", yDim = \"y\") => {\n const grid = _.cloneDeep(rawGrid);\n const canCombineSets = (set1, set2, dim) =>\n new Set([...set1, ...set2].map((d) => d[dim])).size ===\n set1.length + set2.length;\n\n const combineSets = (data, fromIndex, toIndex, dim1, dim2) => {\n const from = data.filter((d) => d[dim1] === fromIndex);\n const to = data.filter((d) => d[dim1] === toIndex);\n\n if (canCombineSets(from, to, dim2)) {\n from.forEach((d) => (d[dim1] = to[0][dim1]));\n return true;\n }\n\n return false;\n };\n\n d3.range(...d3.extent(grid, (d) => d[xDim])).forEach((i) => {\n combineSets(grid, i, i + 1, xDim, yDim);\n });\n\n d3.range(...d3.extent(grid, (d) => d[yDim])).forEach((i) => {\n combineSets(grid, i, i + 1, yDim, xDim);\n });\n\n return packDimension(packDimension(grid, yDim), xDim);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":177,"value":"packDimension = (items, dimensionField = \"x\") => {\n let nextId = 0;\n\n return items\n .sort((a, b) => a[dimensionField] - b[dimensionField])\n .map((item, i) => ({\n ...item,\n [dimensionField]:\n i === 0 || item[dimensionField] === items[i - 1][dimensionField]\n ? nextId\n : ++nextId\n }));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":678,"value":"createLinks = (nodes, percent = 0.2, getId = (d) => d.datum[2]) =>\n nodes\n .map((source, i) =>\n d3\n .shuffle(nodes.slice(i + 1))\n .slice(0, (nodes.length - i) * percent)\n// .map((target) => ({ source: getId(source), target: getId(target) }))\n .map((target) => ({ source, target }))\n )\n .flat()","pinned":false,"hidden":false,"mode":"ojs"},{"id":2693,"value":"distance = (a, b) => Math.sqrt(Math.pow(b.x - a.x, 2), Math.pow(b.y - a.y, 2))","pinned":false,"hidden":false,"mode":"ojs"},{"id":2754,"value":"oDistance = (a, b) => Math.sqrt(Math.pow(b.ox - a.ox, 2), Math.pow(b.oy - a.oy, 2))","pinned":false,"hidden":false,"mode":"ojs"},{"id":497,"value":"### Render","pinned":false,"hidden":false,"mode":"md"},{"id":211,"value":"renderGrid = (\n nodes,\n links,\n {\n getX = (d) => d.x,\n getY = (d) => d.y,\n width = 500,\n height = 500,\n getName = (d) => d.datum[2]\n } = {}\n) =>\n Plot.plot({\n width,\n height,\n x: {\n grid: true,\n domain: d3.range(d3.min(nodes, getX), d3.max(nodes, getX) + 1),\n axis: null\n },\n y: {\n domain: d3.range(d3.min(nodes, getY), d3.max(nodes, getY) + 1),\n grid: true,\n axis: null\n },\n marks: [\n Plot.arrow(links, {\n x1: (d) => d.source.x,\n y1: (d) => d.source.y,\n x2: (d) => d.target.x,\n y2: (d) => d.target.y,\n stroke: \"#bbb\",\n headLength: 0\n }),\n\n Plot.cell(nodes, {\n x: getX,\n y: getY,\n rx: \"50%\",\n ry: \"50%\",\n fill: \"#999\"\n }),\n Plot.text(nodes, {\n x: getX,\n y: getY,\n text: getName,\n fill: \"black\",\n fontSize: \"1.1em\",\n fontWeight: \"bold\"\n })\n ]\n })","pinned":false,"hidden":false,"mode":"ojs"},{"id":20,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":499,"value":"### Utility","pinned":false,"hidden":false,"mode":"md"},{"id":62,"value":"extractNodes = (quadtree) => {\n const nodes = [];\n quadtree.visit(\n (node, x0, y0, x1, y1, ...rest) =>\n void nodes.push({ x0, y0, x1, y1, node, ...rest })\n );\n return nodes;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":5,"value":"createRandomPoints = (count = 100, getDistributors) => {\n return Array.from({ length: count }, (_, id) => {\n const [randomX, randomY] = getDistributors();\n return [randomX(), randomY(), id];\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":528,"value":"multiCluster = (clusterCount = d3.randomInt(3, 8)(), stdDev = 0.4) => {\n const centerX = d3.randomUniform(10);\n const centerY = d3.randomUniform(10);\n\n const clusters = d3\n .range(clusterCount)\n .map(() => [\n d3.randomNormal(centerX(), stdDev),\n d3.randomNormal(centerY(), stdDev)\n ]);\n\n const clusterSelect = d3.randomInt(clusters.length);\n\n return () => clusters[clusterSelect()];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":518,"value":"DISTRIBUTIONS = [\n {\n title: \"Uniform\",\n getDist: () => () => [d3.randomUniform(), d3.randomUniform()]\n },\n {\n title: \"Normal\",\n getDist: () => () => [d3.randomNormal(1, 0.17), d3.randomNormal(1, 0.17)]\n },\n { title: \"Multi Cluster\", getDist: multiCluster }\n]","pinned":false,"hidden":false,"mode":"ojs"},{"id":571,"value":"## Imports","pinned":false,"hidden":false,"mode":"md"},{"id":573,"value":"tubeMap = require(\"d3-tube-map/dist/d3-tube-map.min.js\").then(d => d.tubeMap)","pinned":false,"hidden":false,"mode":"ojs"},{"id":2783,"value":"import {usData} from \"@bratter/us-map\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":2769,"value":"turf = require('@turf/turf@7')","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}