K-Nearest Neighbors

K-nearest neighbors search of a 2D set of points. Move the slider or scroll to change k.

The algorithm was adapted from this block

<html>
  <head>
    <style>
      body {
        font-family: monospace;
      }
      
      .k {
        position: absolute;
        left: 10px;
        top: 10px;
      }
      
      .k span {
        position: relative;
        bottom: 7px;
        padding: 0 10px;
      }
      
      .hull {
        fill: tomato;
        fill-opacity: 0.25;
        stroke: tomato;
        pointer-events: none;
      }
    </style>
  </head>
  <body>
    <div class="k">
     <span>K = 25</span><input type="range" name="k" value="25" min="1">
    </div>
    
     <script src="https://d3js.org/d3.v3.min.js" charset="utf-8"></script>
     <script src="k-nearest-neighbors.js"></script>
     <script>
       var width = 960,
           height = 500,
           k = 25;
       
       var kDiv = d3.select(".k")
        .on("change", function() {
          k = +kDiv.select("input").node().value;
          d3.select(this).select("span").text("K = " + k);
          findNearest.k(k);
        });
       
       var svg = d3.select("body").append("svg")
        .attr("width", width)
        .attr("height", height);
      
       // add invisible rectangle that will pick up mouse movement
       svg.append("rect")
        .attr("width", width)
        .attr("height", height)
        .style("fill-opacity", 0)
        .on("mousemove", mousemove)
        .on("wheel", function() {
          var wheelUp = event.deltaY < 0;
          wheelUp ? k++ : k--;
          k = clamp(k, 1, 100); // limit k to be between 1 and 100
          kDiv.select("input").node().value = k;
          kDiv.select("span").text("K = " + k);
          findNearest.k(k);
          mousemove.call(this);
        });
      
      var data = d3.range(500)
        .map(function(d) {
          return {
            x: d3.random.normal(width/2, width/8)(),
            y: Math.random() * height
          };
        });
      
      var findNearest = d3.kNearestNeighbors()
        .extent([[-1, -1], [width + 1, height + 1]])
        .x(function(d) { return d.x; })
        .y(function(d) { return d.y; })
        .k(k)
        .data(data);
        
      var hull = svg.append("path").attr("class", "hull");
      
      var circles = svg.append("g").attr("class", "circles")
          .selectAll("circle").data(data)
        .enter().append("circle")
          .attr("cx", function(d) { return d.x; })
          .attr("cy", function(d) { return d.y; })
          .attr("r", 2)
          .style("opacity", 0.5);
      
      function mousemove() {
        preventDefault(event);
        
        var nearest = findNearest(d3.mouse(this));
        
        // Draw convex hull around k-nearest points (if k > 1)
        hull.datum(d3.geom.hull(nearest))
          .attr("d", function(d) { 
            return d.length > 1 ? "M" + d.join("L") + "Z" : null; 
          });
       
        // Get corresponding "nearest" data points from original data array 
        nearest = nearest
          .map(function(d) { return data[d.i]; });
        
        // Color nearest points red
        circles
          .style("fill", function(d) {
            return nearest.indexOf(d) !== -1 ? "red" : null;
          });
      }
      
      function clamp(d, min, max) {
        return d < min ? min : d > max ? max : d;
      }
      
      function preventDefault(e) {
        e = e || window.event;
        if (e.preventDefault) e.preventDefault();
        e.returnValue = false;  
      }
     </script>
  </body>
</html>

https://d3js.org/d3.v3.min.js