d3-quadtree

A quadtree recursively partitions two-dimensional space into squares, dividing each square into four equally-sized squares. Each distinct point exists in a unique leaf node; coincident points are represented by a linked list. Quadtrees can accelerate various spatial operations, such as the Barnes–Hut approximation for computing many-body forces, collision detection, and searching for nearby points.

Installing

If you use NPM, npm install d3-quadtree. Otherwise, download the latest release. You can also load directly from d3js.org, either as a standalone library or as part of D3 4.0 alpha. AMD, CommonJS, and vanilla environments are supported. In vanilla, a d3_quadtree global is exported:

<script src="https://d3js.org/d3-quadtree.v0.5.min.js"></script>
<script>

var quadtree = d3_quadtree.quadtree();

</script>

Try d3-quadtree in your browser.

API Reference

# d3.quadtree([extent])

Creates a new, empty quadtree. If an extent [[x0, y0], [x1, y1]] is specified, the extent is initialized according to the given values; otherwise, the extent is initially undefined. For example, to initialize a quadtree covering from ⟨0, 0⟩ to ⟨960, 960⟩:

var q = d3.quadtree([[0, 0], [960, 960]]);

Or, to add a few points using method chaining:

var q = d3.quadtree([[0, 0], [960, 500]])
    .add([  0,   0])
    .add([100,   0])
    .add([  0, 100])
    .add([100, 100]);

# quadtree.extent()

Returns the current extent [[x0, y0], [x1, y1]] of this quadtree, where x0 and y0 are the inclusive lower bounds and x1 and y1 are the inclusive upper bounds, or undefined if this quadtree has no extent. The extent may be initialized when the quadtree is created, and is expanded by calling quadtree.cover or quadtree.add.

# quadtree.root()

Returns the root node of the quadtree.

# quadtree.cover(x, y)

Expands this quadtree to enclose the specified point ⟨x,y⟩, and returns this quadtree. If this quadtree’s extent already encloses the specified point, this method does nothing. If this quadtree has a defined and non-trivial extent, the extent is repeatedly doubled to enclose the specified point, wrapping the root node as necessary; if this quadtree has trivial bounds, i.e. if the lower bound ⟨x0,y0⟩ and upper bound ⟨x1,y1⟩ are coincident, the extent is expanded to enclose the specified point exactly; otherwise, if the quadtree has no extent, the extent is initialized to the trivial extent [[x, y], [x, y]].

# quadtree.add(point)

Adds the specified new point to this quadtree and returns this quadtree. If the specified point is outside the current extent of this quadtree, this quadtree is automatically expanded to cover the new point. The point must be a two-element array of numbers [x, y] or an object with the following properties:

• 0 - the x-coordinate of the point
• 1 - the y-coordinate of the point

These properties must not change while the point is in the quadtree. To update a point’s position, first remove the point, then update its position, and then re-add it to the quadtree. Alternatively, you may discard the existing quadtree entirely and create a new one from scratch; this may be more efficient if many of the points have moved.

# quadtree.remove(point)

Removes the specified point from this quadtree, returning true if the point was removed or false if this quadtree did not contain the specified point.

# quadtree.copy()

Returns a copy of this quadtree. All nodes in the returned quadtree are identical copies of the corresponding node in this quadtree; however, the point objects are shared between the original and the copy.

# quadtree.size()

Returns the total number of points in the quadtree.

# quadtree.points()

Returns an array of all points in the quadtree.

# quadtree.find(x, y)

Given a point ⟨x,y⟩, returns the closest point in this quadtree. If this quadtree is empty, returns undefined.

# quadtree.visit(callback)

Visits each node in this quadtree in pre-order traversal, invoking the specified callback with arguments node, x0, y0, x1, y1 for each node, where node is the node being visited, ⟨x0, y0⟩ are the lower bounds of the node, and ⟨x1, y1⟩ are the upper bounds, and returns this quadtree. (Assuming that positive x is right and positive y is down, as is typically the case in Canvas and SVG, ⟨x0, y0⟩ is the top-left corner and ⟨x1, y1⟩ is the lower-right corner; however, the coordinate system is arbitrary, so more formally x0 <= x1 and y0 <= y1.)

If the callback returns true for a given node, then the children of that node are not visited; otherwise, all child nodes are visited. This can be used to quickly visit only parts of the tree, for example when using the Barnes–Hut approximation. Note, however, that child quadrants are always visited in sibling order: top-left, top-right, bottom-left, bottom-right. In cases such as search, visiting siblings in a specific order may be faster.

# root.visitAfter(callback)

Visits each node in this quadtree in post-order traversal, invoking the specified callback with arguments node, x0, y0, x1, y1 for each node, where node is the node being visited, ⟨x0, y0⟩ are the lower bounds of the node, and ⟨x1, y1⟩ are the upper bounds, and returns this quadtree. (Assuming that positive x is right and positive y is down, as is typically the case in Canvas and SVG, ⟨x0, y0⟩ is the top-left corner and ⟨x1, y1⟩ is the lower-right corner; however, the coordinate system is arbitrary, so more formally x0 <= x1 and y0 <= y1.) Returns root.

Nodes

Internal nodes of the quadtree are represented as four-element arrays in left-to-right, top-to-bottom order:

• 0 - the top-left quadrant, if any
• 1 - the top-right quadrant, if any
• 2 - the bottom-left quadrant, if any
• 3 - the bottom-right quadrant, if any

A child quadrant may be undefined if it is empty.

Leaf nodes are represented as objects with the following properties:

• point - the point, as passed to quadtree.add
• next - the next point in this leaf, if any

For example, to iterate over all points in a leaf node:

if (node.point) do console.log(node.point); while (node = node.next)