block by nitaku ea217200870e9077535bf2e06e9699aa

Quadtree aggregation

Full Screen

In this example, some points (in red) have been used to build a quadtree. The tree structure is then used to aggregate the number of points in each quad (counts obtained for the first level are displayed).

index.js

// Generated by CoffeeScript 1.10.0
(function() {
  var data, dots, enter_quads, height, qside, quads, quadtree, side, svg, vis, width;

  svg = d3.select('svg');

  width = svg.node().getBoundingClientRect().width;

  height = svg.node().getBoundingClientRect().height;

  side = Math.floor(Math.min(width, height) * 0.5);

  data = [[6, 6], [10, 10], [20, 20], [100, 0], [100, 10], [230, 75], [90, 130], [12, 210]];

  quadtree = d3.quadtree().extent([[0, 0], [side, side]]).addAll(data);

  qside = quadtree._x1 - quadtree._x0;

  quadtree.visitAfter(function(n) {
    if (n.length == null) {
      return n.size = 1;
    } else {
      return n.size = d3.sum(n, function(d) {
        if (d != null) {
          return d.size;
        } else {
          return 0;
        }
      });
    }
  });

  vis = svg.append('g').attrs({
    transform: "translate(" + ((width - qside) / 2) + "," + ((height - qside) / 2) + ")"
  });

  quads = vis.selectAll('.quad').data(quadtree.root());

  enter_quads = quads.enter().append('g').attrs({
    "class": 'quad',
    transform: function(d, i) {
      return "translate(" + (quadtree._x0 + i % 2 * qside / 2) + "," + (quadtree._y0 + Math.floor(i / 2) * qside / 2) + ")";
    }
  });

  enter_quads.append('rect').attrs({
    width: qside / 2,
    height: qside / 2,
    fill: function(d) {
      if (d != null) {
        return '#DDD';
      } else {
        return 'white';
      }
    }
  });

  enter_quads.filter(function(d) {
    return d != null;
  }).append('text').text(function(d) {
    return d.size;
  }).attrs({
    x: qside / 4,
    y: qside / 4,
    dy: '0.35em'
  });

  dots = vis.selectAll('.dot').data(data);

  dots.enter().append('circle').attrs({
    "class": 'dot',
    cx: function(d) {
      return d[0];
    },
    cy: function(d) {
      return d[1];
    },
    r: 2
  });

}).call(this);

index.html

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <title>Quadtree aggregation</title>
  <link type="text/css" href="index.css" rel="stylesheet"/>
  <script src="https://d3js.org/d3.v4.min.js"></script>
  <script src="https://d3js.org/d3-selection-multi.v0.4.min.js"></script>
</head>
<body>
  <svg></svg>
  <script src="index.js"></script>
</body>
</html>

index.coffee

svg = d3.select 'svg'
width = svg.node().getBoundingClientRect().width
height = svg.node().getBoundingClientRect().height

side = Math.floor(Math.min(width,height)*0.5)

data = [
  [6,6],
  [10,10],
  [20,20],
  [100,0],
  [100,10],
  [230,75],
  [90,130],
  [12,210]
]


quadtree = d3.quadtree()
  .extent [[0,0], [side, side]]
  .addAll data
  
qside = quadtree._x1 - quadtree._x0

# store a counter for the number of elements in each quad
quadtree.visitAfter (n) ->
  if not n.length?
    n.size = 1
  else
    n.size = d3.sum n, (d) -> if d? then d.size else 0


# VIS

vis = svg.append 'g'
  .attrs
    transform: "translate(#{(width-qside)/2},#{(height-qside)/2})"
  
quads = vis.selectAll '.quad'
  .data quadtree.root()
  
enter_quads = quads.enter().append 'g'
  .attrs
    class: 'quad'
    transform: (d,i) -> "translate(#{quadtree._x0 + i%2 * qside/2},#{quadtree._y0 + Math.floor(i/2) * qside/2})"

enter_quads.append 'rect'
  .attrs
    width: qside/2
    height: qside/2
    fill: (d) -> if d? then '#DDD' else 'white'  
    
enter_quads.filter((d) -> d?).append 'text'
  .text (d) -> d.size
  .attrs
    x: qside/4
    y: qside/4
    dy: '0.35em'
    
dots = vis.selectAll '.dot'
  .data data
  
dots.enter().append 'circle'
  .attrs
    class: 'dot'
    cx: (d) -> d[0]
    cy: (d) -> d[1]
    r: 2

index.css

body, html {
  padding: 0;
  margin: 0;
  height: 100%;
}
svg {
  width: 100%;
  height: 100%;
  background: white;
}

.quad rect {
  stroke: #555;
  shape-rendering: crispEdges;
}
.quad text {
  font-family: sans-serif;
  font-size: 64px;
  fill-opacity: 0.2;
  text-anchor: middle;
}

.dot {
  fill: red;
  fill-opacity: 0.2;
  stroke: #333;
}