Fixed-Radius Near Neighbors

This is just a fork of armollica's block: Fixed-Radius Near Neighbors, but in this version I used a slightly newer version of d3-quadtree.

Fixed-radius near neighbors search from a set of 2D points. Uses a quadtree to accelerate the search. If a quadtree square is entirely outside the specified radius then none of the square's contained points is in the radius. This lets you significantly narrow down the set of points that need to be scanned. Orange dots are scanned points found to be outside the radius. Red dots are scanned points found to be inside the radius.

To test the efficiency of this method [armollica] did 100 searches on a set of 1 million random points layed out like above. Each search was done at a random point with a radius of 25. On average the brute force search method took 460 milliseconds to identify all points in the radius. Doing the exact same searches with the quadtree method took only 1.44 milliseconds on average.

This method is based on this example that uses a similar method for identifying points within a rectangle.

forked from armollica's block: Fixed-Radius Near Neighbors

<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>
       // overwrite d3.quadtree with later version, v0.6
//        d3.quadtree = d3_quadtree.quadtree;
       
       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 ax = (d) => d.x;
       var ay = (d) => d.y;

var quadtree = d3.quadtree(data)
          .extent([[-1, -1], [width + 1, height + 1]])

data.forEach(function(d, i) {
          var point = quadtree.add(d[0], d[1]);
          point.i = i;
        });

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);
          
        fixedRadiusSearch(quadtree, r, [x, y]);
       	//console.log("search complete");
        
        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);
            
            halo
              .attr("cx", mouse[0])
              .attr("cy", mouse[1]);
            
            points.each(function(d) { d.scanned = d.selected = false; });
            
            var found = fixedRadiusSearch(quadtree, r, mouse);
            
            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;
        }

// Find all points in `quadtree` that are within radius `r` of `point`
       function fixedRadiusSearch(quadtree, r, point) { 
         //console.log("search", r, quadtree, point)
          var cx = point[0], cy = point[1];
         	var result = [];
          var v = quadtree.visit(function(node, x0, y0, x1, y1) {
            //console.log("node", node, x0, y0, x1, y1)
            if (!node.length) {
              node.data.scanned = true;
              node.data.selected = pointInCircle(node.data, [cx, cy, r]);
              if (node.data.selected) {
                result.push(node);
              }
            }
            return rectangleOutsideCircle([[x0, y0],[x1, y1]], [cx, cy, r]);
          });
         return result;
        }
         
        function rectangleOutsideCircle(rect, circle) {
          var x0 = rect[0][0], y0 = rect[0][1],
              x1 = rect[1][0], y1 = rect[1][1];
          
          // Rectangle is inside circle if...
          
          // ...circle center is inside rectangle
          var isInside = pointInRectangle(circle, [[x0, y0], [x1, y1]]) ? true :
            // ...any of the rectangle's corners is inside the circle
            pointInCircle([x0, y0], circle) ? true :
            pointInCircle([x0, y1], circle) ? true :
            pointInCircle([x1, y1], circle) ? true :
            pointInCircle([x1, y0], circle) ? true :
            // ...any of the rectangle's sides intersects the circle
            lineIntersectsCircle([[x0, y0], [x1, y0]], circle) ? true :
            lineIntersectsCircle([[x1, y0], [x1, y1]], circle) ? true :
            lineIntersectsCircle([[x1, y1], [x0, y1]], circle) ? true :
            lineIntersectsCircle([[x0, y1], [x0, y0]], circle) ? true :
            false; // ...otherwise it's outside
         
          return !isInside;
        }
        
        function lineIntersectsCircle(line, circle) { 
          // Taken mostly from https://stackoverflow.com/a/1088058
          
          var x0 = line[0][0], y0 = line[0][1],
              x1 = line[1][0], y1 = line[1][1],
              cx = circle[0], cy = circle[1], r = circle[2];
          
          var lineDistance = distance([x0, y0], [x1, y1]);
          
          // [dx, dy] = direction vector of line
          var dx = (x1-x0)/lineDistance,
              dy = (y1-y0)/lineDistance;
          
          // Parametric equation for a line:
          // x = dx*t + x0
          // y = dy*t + y0
          // where 0 <= t <= 1
          
          // Compute parameter t for closest point to circle center 
          // (clamp t to be between line segment end points)
          var t = clamp(dx*(cx-x0) + dy*(cy-y0), 0, lineDistance);
          
          // Compute coordinates of point on line closest to circle center
          var px = t*dx + x0,
              py = t*dy + y0;
          
          // Get distance of this point from center
          var projectionDistance = distance2([cx, cy], [px, py]);
          
          return projectionDistance <= r*r;
        }

function pointInRectangle(point, rect) {
          var x = point[0], y = point[1],
              x0 = rect[0][0], y0 = rect[0][1],
              x1 = rect[1][0], y1 = rect[1][1];
          return (x0 <= x) && (x <= x1) && (y0 <= y) && (y <= y1);
        }

function clamp(d, min, max) {
          return d < min ? min : d > max ? max : d;
        }
     </script>
  </body>
</html>

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