D3 Examples - Fixed-Radius Near Neighbors II

Fixed-Radius Near Neighbors II

Performs a fixed-radius near neighbors search from a set of 2D points using d3-quadtree to speed up the search. Orange dots are points that were scanned but were found to be outside the radius. Red dots are scanned points found to be inside the radius.

This code is inspired and based off of armollica's block: Fixed-Radius Near Neighbors, however this code adds a slight optimization. Rather than calling quadtree.visit() it implements a varation taken from the quadtree.find() method's code written by Mike Bostock, which tries to look at the quads around the point first. This order of traversal allows it to explore fewer quads, and reduces the points outside of the bounding quads that are explored.

Note: The original example was based on this example that uses a similar method for identifying points within a rectangle.

armollica

Fixed-Radius Near Neighbors

xxxxxxxxxx
 
<html>
  <head>
    <style>
            .square {
                fill: none;
                stroke: #ddd;
            }
      
      .point {
        fill: #bbb;
        stroke: white;
      }
            
            .point.scanned {
                fill: orange;
        stroke: grey;
            }
            
            .point.selected {
                fill: red;
        stroke: grey;
            }
            
            .halo {
                fill: none;
                stroke: slategrey;
                stroke-width: 2px;
                stroke-dasharray: 4, 4;
            }
        </style>
  </head>
  <body>
     <script src="https://d3js.org/d3.v4.min.js"></script>
     <script src="quad.js"></script>
     <script src="findAll.js"></script>
     <script>
       // add in 'findAll' function
       var treeProto = d3.quadtree.prototype;
       treeProto.findAll = tree_findAll;
       
       var width = 960,
           height = 500,
           r = 50;
       
       var svg = d3.select("body").append("svg")
          .attr("width", width)
          .attr("height", height);
​
        var data = d3.range(2000)
          .map(function(d) { return [width * Math.random(), height * Math.random()]; });
​
        var addFunc = (d) => { d.selected = true; }
        var expFunc = (d) => { d.scanned = true; }
​
        var quadtree = d3.quadtree(data)
          .extent([[-1, -1], [width + 1, height + 1]])
​
​
        svg.append("g").attr("class", "squares")
            .selectAll(".square").data(squares(quadtree))
           .enter().append("rect")
            .attr("class", "square")
            .attr("x", function(d) { return d.x0; })
            .attr("y", function(d) { return d.y0; })
            .attr("width", function(d) { return d.x1 - d.x0; })
            .attr("height", function(d) { return d.y1 - d.y0; });
       
        var points = svg.append("g").attr("class", "points")
            .selectAll(".point")
                .data(quadtree.data())
            .enter().append("circle")
            .attr("class", "point")
            .attr("cx", function(d) { return d[0]; })
            .attr("cy", function(d) { return d[1]; })
            .attr("r", 4);
          
        var x = width/3,
            y = height/2;
              
        var halo = svg.append("circle").attr("class", "halo")
          .attr("cx", width/3)
          .attr("cy", height/2)
          .attr("r", r);
       
       //console.time('findAll');
       quadtree.findAll(x,y, r, addFunc, expFunc);
       //console.timeEnd('findAll');
​
        
        points
          .classed("scanned", function(d) { return d.scanned; })
          .classed("selected", function(d) { return d.selected; });
          
        svg.append("rect").attr("class", "event-canvas")
          .attr("width", width)
          .attr("height", height)
          .attr("fill-opacity", 0)
          .on("mousemove", function() { 
            var mouse = d3.mouse(this);
            x = mouse[0];
            y = mouse[1];
            
            halo
              .attr("cx", x)
              .attr("cy", y);
            
            points.each(function(d) { d.scanned = d.selected = false; });
            
            //console.time('findAll');
            quadtree.findAll(x,y, r, addFunc, expFunc);
            //console.timeEnd('findAll');
            
            points
              .classed("scanned", function(d) { return d.scanned; })
              .classed("selected", function(d) { return d.selected; });
          });
       
       // Get coordinates of all squares in the tree
       function squares(quadtree) {
          var squares = [];
          quadtree.visit(function(node, x0, y0, x1, y1) {
            if (node.length) squares.push({ x0:x0, y0:y0, x1:x1, y1:y1 }); 
          });
          return squares;
        }
     </script>
  </body>
</html>
    