This demonstrates finding the closest point to the mouse by searching a quadtree. As you descend into the quadtree, you track the closest point yet found and avoid searching cells that cannot contain closer points. Importantly, you must descend preferentially into closer cells so as to restrict the search more quickly.
Patrick Surry implemented a similar solution months earlier!
forked from mbostock‘s block: Quadtree Tree
forked from enjalot‘s block: Quadtree Cube
<!DOCTYPE html>
<meta charset="utf-8">
<title>Quadtree</title>
<style>
svg {
width: 960px;
height: 800px;
}
#mycanvas {
position: absolute;
top: 20px;
right: 20px;
width: 400px;
height: 400px;
}
.point {
fill: #999;
stroke: #fff;
pointer-events: none;
}
.point.scanned {
fill: orange;
fill-opacity: 1;
stroke: brown;
}
.point.selected {
fill: red;
fill-opacity: 1;
}
.node.selected {
stroke: red;
}
.leaf.selected rect {
stroke: red;
}
.leaf.selected circle {
fill: red;
}
.leaf rect.highlighted {
fill: #2ae8e2;
}
.leaf circle {
stroke: #fff;
fill: #999;
}
.leaf rect {
stroke: #111;
fill: #83979a;
}
.branch {
fill: none;
stroke: #111;
stroke-width: 3;
}
.branch.selected {
stroke: red;
}
.node {
fill: #83979a;
stroke: #ccc;
shape-rendering: crispEdges;
}
.node.highlighted {
fill: #5cf9e6;
}
.overlay {
fill: none;
pointer-events: all;
}
</style>
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js"></script>
<script src="aframe.min.js"></script>
<body>
<a-scene canvas="canvas: #mycanvas">
<canvas id="mycanvas"></canvas>
<a-entity position="0 0 0.8">
<a-entity rotation="0 0 0">
<a-entity camera look-controls wasd-controls></a-entity>
</a-entity>
</a-entity>
<a-light color="#9ddce6" position="-1 -3 2" intensity="0.3" type="hemisphere"></a-light>
<a-light color="#36e78e" position="1 3 2" intensity="0.3" type="hemisphere"></a-light>
<a-light color="#9ddce6" position="1 3 -2" intensity="0.5" type="directional"></a-light>
<!-- Sky -->
<a-sky color="#ecfcf4"></a-sky>
</a-scene>
<script>
d3.selection.prototype.moveToFront = function() {
return this.each(function(){
this.parentNode.appendChild(this);
});
};
var width = 400,
height = 400;
var cubeColor = "#c6c6c6"
var cubeDepth = 0.1;
var nodeHighlightColor = "#2ae8e2"
var leafSize = 16;
// scale x,y in a-frame
var axscale = d3.scale.linear()
.domain([0, width])
.range([-1, 1])
var ayscale = d3.scale.linear()
.domain([0, height])
.range([1, -1])
var data = d3.range(25).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([940, 250])
.children(function(d) {
return d.nodes;
})
var rects = nodes(quadtree)
console.log("quadtree", quadtree, rects);
var copy = walkTree(quadtree)
//copy.visit = quadtree.visit; //jank because i want depth on my nodes
var leaves = tree.nodes(copy)
var branches = tree.links(leaves)
console.log("copy", copy)
console.log("leaves", leaves, "branches\n", branches);
// not a self contained recursive function, oh well
var flattened = [];
function flattenTree(node) {
if(node.nodes && node.nodes.length) {
node.nodes.forEach(function(d) {
if(d) {
flattenTree(d)
}
})
}
var newNode = {
depth: node.depth,
leaf: node.leaf,
point: node.point,
x0: node.x0,
x1: node.x1,
y0: node.y0,
y1: node.y1
}
flattened.push(newNode)
}
flattenTree(copy);
console.log("flattened", flattened)
var svg = d3.select("body").append("svg")
var twodgroup = svg.append("g").classed("twodgroup", true)
.attr("transform", "translate(20, 20)")
var squares = twodgroup.selectAll(".node")
.data(flattened.reverse())
squares
.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; })
.on("mousemove", function(d){
var x = getX(d)
var y = getY(d)
var w = getWidth(d)
var h = getHeight(d)
//console.log(d, x, y ,w , h)
squares.classed("highlighted", false)
d3.select(this).classed("highlighted", true)
d3.selectAll("a-box")
.attr({
// opacity: 0.3
color: cubeColor
})
.filter(function(f) { return f === d})
.attr({
// opacity: 1
color: nodeHighlightColor
})
d3.selectAll(".leaf rect")
.classed("highlighted", false)
.filter(function(l,i) {
return (l.depth === d.depth
&& l.x0 === d.x0
&& l.y0 === d.y0
&& l.x1 === d.x1
&& l.y1 === d.y1)
})
.classed("highlighted", true)
})
var point = twodgroup.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);
/*
twodgroup.append("rect")
.attr("class", "overlay")
.attr("width", width)
.attr("height", height)
.on("mousemove", mousemoved);
*/
twodgroup.on("mousemove", mousemoved)
var treegroup = svg.append("g")
.attr("transform", "translate(10, 520)")
var branch = treegroup.selectAll(".branch")
.data(branches)
.enter().append("path").classed("branch", true)
.attr({
d: diagonal
})
var leaf = treegroup.selectAll(".leaf")
.data(leaves)
var leafEnter = leaf
.enter().append("g")
.classed("leaf", true)
.attr("transform", function(d) {
var x = d.x - leafSize/2
var y = d.y - leafSize/2
return "translate(" + [x,y] + ")"
})
leafEnter.append("rect")
.attr({
//x: function(d) { return d.x - leafSize/2},
//y: function(d) { return d.y - leafSize/2},
width: leafSize,
height: leafSize,
})
leafEnter.append("circle")
.attr({
cx: leafSize/2,
cy: leafSize/2,
r: function(d) { return d.leaf ? 4: 0 }
})
var scene = d3.select('a-scene');
if (scene.node().hasLoaded) {
renderScene();
} else {
scene.on('loaded', renderScene);
}
function getX(d) {
var x = axscale(d.x0) + getWidth(d)/2;
return x
}
function getY(d) {
var y = ayscale(d.y0) - getHeight(d)/2;
return y;
}
function getWidth(d) {
var w = Math.abs(d.x1 - d.x0)/width
return 2*w;
}
function getHeight(d) {
var h = Math.abs(d.y1 - d.y0)/height
return 2*h;
}
function renderScene() {
var cubes = scene.selectAll("a-box.rect")
.data(flattened)
cubes.enter().append("a-box")
.attr({
width: function(d) {
return getWidth(d)
},
height: function(d) {
//return cubeDepth
return getHeight(d)
},
depth: function(d) {
//return getHeight(d)
return cubeDepth
},
opacity: 1,
color: cubeColor,
position: function(d) {
//var x = ascale((d.x0 + d.x1)/2);
//var y = ascale((d.y0 + d.y1)/2);
var x = getX(d)
var y = getY(d)
var z = -1 + d.depth * cubeDepth;
return [x,y,z].join(" ")
}
})
}
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("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>