D3 Examples - Custom Beeswarm III (perf. enhancement)

Custom Beeswarm III (perf. enhancement)

This block is a continuation of a previous one.

This sequel experiments a way to vizualise the distribution of things (whatever it is) in a horizontal way (ie. along the x-axis), where constraints/objectives are:

to maintain the exact position of each datum (represented by a circle) along the x-axis

to be able to hover each circle to show related datum (handle overlapping)

Compared to the previous block, this algorithm is faster, because of:

less collision checks (use a direct-access doubly-linked list of possible already arranged colliding circles, so that collision checks are restricted to a small area (square with side of 2*radius))

The more data to arrange, the more it is faster. The more circles are big (more possible collisions), the more it is faster.

The algorithm is:

(hyp) circles to draw are ordered (from right to left in this example)

(hyp) datum must have an identifier named 'id' (used for direct-access in the doubly-linked list)

(init) cf. function 'initArrangement'

loop1 - for each new circle to place Ci:

find already drawn circles susceptible to overlap (close enought to Ci, distance from Ci <= 2*r)

if AAC is empty

place Ci on the x-axis (Ci.y = 0), push Ci in AAC, continue loop1

loop2 - for each Ca in AAC:

place Ci above Ca
if Ci is a better placement than the already tested (best = closest to x-axis, consider absolute value)
- if Ci does not overlap others circles in AAC
  - retain y-position as the best till now
place Ci below Ca
if Ci is a better placement than the already tested
- if Ci does not overlap others circles in AAC
  - retain y-position as the best till now

place Ci at best y-position, add Ci to AAC

Acknowledgments to:

xxxxxxxxxx
 
<!DOCTYPE html>
<meta charset="utf-8">
<style>
  
  #under-construction {
    display: none;
    position: absolute;
    top: 200px;
    left: 300px;
    font-size: 40px;
  }
​
  circle {
    stroke-width: 1.5px;
  }
​
  line {
    stroke: #999;
  }
​
</style>
<body>
  <div id="under-construction">
    UNDER CONSTRUCTION
  </div>
    <script src="https://d3js.org/d3.v3.min.js"></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/dat-gui/0.5.1/dat.gui.min.js">
  </script>
  <script src="already_arranged_data.js"></script>
  <script>
    var width = 960,
        height = 500;
    var trendData = [];
        var config = {
      radius: 4,
      manyPoints: false
    };
​
    insertControls();
    
    var fill = d3.scale.linear().domain([1,150]).range(['lightgreen', 'pink']);
​
    var svg = d3.select("body").append("svg")
      .attr("width", width)
      .attr("height", height);
​
    svg.append("line")
        .attr("id", "x-axis")
      .attr("x1", 0)
      .attr("y1", height/2)
      .attr("x2", width)
      .attr("y2", height/2)
      .style("stroke", "lightgrey");
    
    var nodeContainer = svg.append("g").attr("id", "node-container");
        
    var tooltip, stem, rank, value;
    prepareTooltip();
    
    //-->for metrics purpose
    var informationPanel, computationTimeInfo, dataLengthInfo, posibleCollidersInfo, placementInfo, visitedCollidersInfo;
    prepareInformationPanel();
    
    
    var totalPossibleColliders, maxPossibleColliders,
        totalTestedPlacements,
        visitedColliderCount, totalVisitedColliders, maxVisitedColliders;
    //<--for metrics purpose
    
    
    ////////////////////////
    // Custom Arrangement //
    ////////////////////////
    
    var minDistanceBetweenCircles,
        minSquareDistanceBetweenCircles,
        xBasedPossibleColliders, // for collision detection, array of data, x-based sorted window of possible coliders
            AAD; // for collision detection, y-based sorted direct-access doubly-linked list of possible colliders, limit collision detection to neighbours
    
        function initArrangement() {
      minDistanceBetweenCircles = 2*config.radius;
      minSquareDistanceBetweenCircles = Math.pow(minDistanceBetweenCircles, 2);
      xBasedPossibleColliders = [];
      AAD = new AlreadyArrangedData();
      //-->for metrics purpose
      totalPossibleColliders = maxPossibleColliders = 0;
      totalTestedPlacements = 0;
      visitedColliderCount = totalVisitedColliders = maxVisitedColliders =0;
      //<--for metrics purpose
    };
    
    function updateXBasedPossibleColliders (datum) {
      //remove circles from XBasedPossibleColliders that are far away from datum
      var indexesToRemove = 0;
      xBasedPossibleColliders.every(function (xbpc) {
        if (Math.abs(datum.x-xbpc.x)>minDistanceBetweenCircles) {
          indexesToRemove++;
          AAD.remove(xbpc);
          return true;
        }
        return false;
      });
      xBasedPossibleColliders.splice(0,indexesToRemove);
      
      //-->for metrics purpose
      totalPossibleColliders += xBasedPossibleColliders.length;
      if (xBasedPossibleColliders.length > maxPossibleColliders) {
        maxPossibleColliders = xBasedPossibleColliders.length;
      }
      //<--for metrics purpose
    }
