lwthatcher/.block

## .block
license: mit
height: NaN
scrolling: no
border: yes

## README.md

      
    Raw
  

              README.md
            
          
    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

  
## findAll.js

tree_filter = function(x, y, search, ...params) {
  var node = this._root
  var t = {x:x, y:y,
    	x0: this._x0,
      y0: this._y0,
      x3: this._x1,
      y3: this._y1,
      quads: [],
      node: node}

//   search.init(t, params)
  if (t.node) {t.quads.push(new Quad(t.node, t.x0, t.y0, t.x3, t.y3))};
  search.init(t, params)

	var i = 0;
  while (t.q = t.quads.pop()) {
    i++;
// 		console.log("q", t.q)
    // Stop searching if this quadrant can’t contain a closer node.
    if (!(t.node = t.q.node)
        || (t.x1 = t.q.x0) > t.x3
        || (t.y1 = t.q.y0) > t.y3
        || (t.x2 = t.q.x1) < t.x0
        || (t.y2 = t.q.y1) < t.y0) continue;

    // Bisect the current quadrant.
    if (t.node.length) {
      t.node.explored = true;
      var xm = (t.x1 + t.x2) / 2,
          ym = (t.y1 + t.y2) / 2;

      t.quads.push(
        new Quad(t.node[3], xm, ym, t.x2, t.y2),
        new Quad(t.node[2], t.x1, ym, xm, t.y2),
        new Quad(t.node[1], xm, t.y1, t.x2, ym),
        new Quad(t.node[0], t.x1, t.y1, xm, ym)
      );

      // Visit the closest quadrant first.
      if (t.i = (y >= ym) << 1 | (x >= xm)) {
        t.q = t.quads[t.quads.length - 1];
        t.quads[t.quads.length - 1] = t.quads[t.quads.length - 1 - t.i];
        t.quads[t.quads.length - 1 - t.i] = t.q;
      }
    }

    // Visit this point. (Visiting coincident points isn’t necessary!)
    else {
      var dx = x - +this._x.call(null, t.node.data),
          dy = y - +this._y.call(null, t.node.data),
          d2 = dx * dx + dy * dy;
      search.visit(t, d2);
    }
  }
// 	console.log("i", i);
  return t.result;
}

## index.html
<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}

        var sqrs = svg.append("g").attr("class", "squares")
            .selectAll(".square").data(nodes(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; });

//        console.log("squares", sqrs)

        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", 3);

        var halo = svg.append("circle").attr("class", "halo")
          .attr("cx", x)
          .attr("cy", y)
          .attr("r", radius);

       var rect_halo = svg.append("rect").attr("class", "halo")
       		.attr("x", x)
       		.attr("y", y)
       		.attr("width", 0)
       		.attr("height", 0)

       console.time('findAll');
       quadtree.findAll(x,y, search, ...params);
       console.timeEnd('findAll');

       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)
       }


      function toggleRadius(value) {
        if (!value) {
          halo.transition(t).attr("r", 0);
          params = [];
        }
        else {
          halo.transition(t).attr("r", radius);
          params = [radius];
        }
        clearScanned();
        runSearch();
      }

      function activateRectHalo() {
        halo.transition(t)
          .attr("r", 0)
        rect_halo.transition(t)
        	.attr("x", x - r_width/2)
        	.attr("y", y - r_height/2)
        	.attr("width", r_width)
        	.attr("height", r_width)
      }

      function setRadius(value) {
        radius = +value;
        params = [radius];

        halo.transition(t).attr("r", radius);

        clearScanned();
        runSearch();
      }

      function R_Width(value) {
        r_width = +value;
        params = [radius];

        console.log("new width", r_width)

        halo.transition(t).attr("r", radius);

        clearScanned();
        runSearch();
      }

      function R_Height(value) {
        r_height = +value;
        params = [radius];

        console.log("new height", r_height)

        halo.transition(t).attr("r", radius);

        clearScanned();
        runSearch();
      }


      function setSearch(name) {
        // clear all
        clearScanned();

        // switch to new search method
        console.log("using search method:", name);
        if (name === "radius") {
        	search = radiusSearch;
       		params = [radius];
          d3.select("#cbox-radius")
            .property("disabled", true)
            .property("checked", true);

          d3.select("#radius").attr("disabled", null);

          halo.transition(t).attr("r", radius);

          d3.select("#btn-radius").classed("active", true);
          d3.select("#btn-point").classed("active", null);
          d3.select("#btn-rect").classed("active", null);

          d3.select("#width")
            .property("disabled", true);
          d3.select("#height")
            .property("disabled", true);
        }
        else if (name === "point") {
          search = findSearch;
          params = [radius];
          d3.select("#cbox-radius").attr("disabled", null);
          d3.select("#radius").attr("disabled", null);

          d3.select("#btn-radius").classed("active", null);
          d3.select("#btn-point").classed("active", true);
          d3.select("#btn-rect").classed("active", null);

          d3.select("#width")
            .property("disabled", true);
          d3.select("#height")
            .property("disabled", true);
        }
        else if (name === "rect") {
          activateRectHalo()

          d3.select("#cbox-radius")
            .property("disabled", true);
          d3.select("#radius")
            .property("disabled", true);

          d3.select("#width").attr("disabled", null);
          d3.select("#height").attr("disabled", null);

          d3.select("#btn-radius").classed("active", null);
          d3.select("#btn-point").classed("active", null);
          d3.select("#btn-rect").classed("active", true);
        }
        // find all
				runSearch()
			}


      function runSearch() {
        var found = quadtree.findAll(x,y, search, ...params);
        if (found) found.selected = true;
        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)
       }
      }

      function clearScanned() {
        points.each(function(d) { d.scanned = d.selected = false; });
        if (show_Quads) sqrs.each(function(d) { d.explored = false; });
      }


       // 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>

