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.