Quadtree

On d3.quadtree(), in addition to the x,y coordinates required for each point, is it possible to include other objects/data associated with each point, so that when nearest neighbors are found, the associated object/data can be used?
How would such object/data be added and retrieved?
Thanks in advance.

Yes, it’s possible!

Suppose you have an array of objects called data, where the objects look like this {x:x_i,y:y_i,other:other_i}. The data can be attached either using the constructor like so:

const tree = d3.quadtree(data);

or explicitly using addAll(data).

const tree = d3.quadtree()
    .addAll(data);

The x- and y- components can be derived from the data using the .x() and .y() functions. Retrieving the data is natural, since d3.quadtree.find() and d3.quadtree.visit() return the entire datum of the relevant quadtree node or nodes.

In principle this is all in the d3-quadtree documentation, but it’s probably more helpful to see it in action. Here are two examples of cool notebooks where d3-quadtree is called with arrays of objects with extra properties and the properties are then used after searching the array (I tried to link to the precise cells where the quadtree is used):


Feel free to ask if anything is unclear or if you have any other questions, and merry christmas!

2 Likes

Thank you for the example.
Indeed it made things very clear. I was not getting it from just the documentation. After seeing the example, the documentation makes sense.
In the examples of nearest neighbor, these did not use of object/data associated with a target point (in just about every case, the data consisted of only the x,y coordinates).

in my case I ended up using:

tree=d3.quadtree()
.x(function(d){return d.x})
.y(function(d){return d.y})
.addAll(my_data)

my_data has the x,y coordinates in my_data.x and my_data.y
my_data also has other values for every point.

in finding nearest data I used

var base = projection.invert(d3.mouse(this)),
closest = tree.find(base[0],base[1],3)

this worked, and closest returns all the object/data associated with the target point.
(Note: I used projection.invert, because my original my_data.x and my_data.y was in longitude and latitude), I am using the d3.orthographic projection for my rendering

If you need more advanced search or filtering, have a look at this work-in-progress notebook:

Cool demo! Here’s a quick fork that fixes it in Firefox (offsetX and offsetY seem to be doing strange things causing the SVG to flicker a lot):

1 Like

Thanks! I’ve included your fix and made some small changes to improve readability.
In Firefox offsetX/Y seem to refer to e.target, while in Chrome they refer to the current element. Not sure who’s right.

1 Like