|
<!DOCTYPE html> |
|
<meta charset="utf-8"> |
|
<title>Quadtree</title> |
|
<style> |
|
|
|
svg { |
|
width: 960px; |
|
height: 800px; |
|
} |
|
.point { |
|
fill: #999; |
|
stroke: #fff; |
|
} |
|
|
|
.point.scanned { |
|
fill: orange; |
|
fill-opacity: 1; |
|
stroke: brown; |
|
} |
|
|
|
.point.selected { |
|
fill: red; |
|
fill-opacity: 1; |
|
} |
|
|
|
.node.selected { |
|
stroke: red; |
|
} |
|
.leaf.selected { |
|
fill: red; |
|
} |
|
|
|
.leaf { |
|
fill-opacity: 0.5; |
|
} |
|
.branch { |
|
fill: none; |
|
stroke: #111; |
|
} |
|
.branch.selected { |
|
stroke: red; |
|
} |
|
|
|
.node { |
|
fill: none; |
|
stroke: #ccc; |
|
shape-rendering: crispEdges; |
|
} |
|
|
|
.overlay { |
|
fill: none; |
|
pointer-events: all; |
|
} |
|
|
|
</style> |
|
<body> |
|
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js"></script> |
|
<script> |
|
d3.selection.prototype.moveToFront = function() { |
|
return this.each(function(){ |
|
this.parentNode.appendChild(this); |
|
}); |
|
}; |
|
|
|
var width = 900, |
|
height = 350; |
|
|
|
var data = d3.range(250).map(function(i) { |
|
return { |
|
id: i, |
|
x:Math.random() * width, |
|
y:Math.random() * height |
|
}; |
|
}); |
|
|
|
var diagonal = d3.svg.diagonal() |
|
.projection(function(d) { return [d.x, d.y]; }); |
|
|
|
var quadtree = d3.geom.quadtree() |
|
.extent([[-1, -1], [width + 1, height + 1]]) |
|
.x(function(d) { return d.x }) |
|
.y(function(d) { return d.y }) |
|
(data); |
|
|
|
|
|
function walkTree(node) { |
|
var nodes = []; |
|
if(node.nodes && node.nodes.length) { |
|
node.nodes.forEach(function(d) { |
|
if(d) { |
|
nodes.push(walkTree(d)) |
|
} |
|
}) |
|
} |
|
var newNode = { |
|
leaf: node.leaf, |
|
point: node.point, |
|
x0: node.x0, |
|
x1: node.x1, |
|
y0: node.y0, |
|
y1: node.y1 |
|
} |
|
if(nodes.length) newNode.nodes = nodes; |
|
return newNode; |
|
} |
|
|
|
|
|
var tree = d3.layout.tree() |
|
.size([width - 20, 250]) |
|
.children(function(d) { |
|
return d.nodes; |
|
}) |
|
|
|
var rects = nodes(quadtree) |
|
|
|
console.log("quadtree", quadtree, rects) |
|
|
|
var copy = walkTree(quadtree) |
|
var leaves = tree.nodes(copy) |
|
var branches = tree.links(leaves) |
|
|
|
console.log("leaves", leaves, "branches\n", branches); |
|
|
|
var svg = d3.select("body").append("svg") |
|
|
|
|
|
var squares = svg.selectAll(".node") |
|
.data(rects) |
|
.enter().append("rect") |
|
.attr("class", "node") |
|
.attr("x", function(d) { return d.x0; }) |
|
.attr("y", function(d) { return d.y0; }) |
|
.attr("width", function(d) { return d.y1 - d.y0; }) |
|
.attr("height", function(d) { return d.x1 - d.x0; }); |
|
|
|
var point = svg.selectAll(".point") |
|
.data(data) |
|
.enter().append("circle") |
|
.attr("class", "point") |
|
.attr("cx", function(d) { return d.x; }) |
|
.attr("cy", function(d) { return d.y; }) |
|
.attr("r", 4); |
|
|
|
svg.append("rect") |
|
.attr("class", "overlay") |
|
.attr("width", width) |
|
.attr("height", height) |
|
.on("mousemove", mousemoved); |
|
|
|
var treegroup = svg.append("g") |
|
.attr("transform", "translate(10, 500)") |
|
|
|
var branch = treegroup.selectAll(".branch") |
|
.data(branches) |
|
.enter().append("path").classed("branch", true) |
|
.attr({ |
|
d: diagonal |
|
}) |
|
|
|
|
|
var leaf = treegroup.selectAll(".leaf") |
|
.data(leaves) |
|
.enter().append("circle") |
|
.classed("leaf", true) |
|
.attr({ |
|
cx: function(d) { return d.x }, |
|
cy: function(d) { return d.y}, |
|
r: 3 |
|
}) |
|
|
|
|
|
|
|
function paintParentPath(node) { |
|
branch.filter(function(d) { return d.target === node}) |
|
.classed("selected", true) |
|
.each(function(d) { if(d.source) paintParentPath(d.source) }); |
|
|
|
} |
|
|
|
function mousemoved() { |
|
var p = quadtree.find(d3.mouse(this)); |
|
|
|
point.classed("scanned", function(d) { return d.scanned; }); |
|
point.classed("selected", function(d) { return d === p; }); |
|
squares.classed("selected", function(d) { return d.point === p}) |
|
.filter(function(d) { return d.point === p}) |
|
.moveToFront(); |
|
|
|
leaf |
|
.classed("selected", false) |
|
.attr({r: 3}) |
|
.filter(function(d) { return d.point === p }) |
|
.classed("selected", true) |
|
.attr({r: 6}) |
|
.moveToFront(); |
|
|
|
branch.classed("selected", false) |
|
.filter(function(d) { return d.target.point === p}) |
|
.classed("selected", true) |
|
.each(function(d) { |
|
//console.log(d.target.parent) |
|
if(d.source) paintParentPath(d.source) |
|
}) |
|
|
|
} |
|
|
|
// Collapse the quadtree into an array of rectangles. |
|
function nodes(quadtree) { |
|
var nodes = []; |
|
quadtree.visit(function(node, x0, y0, x1, y1) { |
|
node.x0 = x0, node.y0 = y0; |
|
node.x1 = x1, node.y1 = y1; |
|
nodes.push(node); |
|
}); |
|
return nodes; |
|
} |
|
|
|
</script> |