## quad.js
Quad = function(node, x0, y0, x1, y1) {
  this.node = node;
  this.x0 = x0;
  this.y0 = y0;
  this.x1 = x1;
  this.y1 = y1;
}

## search.js

var radiusSearchInit = function(t, params) {
	t.result = [];
  var [radius] = params;
  t.x0 = t.x - radius, t.y0 = t.y - radius;
  t.x3 = t.x + radius, t.y3 = t.y + radius;
  t.radius = radius * radius;
}

var radiusSearchVisit = function(t, d2) {
  t.node.data.scanned = true;
  if (d2 < t.radius) {
  	do {t.result.push(t.node.data); t.node.data.selected = true;} while (t.node = t.node.next);
  }
}

var radiusSearch = {init: radiusSearchInit, visit:radiusSearchVisit}

var findInit = function(t, params) {
  var [radius] = params;
  if (radius == null || params.length === 0)
  {
    t.radius = Infinity;
  }
  else {
    t.x0 = t.x - radius, t.y0 = t.y - radius;
    t.x3 = t.x + radius, t.y3 = t.y + radius;
    t.radius = radius * radius;
  }
}

var findVisit = function(t, d2) {
  t.node.data.scanned = true;
  if (d2 < t.radius) {
    var d = Math.sqrt(t.radius = d2);
    t.x0 = t.x - d, t.y0 = t.y - d;
    t.x3 = t.x + d, t.y3 = t.y + d;
    t.result = t.node.data;
  }
}