​
    function isBetterPlacement(datum, bestYPosition) {
      return Math.abs(datum.y) < Math.abs(bestYPosition);
    }
​
    function yPosRelativeToXbpc(xbpc, d) {
      // handle Float approximation with +1E-6
      return Math.sqrt(minSquareDistanceBetweenCircles-Math.pow(d.x-xbpc.x,2))+1E-6;
    }
    
    function placeBelow(d, aad, relativeYPos) {
      d.y = aad.y - relativeYPos;
      
      //showOnTheFlyCircleArrangement(d, "test");
    }
​
    function placeAbove(d, aad, relativeYPos) {
      d.y = aad.y + relativeYPos;
      
      //showOnTheFlyCircleArrangement(d, "test");
    }
​
    function areCirclesColliding(d0, d1) {
      visitedColliderCount++; //for metrics prupose
      
      return (Math.pow(d1.y-d0.y, 2) + Math.pow(d1.x-d0.x, 2)) < minSquareDistanceBetweenCircles;
    }
    
    function collidesWithBelow(datum, aad, AAD, visitCount) {
      if (aad === null) { // special case: y_min reached, no collision detected
        return false;
      } else if ((datum.y - aad.datum.y) > minDistanceBetweenCircles) {
        // stop visit, no collision detected, remaining data are too far away
        return false;
      } else if (areCirclesColliding(datum, aad.datum)) {
        return true;
      } else {
        // continue visit
        return collidesWithBelow(datum, aad.below, AAD, visitCount++)
      }
    }
    
    function collidesWithAbove(datum, aad, AAD, visitCount) {
      if (aad === null) { // special case: y_max reached, no collision detected
        return false;
      } else if ((aad.datum.y - datum.y) > minDistanceBetweenCircles) {
        // stop visit, no collision detected, remaining data are too far away
        return false;
      } else if (areCirclesColliding(datum, aad.datum)) {
        return true;
      } else {
        // continue visit
        return collidesWithAbove(datum, aad.above, AAD, visitCount++)
      }
    }
​
    function collidesWithOther (datum, aad, AAD) {
      var visitCount = 0;
      //visit below aad for collision check
      if (collidesWithBelow(datum, aad.below, AAD, visitCount++)) {
        return true;
      } else {
        //visit above aad for collision check
        return collidesWithAbove(datum, aad.above, AAD, visitCount++);
      }
    }
​
    function arrangeCircles (data) {
      initArrangement();
      data.forEach(function (d) {
        var bestYPosition = -Infinity,
            relativeYPos;
        updateXBasedPossibleColliders(d);
        if (xBasedPossibleColliders.length===0) {
          bestYPosition = 0;
        } else {
          //--> if data is NOT sorted
          //AAD.clear();
          //AAD.addMany(xBasedPossibleColliders);
          //--< if data is NOT sorted
          xBasedPossibleColliders.forEach(function(xbpc) {
            relativeYPos = yPosRelativeToXbpc(xbpc, d);
            placeBelow(d, xbpc, relativeYPos);
            if (isBetterPlacement(d, bestYPosition) &&
                !collidesWithOther(d, AAD.aad(xbpc), AAD)) {
              bestYPosition = d.y;
            }
            //-->for metrics purpose
              totalVisitedColliders += visitedColliderCount;
              if (visitedColliderCount > maxVisitedColliders) {
                maxVisitedColliders = visitedColliderCount;
              }
              visitedColliderCount = 0;
            //<--for metrics purpose
            placeAbove(d, xbpc, relativeYPos);
            if (isBetterPlacement(d, bestYPosition) &&
                !collidesWithOther(d, AAD.aad(xbpc), AAD)) {
              bestYPosition = d.y;
            }
            //-->for metrics purpose
              totalVisitedColliders += visitedColliderCount;
              if (visitedColliderCount > maxVisitedColliders) {
                maxVisitedColliders = visitedColliderCount;
              }
              visitedColliderCount = 0;
            //<--for metrics purpose
                totalTestedPlacements += 2; //for metrics purpose
          })
        };
        d.y = bestYPosition;
        xBasedPossibleColliders.push(d);
        AAD.add(d);
        //showOnTheFlyCircleArrangement(d, "final");
      });
    }
