d3-quadtree

A quadtree is a two-dimensional recursive spatial subdivision. This implementation uses square partitions, dividing each square into four equally-sized squares. Each point exists in a unique node; if multiple points are in the same position, some points may be stored on internal nodes rather than leaf nodes. Quadtrees can be used to accelerate various spatial operations, such as the Barnes–Hut approximation for computing many-body forces, or collision detection.

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.4.min.js"></script>
<script>

var quadtree = d3_quadtree.quadtree();

</script>

Try d3-quadtree in your browser.

API Reference

# d3.quadtree([[x0, y0, ]x1, y1])

Creates a new, empty quadtree with the initial bounds x0, y0, x1, y1, where x0 and y0 are the inclusive lower bounds of the extent and x1 and y1 are the inclusive upper bounds. If the initial bounds are not specified, the bounds will be inferred as points are added to the quadtree.

If only the upper bounds x1 and y1 are specified, the lower bounds x0 and y0 are assumed to be 0. If the specified bounds are not square, the shorter side is expanded to produce square bounds while retaining the original center. Thus, the following statements are therefore equivalent:

var q = d3.quadtree(960, 500);
var q = d3.quadtree(0, 0, 960, 500);
var q = d3.quadtree(0, -230, 960, 730);

If an added point is outside the current bounds of this quadtree, this quadtree is expanded by repeatedly doubling its width and height until the new point is contained.

# quadtree.add(point)

Adds the specified new point to this quadtree and returns this quadtree. The point must have the following properties:

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

By returning this quadtree, this method allows method chaining. For example:

var q = d3.quadtree(960, 500)
    .add({x:   0, y:   0})
    .add({x: 100, y:   0})
    .add({x:   0, y: 100})
    .add({x: 100, y: 100});

# 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.)

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

Each child quadrant may be undefined if the specified quadrant 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

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.

See quadtree.visit for a description of the node data structure.