CODEWITHSUNDEEP
d3.js
angus l
angus l

Reputation: 1587

Why is D3 quadtree dropping nodes?

I’m having issues with D3’s excellent quadtree appearing to drop nodes unpredictably. I can understand that it might not return all nodes if they are closely overlapping, but it would be very useful to understand more about when this might happen so I can work around it.

But that assumes that I’m not misusing it. If I run this with 10,000 points in data below, I get about a consistent ~29% drop in leaf nodes. With only 200 I can get one drop. This feels too high.

  1. Am I doing something wrong with my quadtree implementation?

  2. What could I do to work round this?

    var quadtree = d3.geom.quadtree() .x(function(d){return d[0];}) .y(function(d){return d[1];});

    var data = d3.range(10000) .map(function(d){ return [ Math.random(), Math.random() ]; });

If I run this count of quadtree leaves, I get a number below data.length:

var qt = quadtree(data),
    count = 0;
qt.visit(function(p,x1,y1,x2,y2){
    if(p.leaf)count++;
});

But if I run this filter, it returns an empty array suggesting that they are all there:

data.filter(function(d){return qt.find([d.x,d.y]).id !== d.id;});

Where am I going wrong?!

Upvotes: 1

Views: 349

Answers (1)

angus l
angus l

Reputation: 1587

Leaf and point are not interchangeable. Points can exist on internal nodes.

https://github.com/mbostock/d3/wiki/Quadtree-Geom

Upvotes: 1

Related Questions