​
    function showCircles (data) {
      nodeContainer.selectAll("circle").remove();
      var node = nodeContainer.selectAll("circle")
          .data(data)
        .enter().append("circle")
          .attr("r", config.radius-0.75)
          .attr("cx", function(d) { return d.x; })
          .attr("cy", function(d) { return height/2 + d.y; })
          .style("fill", function(d) { return fill(d.rank); })
          .style("stroke", function(d) { return d3.rgb(fill(d.rank)).darker(); })
          .on("mouseenter", function(d) {
            stem.text(d.stem);
            rank.text(d.rank);
            value.text(d.trend);
            tooltip.transition().duration(0).style("opacity", 1); // remove fade out transition on mouseleave
          })
          .on("mouseleave", function(d) {
            tooltip.transition().duration(1000).style("opacity", 0);
          });
    }
    
    function drawBeeswarm() {
      var data = config.manyPoints? quadruple(trendData) : trendData;
            
      var startTime = Date.now();
      arrangeCircles(data);
      showMetrics(data, (Date.now()-startTime));
      
      showCircles(data);
    }
    
    
    ////////////////////////
    // bl.ocks' utilities //
    ////////////////////////
    
    function dottype(d) {
      d.id = d.stem;
      d.stem = d.stem;
      d.rank = +d.rank;
      d.trend = +d.trend;
      d.x = width/2+d.trend*6000;
      d.y = 0;
      trendData.push(d);
      return d;
    }
    
    d3.csv("data.csv", dottype, function(error, data) {
      if (error) throw error;
      drawBeeswarm()
    });
​
    function quadruple(data) {
      // Quadruples data while maintaining order and uniq id
      var quadrupledData = [],
          i;
      data.forEach(function(d) {
        for (i=0; i<3; i++) {
          quadrupledData.push({
            id: d.id+"_"+i,
            stem: d.stem,
            rank: d.rank,
            trend: d.trend,
            x: d.x+i*1E-3,
            y: d.y
          })
        }
        quadrupledData.push(d);
      })
      return quadrupledData;
    }
    
    function insertControls () {
      var ctrls = new dat.GUI({width: 200});
      radiusCtrl = ctrls.add(config, "radius", 1, 20);
      radiusCtrl.onChange(function(value) {
        drawBeeswarm(trendData);
      });
      manyPointsCtrl = ctrls.add(config, "manyPoints");
      manyPointsCtrl.onChange(function(value) {
        drawBeeswarm();
      });
    }
    
    function prepareTooltip() {
      tooltip = svg.append("g")
        .attr("id", "tooltip")
        .attr("transform", "translate("+[width/2, 50]+")")
        .style("opacity", 0);
      var titles = tooltip.append("g").attr("transform", "translate("+[-5,0]+")")
      titles.append("text").attr("text-anchor", "end").text("stem(fr):");
      titles.append("text")
        .attr("text-anchor", "end")
        .attr("transform", "translate("+[0,15]+")")
        .text("rank:");
      titles.append("text")
        .attr("text-anchor", "end")
        .attr("transform", "translate("+[0,30]+")")
        .text("x-value:");
      var values = tooltip.append("g").attr("transform", "translate("+[5,0]+")")
      stem = values.append("text")
        .attr("text-anchor", "start");
      rank = values.append("text")
        .attr("text-anchor", "start")
        .attr("transform", "translate("+[0,15]+")");
      value = values.append("text")
        .attr("text-anchor", "start")
        .attr("transform", "translate("+[0,30]+")");
    }
    
    function prepareInformationPanel() {
      var i=4;
      informationPanel = svg.append("g")
        .attr("id", "infomation-panel")
        .attr("transform", "translate("+[width-20, height-20]+")");
      computationTimeInfo = informationPanel.append("text")
        .attr("text-anchor", "end")
        .attr("transform", "translate("+[0,-15*i--]+")");
      dataLengthInfo = informationPanel.append("text")
        .attr("text-anchor", "end")
        .attr("transform", "translate("+[0,-15*i--]+")");
      possibleCollidersInfo = informationPanel.append("text")
        .attr("text-anchor", "end")
        .attr("transform", "translate("+[0,-15*i--]+")");
      placementInfo = informationPanel.append("text")
        .attr("text-anchor", "end")
        .attr("transform", "translate("+[0,-15*i--]+")");
      visitedCollidersInfo = informationPanel.append("text")
        .attr("text-anchor", "end");
    }
    
    function showMetrics(data, elapsed) {
      computationTimeInfo.text("Arrangement took: "+elapsed+" ms");
      dataLengthInfo.text("# data: "+data.length);
      possibleCollidersInfo.text("# possible colliders: ~"+Math.round(totalPossibleColliders/data.length)+" per data ("+maxPossibleColliders+" max, "+totalPossibleColliders+" total)");
      placementInfo.text("# tested placements: ~"+Math.round(totalTestedPlacements/data.length)+" per data ("+(maxPossibleColliders*2)+" max, "+totalTestedPlacements+" total)");
      visitedCollidersInfo.text("# collision checks: ~"+Math.round(totalVisitedColliders/totalTestedPlacements)+" per placement ("+maxVisitedColliders+" max, "+totalVisitedColliders+" total)")
    }
​
    function showOnTheFlyCircleArrangement(d, type) {
      nodeContainer.selectAll("circle.test").remove();
      nodeContainer.append("circle")
        .datum(d)
        .classed(type, true)
        .attr("r", config.radius)
        .attr("cx", function(d) { return d.x; })
        .attr("cy", function(d) { return height/2 + d.y; })
        .style("fill", function(d) { return fill(d.rank); })
        .style("stroke", function(d) { return d3.rgb(fill(d.rank)).darker(); })
    }
  </script>
</body>
    