31:T408,md`# Compact beeswarm plot Mike Bostock's [dodge function](https://observablehq.com/@d3/beeswarm) implements a commonly-used strategy for generating [beeswarm layouts](http://www.cbs.dtu.dk/~eklund/beeswarm/). The points are placed one by one, from the lowest-valued to the highest-valued. Each point is placed at the lowest available *y* position that does not overlap any circle that has already been placed. The plot below gives an example. The number on each circle indicates the time at which it was placed. The earliest-placed circles are yellow, and later ones are blue. This approach has at least two benefits: points do not overlap, and the shape of the beeswarm gives an approximation of the density of the distribution. This notebook will introduce an alternative strategy for placing circles that retains these two benefits while often giving a more compact layout. The description is based on one-sided beeswarm plots for simplicity, but the method can easily be extended to create two-sided beeswarms.`32:T532,function dodge(data, { diameter = 1, x = d => d } = {}) { // This is a slightly-edited version of Mike Bostock's dodge() function. const diameter2 = diameter ** 2; const circles = data .map((d, i, data) => ({ x: +x(d, i, data), data: d })) .sort((a, b) => a.x - b.x); const epsilon = 1e-3; let head = null, tail = null; // Returns true if circle ⟨x,y⟩ intersects with any circle in the queue. function intersects(x, y) { let a = head; while (a) { if (diameter2 - epsilon > (a.x - x) ** 2 + (a.y - y) ** 2) { return true; } a = a.next; } return false; } let time = 0; // Place each circle sequentially. for (const b of circles) { // Remove circles from the queue that can’t intersect the new circle b. while (head && head.x < b.x - diameter2) head = head.next; // Choose the minimum non-intersecting tangent. if (intersects(b.x, (b.y = 0))) { let a = head; b.y = Infinity; do { let y = a.y + Math.sqrt(diameter2 - (a.x - b.x) ** 2); if (y < b.y && !intersects(b.x, y)) b.y = y; a = a.next; } while (a); } b.insertionTime = ++time; // Add b to the queue. b.next = null; if (head === null) head = tail = b; else tail = tail.next = b; } return circles; }33:T48e,function compactBeeswarm(data, { diameter = 1, x = d => d } = {}) { const diameter2 = diameter ** 2; // For placed circles, circle.y is the y position; for unplaced // circles, circle.y is the lowest currently-permitted y position. const circles = data .map((d, i, data) => ({ x: +x(d, i, data), placed: false, y: 0, data: d })) .sort((a, b) => a.x - b.x); // next() returns the point that is to be placed next function next() { let best; for (let c of circles) { if (c.placed) continue; if (!best || c.y < best.y) best = c; } return best; } // updateYValues(circle) updates the y values of unplaced points // that horizontally overlap circle. function updateYValues(circle) { for (let c of circles) { if (c.placed) continue; let xDiff = Math.abs(circle.x - c.x); if (xDiff >= diameter) continue; let yDiff = Math.sqrt(diameter2 - xDiff ** 2); c.y = Math.max(c.y, circle.y + yDiff); } } let time = 0; for (let i = 0; i < circles.length; i++) { let c = next(); c.placed = true; c.insertionTime = ++time; updateYValues(c); } return circles; }34:T404,md`## Implementations and examples of compact beeswarms [accurate-beeswarm-plot](https://github.com/jtrim-ons/accurate-beeswarm-plot) is a JavaScript implementation that aims for efficiency. The algorithm uses a priority queue to select which point will be placed next, and only updates the *y* values of circles that horizontally overlap (i.e. have *x* value within twice *r* of) the circle that has just been placed. The algorithm has *O(m log n)* time complexity, where *n* is the number of points and *m* is *n* plus the number of pairs of points that overlap horizontally. Some examples on Observable using accurate-beeswarm-plot are in [this collection](https://observablehq.com/collection/@jtrim-ons/compact-beeswarm-plots). The latest version of the [beeswarm package for R](https://github.com/aroneklund/beeswarm) has a simple implementation of compact beeswarms. To use this, select the "compactswarm" method. Both of these implementations have options including two-sided beeswarm plots and random tie-breaking.`35:[{"id":"53c407ee531bab128477148c9e28c49dd06bf83a93ae317e58dbb9fc819db0d4f6c4fb9646fa2fe20faad76addee20cfc360eab2362eeaec3340a5e4655b9996","href":"https://static.observableusercontent.com/files/53c407ee531bab128477148c9e28c49dd06bf83a93ae317e58dbb9fc819db0d4f6c4fb9646fa2fe20faad76addee20cfc360eab2362eeaec3340a5e4655b9996","name":"cars-2.csv","type":"application/octet-stream","lastModified":1618302709330.642,"size":20140}] 2f:{"title":"Compact beeswarm plot","cells":[{"id":1,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":353,"value":"dodgeChart = {\n const dodgedData = dodge(data, {\n diameter: radius * 2 + padding,\n x: d => x(d.value)\n });\n const svg = d3.create(\"svg\").attr(\"viewBox\", [0, 0, width, height]);\n\n svg.append(\"g\").call(xAxis);\n\n svg\n .append(\"g\")\n .selectAll(\"circle\")\n .data(dodgedData)\n .join(\"circle\")\n .attr(\"cx\", d => d.x)\n .attr(\"cy\", d => height - margin.bottom - radius - padding - d.y)\n .attr(\"r\", radius)\n .attr(\"fill\", d => colourScale(d.insertionTime / data.length))\n .attr(\"fill-opacity\", .4)\n .attr(\"stroke\", \"#bbb\");\n\n svg\n .append(\"g\")\n .selectAll(\"text\")\n .data(dodgedData)\n .join(\"text\")\n .attr(\"x\", d => d.x)\n .attr(\"y\", d => height - margin.bottom - radius - padding - d.y)\n .attr(\"text-anchor\", \"middle\")\n .attr(\"dominant-baseline\", \"central\")\n .style(\"font-size\", \"9px\")\n .text(d => d.insertionTime);\n\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":346,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":441,"value":"md`## Compact beeswarms\n\nThe standard beeswarm method described above places the data points in a predetermined order (left to right in our example, although right-to-left and randomly ordered are also possibilities). The new *compact beeswarm* method chooses, at each step, which point to place next by selecting a point that can be placed as close as possible to the *y*-axis without overlapping any previously-placed point. The plot below gives an example. In this example, ties are broken by preferring low-valued data points, but other strategies such as random tie-breaking are also possible.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":397,"value":"compactBeeswarmChart = {\n const beeswarmData = compactBeeswarm(data, {\n diameter: radius * 2 + padding,\n x: d => x(d.value)\n });\n const svg = d3.create(\"svg\").attr(\"viewBox\", [0, 0, width, height]);\n\n svg.append(\"g\").call(xAxis);\n\n svg\n .append(\"g\")\n .selectAll(\"circle\")\n .data(beeswarmData)\n .join(\"circle\")\n .attr(\"cx\", d => d.x)\n .attr(\"cy\", d => height - margin.bottom - radius - padding - d.y)\n .attr(\"r\", radius)\n .attr(\"fill\", d => colourScale(d.insertionTime / data.length))\n .attr(\"fill-opacity\", .4)\n .attr(\"stroke\", \"#bbb\");\n\n svg\n .append(\"g\")\n .selectAll(\"text\")\n .data(beeswarmData)\n .join(\"text\")\n .attr(\"x\", d => d.x)\n .attr(\"y\", d => height - margin.bottom - radius - padding - d.y)\n .attr(\"text-anchor\", \"middle\")\n .attr(\"dominant-baseline\", \"central\")\n .style(\"font-size\", \"9px\")\n .text(d => d.insertionTime);\n\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":453,"value":"md`The compactBeeswarm function below is a simple quadratic-time implementation of the compact beeswarm layout. Each data point has a boolean member placed which records whether the point's *y* value has already been fixed.\n\nBecause the algorithm has a strategy of choosing points that can be placed as low as possible, the following is true: the set of forbidden *y* values for each unplaced point is always an interval *[0,y)* for some value *y* specific to that point. The algorithm keeps track of each of these *y* values as the member variable y. When a point is placed, the y values for nearby unplaced points are updated.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":388,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":421,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":502,"value":"## More beeswarms\n\nI've also written [beeswarm code](https://observablehq.com/@jtrim-ons/non-force-directed-beeswarm-of-mobility-version-3-no-union-o) for circles that don't all have the same radius.","pinned":false,"hidden":false,"mode":"md"},{"id":3,"value":"data = (await FileAttachment(\"cars-2.csv\").csv({\n typed: true\n})).map(({ Name: name, Weight_in_lbs: value }) => ({ name, value: +value }))","pinned":false,"hidden":false,"mode":"ojs"},{"id":77,"value":"x = d3.scaleLinear()\n .domain(d3.extent(data, d => d.value))\n .range([margin.left, width - margin.right])","pinned":false,"hidden":false,"mode":"ojs"},{"id":108,"value":"xAxis = g => g\n .attr(\"transform\", `translate(0,${height - margin.bottom})`)\n .call(d3.axisBottom(x).tickSizeOuter(0))","pinned":false,"hidden":false,"mode":"ojs"},{"id":357,"value":"colourScale = chroma.scale(['yellow', '008ae5'])","pinned":false,"hidden":false,"mode":"ojs"},{"id":32,"value":"height = 450","pinned":false,"hidden":false,"mode":"ojs"},{"id":206,"value":"radius = width < 600 ? 5 : 6.5","pinned":false,"hidden":false,"mode":"ojs"},{"id":208,"value":"padding = 1.5","pinned":false,"hidden":false,"mode":"ojs"},{"id":102,"value":"margin = ({top: 20, right: 20, bottom: 30, left: 20})","pinned":false,"hidden":false,"mode":"ojs"},{"id":11,"value":"d3 = require(\"d3@6\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":316,"value":"chroma = require('chroma-js')","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W35","stdlib":"1","titling":"auto"}