32:T471,md`# Non-force-directed beeswarm of mobility (version 2: no priority queue) **[Version 3](https://observablehq.com/@jtrim-ons/non-force-directed-beeswarm-of-mobility-version-3-no-union-o) has less code than this one!** This is a second very hacky attempt at a non-force-directed beeswarm with variable radius. It is based on [Josh Holder's work](https://observablehq.com/@jholder112233/d3-force-beeswarm-of-mobility), which (unlike this notebook) uses d3-force. The beeswarm code in this notebook is a version of [accurate-beeswarm-plot](https://github.com/jtrim-ons/accurate-beeswarm-plot), extended to handle circles of different sizes. Some observations: - The code in this workbook is not production quality!!! - Some of the gaps between circles are large and distracting in comparison to the force-directed version. - The non-force directed layout is very quick to calculate compared to the force-directed version. Try changing the width using the slider below. - The force-directed version seems to give reasonably accurate x values. The non-force-directed beeswarm has completely accurate x values; this is its main advantage.`33:Tbc5,class AccurateBeeswarm { constructor(items, radiusFun, xFun) { this.items = items; this.radiusFun = radiusFun; this.xFun = xFun; this.tieBreakFn = this._sfc32(0x9E3779B9, 0x243F6A88, 0xB7E15162, seed); this.maxR = Math.max(...items.map(d => radiusFun(d))); this.rng = this._sfc32(1, 2, 3, seed); } calculateYPositions() { let all = this.items .map((d, i) => ({ datum: d, originalIndex: i, x: this.xFun(d), y: null, placed: false, forbiddenY: new UnionOfIntervals(), bestPosition: 0, heapPos: -1 })) .sort((a, b) => a.x - b.x); all.forEach(function(d, i) { d.index = i; }); let tieBreakFn = this.tieBreakFn; all.forEach(function(d) { d.tieBreaker = tieBreakFn(d.x); }); let allSortedByPriority = [...all].sort((a, b) => { let key_a = this.radiusFun(a.datum) + a.tieBreaker * randomness1; let key_b = this.radiusFun(b.datum) + b.tieBreaker * randomness1; return key_b - key_a; }); for (let item of allSortedByPriority) { item.placed = true; // If nothing placed overlaps this circle on the x axis (even if // they were side by side), choose the y position at random. This // makes the plot look a bit more natural and less like the Mandelbrot // set! item.y = item.forbiddenY.head.next != item.forbiddenY.tail ? item.bestPosition : this.radiusFun(item.datum) * (this.rng() - .5) * randomness2; this._updateForbiddenYIntervals(item, all); } all.sort((a, b) => a.originalIndex - b.originalIndex); return all.map(d => ({ datum: d.datum, x: d.x, y: d.y })); } // Random number generator (for reproducibility) // https://stackoverflow.com/a/47593316 _sfc32(a, b, c, d) { let rng = function() { a >>>= 0; b >>>= 0; c >>>= 0; d >>>= 0; var t = (a + b) | 0; a = b ^ (b >>> 9); b = (c + (c << 3)) | 0; c = (c << 21) | (c >>> 11); d = (d + 1) | 0; t = (t + d) | 0; c = (c + t) | 0; return (t >>> 0) / 4294967296; }; for (let i = 0; i < 10; i++) { rng(); } return rng; } _updateForbiddenYIntervals(item, all) { for (let step of [-1, 1]) { let xDist; let r = this.radiusFun(item.datum); for ( let i = item.index + step; i >= 0 && i < all.length && (xDist = Math.abs(item.x - all[i].x)) < r + this.maxR; i += step ) { let other = all[i]; if (other.placed) continue; let sumOfRadii = r + this.radiusFun(other.datum); if (xDist >= r + this.radiusFun(other.datum)) continue; let yDist = Math.sqrt(sumOfRadii * sumOfRadii - xDist * xDist); let forbiddenInterval = [item.y - yDist, item.y + yDist]; other.forbiddenY.addInterval(forbiddenInterval); other.bestPosition = other.forbiddenY.bestAvailableValue(); } } } }34:T6d4,class UnionOfIntervals { constructor() { this.head = { right: -Infinity }; this.tail = { left: Infinity }; this.head.next = this.tail; this.tail.prev = this.head; } del(i) { i.prev.next = i.next; i.next.prev = i.prev; } insertBefore(interval, i) { interval.prev = i.prev; interval.next = i; interval.prev.next = interval; i.prev = interval; } addInterval(interval) { let l = interval[0]; let r = interval[1]; interval = { left: l, right: r }; let nxt; for (let i = this.head.next; i != this.tail; i = nxt) { nxt = i.next; // if `i` contains `interval`, do nothing if (i.left <= l && i.right >= r) { return; } // if `interval` contains `i`, delete `i` if (l <= i.left && r >= i.right) { this.del(i); } } for (let i = this.head.next; i != this.tail; i = nxt) { nxt = i.next; if (r <= i.left) { this.insertBefore(interval, i); return; } if (r > i.left && r < i.right) { i.left = l; return; } if (l < i.right) { if (r > i.next.left) { // combine i and i.next i.right = i.next.right; this.del(i.next); } else { i.right = r; } return; } } this.insertBefore(interval, this.tail); } bestAvailableValue() { let best = Infinity; let zeroAvailable = true; for (let i = this.head.next; i != this.tail; i = i.next) { if (i.left < 0 && i.right > 0) zeroAvailable = false; if (Math.abs(i.left) < Math.abs(best)) best = i.left; if (Math.abs(i.right) < Math.abs(best)) best = i.right; } return zeroAvailable ? 0 : best; } }35:[] 30:{"title":"Non-force-directed beeswarm of mobility (version 2: no priority queue)","cells":[{"id":0,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":13,"value":"height = 600","pinned":false,"hidden":false,"mode":"ojs"},{"id":15,"value":"viewof width = new Range([300, 1200], { value: 950, label: \"Width\", step: 10 })","pinned":false,"hidden":false,"mode":"ojs"},{"id":211,"value":"md`If Randomness 1 is zero, large circles are placed first. If it is set to a large value, circles are placed in a more-or-less random order.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":171,"value":"viewof randomness1 = new Range([0, 25], {\n value: 5,\n label: \"Randomness 1\",\n step: 1\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":214,"value":"md`A large value of Randomness 2 causes some of the earliest-placed circles to be placed far away from the y=0 line.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":181,"value":"viewof randomness2 = new Range([0, 25], {\n value: 5,\n label: \"Randomness 2\",\n step: 1\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":189,"value":"viewof seed = new Range([0, 25], {\n value: 1,\n label: \"RNG Seed\",\n step: 1\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":96,"value":"chart2 = {\n const svg = d3\n .create(\"svg\")\n .attr(\"height\", height)\n .attr(\"width\", width);\n\n svg\n .selectAll(\"circle\")\n .data(positionedData)\n .enter()\n .append(\"circle\")\n .attr(\"cx\", d => d.x)\n .attr(\"cy\", d => d.y + height * .4)\n .attr(\"r\", d => rScale(d.datum.pop))\n .style(\"fill\", \"#bdbdbd\");\n\n svg\n .append(\"g\")\n .call(d3.axisTop(xScale))\n .style(\"transform\", `translateY(${height * 0.75}px`);\n\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":77,"value":"rScale = d3\n .scaleSqrt()\n .domain([0, d3.max(mobility_data, d => d.pop)])\n .range([0, 8])","pinned":false,"hidden":false,"mode":"ojs"},{"id":81,"value":"xScale = d3\n .scaleLinear()\n .domain([-1, 0])\n .range([0, width])\n .clamp(true)","pinned":false,"hidden":false,"mode":"ojs"},{"id":74,"value":"positionedData = new AccurateBeeswarm(\n data,\n d => rScale(d.pop) + .2,\n d => xScale(d.pct_change)\n).calculateYPositions()","pinned":true,"hidden":false,"mode":"ojs"},{"id":83,"value":"data = mobility_data.filter(d => d.in_lockdown === \"TRUE\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":67,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":218,"value":"md`The UnionOfIntervals class represents a union of non-overlapping open intervals, sorted in ascending order. It is used by the algorithm to store the set of disallowed y values for an unplaced circle.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":71,"value":"$34","pinned":true,"hidden":false,"mode":"ojs"},{"id":49,"value":"html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"mobility_data = d3.csv(\"https://static01.nyt.com/newsgraphics/2020/03/27/coronavirus-behavior-int/d08526cd59a705b40c03e9950174af4a5bb72835/pct_change_04_01.csv\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":10,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":160,"value":"import { Range } from \"@observablehq/inputs\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W35","stdlib":"1","titling":"auto"}