toolkit/javascript/d3/examples/quadtree/quadtree.html
author Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
Fri, 18 Apr 2014 14:31:58 +0200
changeset 51 79833eaa394a
parent 47 c0b4a8b5a012
permissions -rw-r--r--
set up second level for navigation
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
47
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
     1
<!DOCTYPE html>
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
     2
<html>
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
     3
  <head>
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
     4
    <title>Quadtree</title>
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
     5
    <script type="text/javascript" src="../../d3.js"></script>
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
     6
    <script type="text/javascript" src="../../d3.geom.js"></script>
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
     7
    <style type="text/css">
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
     8
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
     9
svg {
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    10
  padding: 2px;
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    11
}
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    12
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    13
circle {
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    14
  fill: lightsteelblue;
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    15
  stroke: steelblue;
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    16
  stroke-width: 1.5px;
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    17
}
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    18
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    19
rect {
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    20
  fill: none;
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    21
  stroke: #000;
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    22
  stroke-opacity: .3;
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    23
}
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    24
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    25
    </style>
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    26
  </head>
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    27
  <body>
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    28
    <script type="text/javascript">
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    29
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    30
var w = 500;
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    31
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    32
// Generate random points.
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    33
var data = d3.range(500).map(function() {
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    34
  return {
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    35
    x: Math.random() * w,
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    36
    y: Math.random() * w
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    37
  };
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    38
});
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    39
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    40
// Generate a quadtree of the specified data.
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    41
var quadtree = d3.geom.quadtree(data, 0, w);
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    42
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    43
var vis = d3.select("body").append("svg:svg")
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    44
    .attr("width", w)
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    45
    .attr("height", w)
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    46
    .style("pointer-events", "all");
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    47
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    48
vis.selectAll("rect")
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    49
    .data(nodes(quadtree))
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    50
  .enter().append("svg:rect")
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    51
    .attr("x", function(d) { return d.x; })
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    52
    .attr("y", function(d) { return d.y; })
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    53
    .attr("width", function(d) { return d.width; })
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    54
    .attr("height", function(d) { return d.height; });
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    55
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    56
vis.selectAll("circle")
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    57
    .data(data)
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    58
  .enter().append("svg:circle")
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    59
    .attr("cx", function(d) { return d.x; })
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    60
    .attr("cy", function(d) { return d.y; })
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    61
    .attr("r", 4.5);
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    62
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    63
// Highlight selected nodes using the quadtree.
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    64
vis.on("mousedown", function() {
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    65
  var m0 = d3.svg.mouse(this);
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    66
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    67
  var rect = d3.select(this).append("svg:rect")
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    68
      .style("fill", "#999")
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    69
      .style("fill-opacity", .5);
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    70
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    71
  d3.select(window).on("mousemove", function() {
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    72
    var m1 = d3.svg.mouse(rect.node()),
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    73
        x0 = Math.min(w, m0[0], m1[0]),
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    74
        y0 = Math.min(w, m0[1], m1[1]),
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    75
        x1 = Math.max(0, m0[0], m1[0]),
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    76
        y1 = Math.max(0, m0[1], m1[1]);
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    77
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    78
    data.forEach(function(d) { d.z = 0; })
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    79
    find(quadtree, x0, y0, x1, y1).forEach(function(d) { d.z = 1; });
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    80
    vis.selectAll("circle").style("fill", function(d) { return d.z ? "red" : null; });
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    81
    rect.attr("x", x0).attr("y", y0).attr("width", x1 - x0).attr("height", y1 - y0);
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    82
  });
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    83
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    84
  d3.select(window).on("mouseup", function() {
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    85
    rect.remove();
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    86
    d3.select(window).on("mousemove", null).on("mouseup", null);
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    87
  });
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    88
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    89
  d3.event.preventDefault();
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    90
});
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    91
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    92
// Collapse the quadtree into an array of rectangles.
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    93
function nodes(quadtree) {
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    94
  var nodes = [];
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    95
  quadtree.visit(function(node, x1, y1, x2, y2) {
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    96
    nodes.push({x: x1, y: y1, width: x2 - x1, height: y2 - y1});
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    97
  });
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    98
  return nodes;
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
    99
}
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
   100
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
   101
// Find the nodes within the specified rectangle.
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
   102
function find(quadtree, x0, y0, x3, y3) {
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
   103
  var points = [];
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
   104
  quadtree.visit(function(node, x1, y1, x2, y2) {
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
   105
    var p = node.point;
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
   106
    if (p && (p.x >= x0) && (p.x < x3) && (p.y >= y0) && (p.y < y3)) points.push(p);
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
   107
    return x1 >= x3 || y1 >= y3 || x2 < x0 || y2 < y0;
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
   108
  });
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
   109
  return points;
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
   110
}
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
   111
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
   112
    </script>
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
   113
  </body>
c0b4a8b5a012 add toolkit.html + démonstrateurs
Nicolas Sauret <nicolas.sauret@iri.centrepompidou.fr>
parents:
diff changeset
   114
</html>