var findSearch = {init:findInit, visit:findVisit}

	tree_filter = function(x, y, search, ...params) {
	var node = this._root
	var t = {x:x, y:y,
	x0: this._x0,
	y0: this._y0,
	x3: this._x1,
	y3: this._y1,
	quads: [],
	node: node}

	// search.init(t, params)
	if (t.node) {t.quads.push(new Quad(t.node, t.x0, t.y0, t.x3, t.y3))};
	search.init(t, params)

	var i = 0;
	while (t.q = t.quads.pop()) {
	i++;
	// console.log("q", t.q)
	// Stop searching if this quadrant can’t contain a closer node.
	if (!(t.node = t.q.node)
	\|\| (t.x1 = t.q.x0) > t.x3
	\|\| (t.y1 = t.q.y0) > t.y3
	\|\| (t.x2 = t.q.x1) < t.x0
	\|\| (t.y2 = t.q.y1) < t.y0) continue;

	// Bisect the current quadrant.
	if (t.node.length) {
	t.node.explored = true;
	var xm = (t.x1 + t.x2) / 2,
	ym = (t.y1 + t.y2) / 2;

	t.quads.push(
	new Quad(t.node[3], xm, ym, t.x2, t.y2),
	new Quad(t.node[2], t.x1, ym, xm, t.y2),
	new Quad(t.node[1], xm, t.y1, t.x2, ym),
	new Quad(t.node[0], t.x1, t.y1, xm, ym)
	);

	// Visit the closest quadrant first.
	if (t.i = (y >= ym) << 1 \| (x >= xm)) {
	t.q = t.quads[t.quads.length - 1];
	t.quads[t.quads.length - 1] = t.quads[t.quads.length - 1 - t.i];
	t.quads[t.quads.length - 1 - t.i] = t.q;
	}
	}

	// Visit this point. (Visiting coincident points isn’t necessary!)
	else {
	var dx = x - +this._x.call(null, t.node.data),
	dy = y - +this._y.call(null, t.node.data),
	d2 = dx * dx + dy * dy;
	search.visit(t, d2);
	}
	}
	// console.log("i", i);
	return t.result;
	}
	<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}

	var sqrs = svg.append("g").attr("class", "squares")
	.selectAll(".square").data(nodes(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; });

	// console.log("squares", sqrs)

	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", 3);

	var halo = svg.append("circle").attr("class", "halo")
	.attr("cx", x)
	.attr("cy", y)
	.attr("r", radius);

	var rect_halo = svg.append("rect").attr("class", "halo")
	.attr("x", x)
	.attr("y", y)
	.attr("width", 0)
	.attr("height", 0)

	console.time('findAll');
	quadtree.findAll(x,y, search, ...params);
	console.timeEnd('findAll');

	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)
	}



	function toggleRadius(value) {
	if (!value) {
	halo.transition(t).attr("r", 0);
	params = [];
	}
	else {
	halo.transition(t).attr("r", radius);
	params = [radius];
	}
	clearScanned();
	runSearch();
	}

	function activateRectHalo() {
	halo.transition(t)
	.attr("r", 0)
	rect_halo.transition(t)
	.attr("x", x - r_width/2)
	.attr("y", y - r_height/2)
	.attr("width", r_width)
	.attr("height", r_width)
	}

	function setRadius(value) {
	radius = +value;
	params = [radius];

	halo.transition(t).attr("r", radius);

	clearScanned();
	runSearch();
	}

	function R_Width(value) {
	r_width = +value;
	params = [radius];

	console.log("new width", r_width)

	halo.transition(t).attr("r", radius);

	clearScanned();
	runSearch();
	}

	function R_Height(value) {
	r_height = +value;
	params = [radius];

	console.log("new height", r_height)

	halo.transition(t).attr("r", radius);

	clearScanned();
	runSearch();
	}


	function setSearch(name) {
	// clear all
	clearScanned();

	// switch to new search method
	console.log("using search method:", name);
	if (name === "radius") {
	search = radiusSearch;
	params = [radius];
	d3.select("#cbox-radius")
	.property("disabled", true)
	.property("checked", true);

	d3.select("#radius").attr("disabled", null);

	halo.transition(t).attr("r", radius);

	d3.select("#btn-radius").classed("active", true);
	d3.select("#btn-point").classed("active", null);
	d3.select("#btn-rect").classed("active", null);

	d3.select("#width")
	.property("disabled", true);
	d3.select("#height")
	.property("disabled", true);
	}
	else if (name === "point") {
	search = findSearch;
	params = [radius];
	d3.select("#cbox-radius").attr("disabled", null);
	d3.select("#radius").attr("disabled", null);

	d3.select("#btn-radius").classed("active", null);
	d3.select("#btn-point").classed("active", true);
	d3.select("#btn-rect").classed("active", null);

	d3.select("#width")
	.property("disabled", true);
	d3.select("#height")
	.property("disabled", true);
	}
	else if (name === "rect") {
	activateRectHalo()

	d3.select("#cbox-radius")
	.property("disabled", true);
	d3.select("#radius")
	.property("disabled", true);

	d3.select("#width").attr("disabled", null);
	d3.select("#height").attr("disabled", null);

	d3.select("#btn-radius").classed("active", null);
	d3.select("#btn-point").classed("active", null);
	d3.select("#btn-rect").classed("active", true);
	}
	// find all
	runSearch()
	}


	function runSearch() {
	var found = quadtree.findAll(x,y, search, ...params);
	if (found) found.selected = true;
	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)
	}
	}

	function clearScanned() {
	points.each(function(d) { d.scanned = d.selected = false; });
	if (show_Quads) sqrs.each(function(d) { d.explored = false; });
	}



	// 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>
	Quad = function(node, x0, y0, x1, y1) {
	this.node = node;
	this.x0 = x0;
	this.y0 = y0;
	this.x1 = x1;
	this.y1 = y1;
	}

	var radiusSearchInit = function(t, params) {
	t.result = [];
	var [radius] = params;
	t.x0 = t.x - radius, t.y0 = t.y - radius;
	t.x3 = t.x + radius, t.y3 = t.y + radius;
	t.radius = radius * radius;
	}

	var radiusSearchVisit = function(t, d2) {
	t.node.data.scanned = true;
	if (d2 < t.radius) {
	do {t.result.push(t.node.data); t.node.data.selected = true;} while (t.node = t.node.next);
	}
	}

	var radiusSearch = {init: radiusSearchInit, visit:radiusSearchVisit}

	var findInit = function(t, params) {
	var [radius] = params;
	if (radius == null \|\| params.length === 0)
	{
	t.radius = Infinity;
	}
	else {
	t.x0 = t.x - radius, t.y0 = t.y - radius;
	t.x3 = t.x + radius, t.y3 = t.y + radius;
	t.radius = radius * radius;
	}
	}

	var findVisit = function(t, d2) {
	t.node.data.scanned = true;
	if (d2 < t.radius) {
	var d = Math.sqrt(t.radius = d2);
	t.x0 = t.x - d, t.y0 = t.y - d;
	t.x3 = t.x + d, t.y3 = t.y + d;
	t.result = t.node.data;
	}
	}

	var findSearch = {init:findInit, visit:findVisit}