quadtree

_.md

[ Launch: quadtree ] 35c693d8ba655a303920 by enjalot

config.json

{"description":"quadtree","endpoint":"","display":"svg","public":true,"require":[],"fileconfigs":{"inlet.js":{"default":true,"vim":false,"emacs":false,"fontSize":12},"_.md":{"default":true,"vim":false,"emacs":false,"fontSize":12},"config.json":{"default":true,"vim":false,"emacs":false,"fontSize":12},"style.css":{"default":true,"vim":false,"emacs":false,"fontSize":12}},"fullscreen":false,"play":false,"loop":false,"restart":false,"autoinit":true,"pause":true,"loop_type":"pingpong","bv":false,"nclones":15,"clone_opacity":0.4,"duration":3000,"ease":"linear","dt":0.01,"ajax-caching":true,"thumbnail":"http://i.imgur.com/zpQ8Yw2.png"}

inlet.js

//adapted from http://bl.ocks.org/patricksurry/6478178

var width = 200;
var height = 200;

var random = [[0.16643382632173598,0.7419698103331029],[0.5596713435370475,0.9075538499746472],[0.22632705164141953,0.769712520763278],[0.7369719881098717,0.7627149370964617],[0.8743528828490525,0.6298443539999425],[0.20230200816877186,0.6607718782033771],[0.677479307167232,0.05559924151748419],[0.4338662535883486,0.3875766391865909],[0.0649221062194556,0.4499512354377657],[0.6374880156945437,0.9186435316223651]]
var data = random.map(function(r) {
  return [r[0] * width, r[1] * height];
});

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

var color = d3.scale.linear()
    .domain([0, 8])  // max depth of quadtree
    .range(["#efe", "#060"]);
    
var svg = d3.select("svg")
.on("click", function (d) {
  var xy = d3.mouse(d3.selectAll('svg')[0][0]);
  
  svg.selectAll("#pt")
      .attr("cx", xy[0])
      .attr("cy", xy[1]);
  clicked(quadtree);
  //quadtree = add(xy);
});

var rect, point;
function render(q) {
  var g = svg.append("g").classed("points", true)
  .attr("transform", "translate(" + [50, 20] + ")")
  rect = g.selectAll(".node")
      .data(nodes(q))
  rect.exit().remove()
  rect
    .enter().append("rect")
    .attr("class", "node")
  rect
    .attr("x", function(d) { return d.x1; })
    .attr("y", function(d) { return d.y1; })
    .attr("width", function(d) { return d.x2 - d.x1; })
    .attr("height", function(d) { return d.y2 - d.y1; })
  
  point = g.selectAll(".point")
      .data(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 treerect;
function renderTree(q) {
  var list = nodes(q);

  var depths = []
  list.forEach(function(d) {
    if(!depths[d.depth]) {
      depths[d.depth] = { w: w(d), siblings: [d] };
    } else {
      depths[d.depth].siblings.push(d);
    }
  })
  
  
  var g = svg.append("g").classed("tree", true)
    .attr("transform", "translate(" + [50, height + 50] + ")")
  treerect = g.selectAll(".tnode")
      .data(list)
  treerect.exit().remove()
  treerect.enter().append("rect").classed("tnode", true)
  
  //console.log(q, list)
  
  var max = d3.max(list, function(d) { return d.depth });
  function w(d) {
    var wi = d.x2 - d.x1
    return wi;
  }
  function x(d) {
    var xx = 0;
    if(d.parent) {
      xx += (w(d) + 10) * d.parent.nodes.indexOf(d);
      xx += x(d.parent);
    }
    return xx;
  }
  treerect.attr({
    x: function(d) {
      return x(d);
    },
    y: function(d) { 
      var y = 0;
      for(var i = 0; i < d.depth; i++) {
        y += depths[i].w + 10
      }
      return y;
    },
    width: function(d) { return w(d) },
    height: function(d) { return w(d) }
  })
}

render(quadtree)
renderTree(quadtree)


svg.append("circle")
    .attr("id", "pt")
    .attr("r", 3)
    .attr("cx", width/2)
    .attr("cy", height/2)
    .style("fill", "yellow");

// PDS Collect a list of nodes to draw rectangles, adding extent and depth data
function nodes(quadtree) {
  var nodes = [];
  quadtree.depth = 0; // root
  quadtree.visit(function(node, x1, y1, x2, y2) {
    node.x1 = x1;
    node.y1 = y1;
    node.x2 = x2;
    node.y2 = y2;
    nodes.push(node);
    for (var i=0; i<4; i++) {
      if (node.nodes[i]) {
        node.nodes[i].depth = node.depth+1;
        node.nodes[i].parent = node;
      }
    }
  });
  return nodes;
}

      
function nearest(x, y, best, node) {
    var x1 = node.x1, y1 = node.y1, x2 = node.x2, y2 = node.y2;
    node.visited = true;
    // exclude node if point is farther away than best distance in either axis
    if (x < x1 - best.d || x > x2 + best.d || y < y1 - best.d || y > y2 + best.d) {
        return best;
    }
    // test point if there is one, potentially updating best
    var p = node.point;
    if (p) {
      p.scanned = true;
      var dx = p[0] - x, dy = p[1] - y, d = Math.sqrt(dx*dx + dy*dy);
      if (d < best.d) {
        best.d = d;
        best.p = p;
      }
    }
    // check if kid is on the right or left, and top or bottom
    // and then recurse on most likely kids first, so we quickly find a 
    // nearby point and then exclude many larger rectangles later
    var kids = node.nodes;
    var rl = (2*x > x1 + x2), bt = (2*y > y1 + y2);
    if (kids[bt*2+rl]) best = nearest(x, y, best, kids[bt*2+rl]);
    if (kids[bt*2+(1-rl)]) best = nearest(x, y, best, kids[bt*2+(1-rl)]);
    if (kids[(1-bt)*2+rl]) best = nearest(x, y, best, kids[(1-bt)*2+rl]);
    if (kids[(1-bt)*2+(1-rl)]) best = nearest(x, y, best, kids[(1-bt)*2+(1-rl)]);
    
    return best;
}

function add(xy) {
  data.push(xy)
  var q = d3.geom.quadtree()
    .extent([[-1, -1], [width + 1, height + 1]])
    (data);
  render(q);
  return q;
}

function clicked() {
    pt = d3.selectAll('#pt');
    var x = +pt.attr('cx'), y = +pt.attr('cy');
    
    point.each(function(d) { d.scanned = d.selected = false; });
    rect.each(function(d) { d.visited = false; });
    //treerect.each(function(d) { d.visited = false; });
    
    var best = nearest(x, y, {d: height+width, p: null}, quadtree);
    best.p.selected = true;
    point.classed("scanned", function(d) { return d.scanned; });
    point.classed("selected", function(d) { return d.selected; });
    rect.style('fill', function(d) { return d.visited ? color(d.depth) : 'none'; });
    treerect.style('fill', function(d) { return d.visited ? color(d.depth) : 'none'; });
}

//clicked();

style.css

.point {
  fill: #999;
}

.point.scanned {
  fill: #908ad5;
  fill-opacity: 1;
  stroke: #fff;
}

.point.selected {
  fill: #00d0ff;
  fill-opacity: 1;
}

.node {
  fill: none;
  stroke: #3a3a3a;
  stroke-opacity: 0.4;
  stroke-width: 1;
  shape-rendering: crispEdges;
}


.tnode {
  fill: none;
  stroke: #3a3a3a;
  stroke-opacity: 1;
  stroke-width: 1;
  shape-rendering: crispEdges;
}