Related #3, maybe there’s a way to support d3-hierarchy’s iteration methods.

Elsewhere in D3 (such as in d3-voronoi and d3-shape’s line) we use [x, y] to represent a two-dimensional point. Currently d3-force uses {x: x, y: y} instead, and it’s the desire to avoid creating duplicate objects to store the particles in the quadtree that necessitated the same representation here.

However, we could just as easily use {0: x, 1: y} in d3-force, and then we could use the more natural representation here. The alternative would be to switch everywhere else in D3 over to using {x: x, y: y}, but that would be a pain and there are times where [x, y] is really nice, like "M" + points.join("L").

Currently, quadtree.find returns one point even if many coincident points are in the tree.

var quadtree = d3.quadtree([[1, 1, "red"], [1, 1, "green"], [0, 0, "blue"]]);
var result = quadtree.find(1,1);

result will be [1, 1, "green"].

I'm working with a point-of-interest dataset that contains many locations at the same coordinates (e.g., stores in the same mall), and my desired behavior is to return all of the points at that one location [[1, 1, "green"], [1, 1, "red"]]. I have created a fork that does this with a couple minor changes. I would create a PR, but they are breaking changes because the results are now an array rather than a single value. It may not be worth trying to merge as is.

Hi, It took me some time to find this examlple

// Find the nodes within the specified rectangle.
function search(quadtree, x0, y0, x3, y3) {
  quadtree.visit(function(node, x1, y1, x2, y2) {
    if (!node.length) {
      do {
        var d = node.data;
        d.scanned = true;
        d.selected = (d[0] >= x0) && (d[0] < x3) && (d[1] >= y0) && (d[1] < y3);
      } while (node = node.next);
    }
    return x1 >= x3 || y1 >= y3 || x2 < x0 || y2 < y0;
  });
}

Please add this method to the tree, or at least add it to the README

Related d3/d3#1788 d3/d3#1991.

Perhaps this:

var tree = d3.quadtree(nodes);

Should be shorthand for this:

var tree = d3.quadtree().addAll(nodes);

And this:

var tree = d3.quadtree(nodes, x, y);

Should be shorthand for this:

var tree = d3.quadtree().x(x).y(y).addAll(nodes);

For consistency with d3-hierarchy.

