31:T4c1,md`# Non-force-directed beeswarm of mobility **[Version 2](https://observablehq.com/@jtrim-ons/non-force-directed-beeswarm-of-mobility-version-2-no-priori) has tidier code than this one!** This is a 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. The priority queue isn't really necessary, but the _greater method can be tweaked to affect the layout. 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.`32:Tda6,class AccurateBeeswarm { constructor(items, radiusFun, xFun) { this.items = items; this.radiusFun = radiusFun; let radius = 2; this.diameter = radius * 2; this.diameterSq = this.diameter * this.diameter; this.xFun = xFun; this.tieBreakFn = x => x; this._oneSided = false; this.maxR = Math.max(...items.map(d => radiusFun(d))); this.rng = this._sfc32(1, 2, 3, 4); } withTiesBrokenRandomly() { this.tieBreakFn = this._sfc32(0x9E3779B9, 0x243F6A88, 0xB7E15162, 1); return this; } oneSided() { this._oneSided = true; return this; } calculateYPositions() { let all = this.items .map((d, i) => ({ datum: d, originalIndex: i, x: this.xFun(d), y: null, placed: false, forbiddenY: new UnionOfIntervals(), score: 0, 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 pq = new AccurateBeeswarmPriorityQueue(this.radiusFun); pq.push(...all); while (!pq.isEmpty()) { let item = pq.pop(); 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) * 3; this._updateYBounds(item, all, pq); } all.sort((a, b) => a.originalIndex - b.originalIndex); return all.map(d => ({ datum: d.datum, x: d.x, y: d.y })); } // Random number generator // 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; } _updateYBounds(item, all, pq) { 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( this._oneSided ); let prevScore = other.score; other.score = Math.abs(other.bestPosition); if (other.score > prevScore) { // It is never the case that other.score < prevScore here. // The if statement is unnecessary, but makes the algorithm // run a little faster. pq.deprioritise(other); } } } } }33:T731,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(oneSided = false) { 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 ((!oneSided || i.left >= 0) && Math.abs(i.left) < Math.abs(best)) best = i.left; if ((!oneSided || i.right >= 0) && Math.abs(i.right) < Math.abs(best)) best = i.right; } return zeroAvailable ? 0 : best; } }34:T84f,class AccurateBeeswarmPriorityQueue { // Based on https://stackoverflow.com/a/42919752 parent(i) { return ((i + 1) >>> 1) - 1; } left(i) { return (i << 1) + 1; } right(i) { return (i + 1) << 1; } constructor(radiusFun) { this.TOP = 0; this._heap = []; this.radiusFun = radiusFun; } size() { return this._heap.length; } isEmpty() { return this.size() == 0; } peek() { return this._heap[this.TOP]; } push(...values) { values.forEach(value => { value.heapPos = this.size(); this._heap.push(value); this._siftUp(); }); return this.size(); } pop() { const poppedValue = this.peek(); const bottom = this.size() - 1; if (bottom > this.TOP) { this._swap(this.TOP, bottom); } this._heap.pop(); this._siftDown(); return poppedValue; } // Caution: this only works if new priority is less than or equal to old one. deprioritise(item) { this._siftDown(item.heapPos); } _greater(i, j) { let a = this._heap[i]; let b = this._heap[j]; let ra = this.radiusFun(a.datum); let rb = this.radiusFun(b.datum); // The 5 in the following line was just chosen to make the plots look nice ra += a.tieBreaker * 5; rb += b.tieBreaker * 5; if (ra > rb) return true; if (ra < rb) return false; return a.tieBreaker < b.tieBreaker; } _swap(i, j) { let tmp = this._heap[i]; this._heap[i] = this._heap[j]; this._heap[j] = tmp; this._heap[i].heapPos = i; this._heap[j].heapPos = j; } _siftUp() { let node = this.size() - 1; while (node > this.TOP && this._greater(node, this.parent(node))) { this._swap(node, this.parent(node)); node = this.parent(node); } } _siftDown(node = this.TOP) { let l, r; let sz = this.size(); while ( ((l = this.left(node)), (r = this.right(node)), (l < sz && this._greater(l, node)) || (r < sz && this._greater(r, node))) ) { let maxChild = r < sz && this._greater(r, l) ? r : l; this._swap(node, maxChild); node = maxChild; } } }35:[] 2f:{"title":"Non-force-directed beeswarm of mobility","cells":[{"id":0,"value":"$31","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\" })","pinned":true,"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":79,"value":"max_pop = d3.max(mobility_data, d => d.pop)","pinned":false,"hidden":false,"mode":"ojs"},{"id":77,"value":"rScale = d3\n .scaleSqrt()\n .domain([0, max_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)\n .withTiesBrokenRandomly()\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":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":71,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":65,"value":"$34","pinned":true,"hidden":false,"mode":"ojs"},{"id":49,"value":"html``","pinned":true,"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":true,"hidden":false,"mode":"ojs"},{"id":160,"value":"import { Range } from \"@observablehq/inputs\"","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W35","stdlib":"1","titling":"auto"}