Quadtree Search Filters

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.

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

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

forked from lwthatcher's block: Fixed-Radius Near Neighbors II

<html>
  <head>
    <link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css">
    <style>
			.square {
				fill: none;
				stroke: #ddd;
/*         shape-rendering: crispEdges; */
			}
      
      .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;
			}
      
      .counter {
        width: 100%
      }
      
      .title {
        font-weight: bold;
      }
      
      .small-text {
        cursor: default;
      }
      
      .square.explored {
        fill: slateblue;
      }
		</style>
  </head>
  <body>
<script src="https://d3js.org/d3.v4.js"></script>
<script src="quad.js"></script>
<script src="findAll.js"></script>
<script src="search.js"></script>
<div class="row">
	<div id="svg-cont" class="col-sm-10"></div>
		<div class="col-sm-2">
			<div class="row"><div class="col-sm-10"><button id="btn-radius" onclick="setSearch('radius')" class="btn btn-info active">Radius</button></div></div>
      
      <br>
      <div class="row"><div class="col-sm-10"><button id="btn-point" onclick="setSearch('point')" class="btn btn-info">Point</button></div></div>
      <br>
      
      <div class="row"><div class="col-sm-10"><button id="btn-rect" onclick="setSearch('rect')" class="btn btn-info">Rectangle</button></div></div>
      <hr>
      
      <div class="row"><div class="col-sm-10">
    		<div class="title">
          Radius:
          <label class="checkbox-inline small-text">
          	<input id="cbox-radius" type="checkbox" onclick="toggleRadius(this.checked)" disabled checked /> (Use Radius)
          </label>
        </div>
      	<input class="counter" id="radius" type="number" onchange="setRadius(this.value)" value=30></input>
  	</div></div>
  	<hr>
  	
  	<div class="row"><div class="col-sm-10">
    	<div class="title">Width: </div>
      <input class="counter" id="width" type="number" onchange="R_Width(this.value)" value=45 disabled></input>
      <br>
      <div class="title">Height: </div>
      <input class="counter" id="height" type="number" onchange="R_Height(this.value)" value=45 disabled></input>
    </div></div>
  </div>       
</div>
    
     <script>
       // add in 'findAll' function
       var treeProto = d3.quadtree.prototype;
       treeProto.findAll = tree_filter;

var width = 700,
           height = 400,
           radius = 30,
           r_width = 45,
           r_height = 45;
       var x = width/3,
           y = height/2;
       var t = d3.transition()
    		.duration(100)
    		.ease(d3.easeLinear); 
       
       var show_Quads = false;
       var search = radiusSearch;
       var params = [radius];
       
       var svg = d3.select("#svg-cont").append("svg")
          .attr("width", width)
          .attr("height", height);

var data = d3.range(1000)
          .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()
          .extent([[-1, -1], [width + 1, height + 1]])
        	.addAll(data)

var left_x = (mx) => {mx - r_width/2}
        var top_y = (my) => {my - r_height/2}

points
        .classed("scanned", function(d) { return d.scanned; })
        .classed("selected", function(d) { return d.selected; });
       
       if (show_Quads) {
         sqrs
          .classed("explored", (d) => {return d.explored;})
        	.attr("fill-opacity", 0.1)
       }

// Mouse Move 
       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);
         		rect_halo
        			.attr("x", x - r_width/2)
        			.attr("y", y - r_height/2)
        			.attr("width", r_width)
        			.attr("height", r_width)
         		
            
            clearScanned();
          	runSearch();
          });
       
       // Get coordinates of all squares in the tree       
       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;
      }
     </script>
  </body>
</html>

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