v1.0.0

• First stable release.

Changes since D3 3.x

The d3.geom.quadtree method has been replaced by d3.quadtree. 4.0 removes the concept of quadtree “generators” (configurable functions that build a quadtree from an array of data); there are now just quadtrees, which you can create via d3.quadtree and add data to via quadtree.add and quadtree.addAll. This code in 3.x:

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

Can be rewritten in 4.0 as:

var quadtree = d3.quadtree()
    .extent([[0, 0], [width, height]])
    .addAll(data);

The new quadtree implementation is vastly improved! It is no longer recursive, avoiding stack overflows when there are large numbers of coincident points. The internal storage is now more efficient, and the implementation is also faster; constructing a quadtree of 1M normally-distributed points takes about one second in 4.0, as compared to three seconds in 3.x.

The change in internal node structure affects quadtree.visit: use node.length to distinguish leaf nodes from internal nodes. For example, to iterate over all data in a quadtree:

quadtree.visit(function(node) {
  if (!node.length) {
    do {
      console.log(node.data);
    } while (node = node.next)
  }
});

There’s a new quadtree.visitAfter method for visiting nodes in post-order traversal. This feature is used in d3-force to implement the Barnes–Hut approximation.

You can now remove data from a quadtree using quadtree.remove and quadtree.removeAll. When adding data to a quadtree, the quadtree will now expand its extent by repeated doubling if the new point is outside the existing extent of the quadtree. There are also quadtree.extent and quadtree.cover methods for explicitly expanding the extent of the quadtree after creation.

Quadtrees support several new utility methods: quadtree.copy returns a copy of the quadtree sharing the same data; quadtree.data generates an array of all data in the quadtree; quadtree.size returns the number of data points in the quadtree; and quadtree.root returns the root node, which is useful for manual traversal of the quadtree. The quadtree.find method now takes an optional search radius, which is useful for pointer-based selection in force-directed graphs.

See CHANGES for all D3 changes since 3.x.

v0.8.0

• Export to the global d3 in vanilla environments (d3/d3#2840).

v0.7.3

• Allow an optional search radius with quadtree.find.

v0.7.2

• Minor optimization.

v0.7.1

• Enforce integer extent to avoid floating point error on subsequent doubling.

v0.7.0

• Restore quadtree.x.
• Restore quadtree.y.
• Change quadtree.add to take a datum and return the quadtree.
• Change quadtree.remove to take a datum and return the quadtree.
• Changed the leaf node data structure to store leaf.data instead of leaf.x and leaf.y.
• Add quadtree.addAll.
• Add quadtree.removeAll.
• Add optional arguments nodes, x and y to the d3.quadtree constructor.

v0.6.0

• Changed quadtree.add to create and return the new point.
• Leaf nodes are now points directly, rather than objects with a point property.
• Points are once again represented as {x: x, y: y} instead of [x, y].
• The constructor no longer takes an optional extent; use quadtree.extent or quadtree.cover.

v0.5.0

• Points are now represented as [x, y] rather than {x: x, y: y}.
• d3.quadtree now takes an optional extent [[x0, y0], [x1, y1]].
• Replaced public fields quadtree.{x0,y0,x1,y1} with quadtree.extent.
• Changed quadtree.root to a method.
• Added quadtree.cover.
• Added quadtree.size.
• Added quadtree.points.
• Added quadtree.copy.

v0.4.0

• Eliminate quadtree “generators”; instead, just create a quadtree and add points.
• Add quadtree.remove.
• Automatically expand the quadtree if an added point is outside the current bounds.

v0.3.0

• A complete rewrite to eliminate recursion.
• A lot of other changes; see the 0.4 for more.