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