D3 Examples - K-D Tree Nearest Neighbor

K-D Tree Nearest Neighbor

k-d tree nearest neighbor search (1-NN). The red dot is the nearest neighbor. Orange dots are scanned and not selected.

Compare to nearest neighbor search using quadtrees from this block. The k-d tree technique seems to scan more points, although the process of limiting the search set is different so this isn't really a direct measure of which is more efficient.

Here's a more up-to-date version of this block that works for k nearest neighbors.

xxxxxxxxxx
 
<html>
  <head>
    <style>
      .line {
        fill: none;
        stroke: #ccc;
      }
      
      .point {
        fill: #999;
        stroke: #fff;
      }
​
      .point.scanned {
        fill: orange;
        stroke: #999;
      }
      
      .point.selected {
        fill: red;
        stroke: #999;
      }
      
      .halo {
        fill: none;
        stroke: red;
      }
    </style>
  </head>
  <body>
     <script src="kd-tree.js"></script>
     <script src="https://d3js.org/d3.v3.min.js" charset="utf-8"></script>
     <script>
       var width = 960,
           height = 500;
       
       var svg = d3.select("body").append("svg")
        .attr("width", width)
        .attr("height", height);
       
       var data = d3.range(2000)
        .map(function() {
          return {
            x: width * Math.random(),
            y: height * Math.random(),
            value: d3.random.normal()() // just for testing purposes
          };
        });
        
        var tree = KDTree()
          .x(function(d) { return d.x; })
          .y(function(d) { return d.y; })
          (data);
        
        svg.append("g").attr("class", "lines")
            .selectAll(".line").data(tree.lines([[0,0], [width, height]]))
          .enter().append("path")
            .attr("class", "line")
            .attr("d", d3.svg.line());
            
        var points = svg.append("g").attr("class", "points")
            .selectAll(".point").data(tree.flatten())
          .enter().append("circle")
            .attr("class", "point")
            .attr("cx", function(d) { return d.location[0]; })
            .attr("cy", function(d) { return d.location[1]; })
            .attr("r", 4);
        
        var halo = svg.append("circle").attr("class", "halo");
        
        update([width/3, height/2]);
        
        svg.append("rect").attr("class", "event-canvas")
          .attr("width", width)
          .attr("height", height)
          .attr("fill-opacity", 0)
          .on("mousemove", function() { update(d3.mouse(this)); });
          
        function update(point) {
          var nearest = tree.find(point);
              
          points
            .classed("scanned", function(d) { return nearest.scannedNodes.indexOf(d) !== -1; })
            .classed("selected", function(d) { return d === nearest.node; });
            
          halo
            .attr("cx", point[0])
            .attr("cy", point[1])
            .attr("r", nearest.distance);
        };
     </script>
  </body>
</html>
    