I have revised findAll (see the discussion in #18):
https://observablehq.com/d/ff2450667f13132f

also prepared a quadtree.findInPolygon() algorithm (which was fun!) (ping @gka)
https://observablehq.com/d/54a6e96b6630b0d9

I think both functions could be added to this module—however findInPolygon adds a dependency on a dedicated functions in d3.polygon (polygonIntersect, d3/d3-polygon#28), that doesn't yet exist, so don't expect it to land too soon (if at all).

Anyways it's already usable by copying the code, and it would be great to have tests and feedback.

Should it be explicitly undefined? Should it throw an error? Can we handle mutation during iteration (probably not)?

I am trying to make a flock simulation and using a quadtree to limit calculations per iteration.

When I create the quadtree as:
const quadtree = d3.quadtree(boids.map((b) => [b.position.x, b.position.y]));
the data is loaded correctly.

However, when I substitute it with:
const quadtree = d3.quadtree(boids).x((b) => b.position.x).y((b) => b.position.y);
the quadtree.data() = [];

Isn't this an issue with the x(), y() accessors? Or am I doing sth wrong?

Version: 5.16.0

Not exactly sure if this is a bug or if I'm doing something wrong:

const d3Quadtree = require("d3-quadtree")

const tree = d3Quadtree.quadtree().x(d => d.x).y(d => d.y);

tree.add({ x: 681, y: 86, width: 12, height: 12 })
tree.add({ x: 713, y: 52, width: 12, height: 12 })
tree.add({ x: 470, y: 103, width: 12, height: 12 })
tree.add({ x: 745, y: 188, width: 12, height: 12 })
tree.add({ x: 671, y: 144, width: 12, height: 12 })
tree.add({ x: 724, y: 128, width: 12, height: 12 })
tree.add({ x: 798, y: 179, width: 12, height: 12 })
tree.add({ x: 671, y: 200, width: 12, height: 12 })
tree.add({ x: 766, y: 221, width: 12, height: 12 })

const find = tree.find(745, 188, 12)

tree.remove(find)

tree.find(745, 188, 12)

Running the above code snippet in https://npm.runkit.com/d3-quadtree causes tree.remove(find) to not properly remove the found data point.

Even weirder: commenting out any one of the 3 lines above the add for coord 745,188 causes the remove to function correctly. (i.e. commenting out tree.add({ x: 681, y: 86, width: 12, height: 12 }))

The only thing that I could determine was different between commenting out one of the top 3 add lines versus not was that the quadtree y0 point was negative, but this is maybe a red herring.

Just reading through cover.js
Surely

    var z = x1 - x0 || 1

    while (x0 > x || x >= x1 || y0 > y || y >= y1) {
      i = (y < y0) << 1 | (x < x0);
      parent = new Array(4), parent[i] = node, node = parent, z *= 2;
      switch (i) {
        case 0: x1 = x0 + z, y1 = y0 + z; break;
        case 1: x0 = x1 - z, y1 = y0 + z; break;
        case 2: x1 = x0 + z, y0 = y1 - z; break;
        case 3: x0 = x1 - z, y0 = y1 - z; break;
      }
    }

should be

    var zx = x1 - x0 || 1, zy = y1 - y0 || 1

    while (x0 > x || x >= x1 || y0 > y || y >= y1) {
      i = (y < y0) << 1 | (x < x0);
      parent = new Array(4), parent[i] = node, node = parent, zx *= 2, zy *= 2;
      switch (i) {
        case 0: x1 = x0 + zx, y1 = y0 + zy; break;
        case 1: x0 = x1 - zx, y1 = y0 + zy; break;
        case 2: x1 = x0 + zx, y0 = y1 - zy; break;
        case 3: x0 = x1 - zx, y0 = y1 - zy; break;
      }
    }

d3.quadtree().add([1, 2]).find(1, 2, 0) returns undefined, while I'd expect it to return [1, 2].

The introduction describes how coincident nodes were stored in the previous implementation; it should be updated to reflect the new one.

See https://observablehq.com/@llb4ll/k-nearest-neighbor-search-using-d3-quadtrees

It’d be nice if the quadtree didn’t use recursion. Perhaps eliminating the recursion from the coincident nodes case would be sufficient; currently you get worst-case behavior when all the nodes are initialized to the same point.

Probably better to have accessor methods for consistency with the rest of D3’s API:

• quadtree.root() returns the root node
• quadtree.extent() returns the extent [[x0, y0], [x1, y1]].

We currently remove the leaf node on remove, but often there are sibling nodes that could be collapsed after the removal. We don’t do that, but we should; removing a node should exactly undo the adding of the node.

If a tree has the extent [[1,1],[5,5]], calling tree.extent( tree.extent() ) returns a tree with the extent [[1,1], [9,9]]

CRM strictly requires ES5 modules while d3-force and d3-quadtree are known to have ES6 code. Any suggestions on using these modules with CRM?

Thanks!
Parul

I have a pretty heavy quadtree calculation that I would like to handle using workers, but I can't seem to find a good serialization/deserialization strategy for quadtrees, so that they can be sent via postMessage. Does anyone have an idea how I could do this?

Otherwise, adding a point could change the implicit extent.

I like to use an optional filter argument with the find method so that the search can return only the nearest relevant point (e.g.: the nearest red point if blue points have been temporarily hidden by a user interaction). The basic fork that works for my purposes is extremely simple; it would take slightly more work to properly handle coincident points.

Something like this is referenced in an existing pull discussion. Happy to file a pull request for just this if desired.

Can you help me understand what is happening here? Looks like this library is a dependency of d3-force. Thanks.