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:

<!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");
    }

https://d3js.org/d3.v3.min.js

https://cdnjs.cloudflare.com/ajax/libs/dat-gui/0.5.1/dat.gui.min.js