Quadtree Tree: Nearest Neighbors

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 quadtree = d3.geom.quadtree()
    .extent([[-1, -1], [width + 1, height + 1]])
    .x(function(d) { return d.x })
    .y(function(d) { return d.y })
    (data);

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 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) });
  
}

// 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>

https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.5/d3.min.js