Skip to content

Instantly share code, notes, and snippets.

@enjalot
Last active June 17, 2023 09:47
Show Gist options
  • Save enjalot/778182a0cae1c2ff60186f7e7c1d350f to your computer and use it in GitHub Desktop.
Save enjalot/778182a0cae1c2ff60186f7e7c1d350f to your computer and use it in GitHub Desktop.
Quadtree Tree: Nearest Neighbors
license: gpl-3.0
height: 1060

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 Tree

<!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;
}
.point.near {
fill: blue;
}
.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 RADIUS = 50;
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([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 mouseCircle = svg.append("circle").classed("mouse", true)
.attr({
r: RADIUS,
fill: "none",
stroke: "#555"
})
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.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 xy = d3.mouse(this);
mouseCircle.attr({
cx: xy[0],
cy: xy[1]
});
// version of visit which doesn't mutate the tree
var hits = [];
var visits = [];
quadtree.visit(nearest({ x: xy[0], y: xy[1] }, RADIUS, hits, visits))
console.log("visits", visits)
point.classed("near", false)
svg.selectAll("circle.point").data(hits, function(d) { return d.id}).classed("near", true)
/*
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;
}
function nearest(node, radius, hits, visits) {
if(!hits) hits = [];
if(!visits) visits = [];
// we want to find everything within radius
var r = radius,
nx1 = node.x - r,
nx2 = node.x + r,
ny1 = node.y - r,
ny2 = node.y + r;
return function(quad, x1, y1, x2, y2) {
visits.push(quad)
if (quad.point && (quad.point !== node)) {
var x = node.x - quad.point.x,
y = node.y - quad.point.y,
l = Math.sqrt(x * x + y * y),
r = radius;
if (l < r) {
//quad.point.near = true
hits.push(quad.point)
} else {
//quad.point.near = false;
}
}
return x1 > nx2 || x2 < nx1 || y1 > ny2 || y2 < ny1;
}
}
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment