d3-quadtree

What is d3-quadtree?

The d3-quadtree package is a part of the D3.js library and provides a data structure known as a quadtree. A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions. This package is particularly useful for spatial indexing, collision detection, and efficient neighbor searching.

What are d3-quadtree's main functionalities?

Creating a Quadtree

This feature allows you to create a quadtree from a set of points. The quadtree can then be used for efficient spatial queries.

const d3 = require('d3-quadtree');
const points = [[0, 0], [1, 1], [2, 2], [3, 3]];
const quadtree = d3.quadtree().addAll(points);

Adding Points

This feature allows you to add individual points to an existing quadtree. This is useful for dynamically updating the quadtree as new data points are introduced.

const d3 = require('d3-quadtree');
const quadtree = d3.quadtree();
quadtree.add([0, 0]);
quadtree.add([1, 1]);

Finding Nearest Neighbor

This feature allows you to find the nearest neighbor to a given point. This is useful for applications like collision detection or finding the closest data point.

const d3 = require('d3-quadtree');
const points = [[0, 0], [1, 1], [2, 2], [3, 3]];
const quadtree = d3.quadtree().addAll(points);
const nearest = quadtree.find(1.5, 1.5);

Bounding Box Search

This feature allows you to search for points within a specific bounding box. This is useful for spatial queries where you need to find all points within a certain area.

const d3 = require('d3-quadtree');
const points = [[0, 0], [1, 1], [2, 2], [3, 3]];
const quadtree = d3.quadtree().addAll(points);
const found = [];
quadtree.visit((node, x0, y0, x1, y1) => {
  if (!node.length) {
    do {
      const d = node.data;
      if (d[0] >= 1 && d[0] <= 2 && d[1] >= 1 && d[1] <= 2) {
        found.push(d);
      }
    } while (node = node.next);
  }
  return x0 >= 2 || y0 >= 2 || x1 < 1 || y1 < 1;
});

Other packages similar to d3-quadtree

rbush

rbush is a high-performance JavaScript library for 2D spatial indexing of points and rectangles. It is similar to d3-quadtree in that it provides efficient spatial queries, but it uses an R-tree data structure instead of a quadtree. R-trees are generally better for dynamic datasets where insertions and deletions are frequent.

kdbush

kdbush is a very fast static spatial index for 2D points based on a flat KD-tree. It is similar to d3-quadtree in that it provides efficient nearest neighbor searches, but it is optimized for static datasets where the points do not change after the initial build.

geokdbush

geokdbush is a geospatial extension of kdbush, providing fast nearest neighbor searches for geographic coordinates. It is similar to d3-quadtree in that it provides efficient spatial queries, but it is specifically optimized for geographic data and uses a flat KD-tree structure.

README

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

var quadtree = d3_quadtree.quadtree();

</script>

Try d3-quadtree in your browser.

API Reference

# d3.quadtree()

Creates a new, empty quadtree with an empty extent.

# quadtree.extent([extent])

If extent is specified, expands the quadtree to cover the specified points [[x0, y0], [x1, y1]] and returns the quadtree. If extent is not specified, returns the quadtree’s current extent [[x0, y0], [x1, y1]], where x0 and y0 are the inclusive lower bounds and x1 and y1 are the inclusive upper bounds, or undefined if the quadtree has no extent. The extent may be expanded automatically by calling quadtree.cover or quadtree.add.

# quadtree.root()

Returns the root node of the quadtree.

# quadtree.cover(x, y)

Expands the quadtree to cover the specified point ⟨x,y⟩, and returns the quadtree. If the quadtree’s extent already covers the specified point, this method does nothing. If the quadtree has a defined and non-trivial extent, the extent is repeatedly doubled to cover the specified point, wrapping the root node as necessary; if the quadtree has trivial bounds, i.e. if the lower bound ⟨x0,y0⟩ and upper bound ⟨x1,y1⟩ are coincident, the extent is expanded to cover 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(x, y)

Creates a new point ⟨x,y⟩ (a leaf node), adds it to the quadtree, and returns it. If the new point is outside the current extent of the quadtree, the quadtree is automatically expanded to cover the new point.

# quadtree.remove(point)

Removes the specified point (a leaf node) from the quadtree, returning true if the point was removed or false if the quadtree did not contain the specified point.

# quadtree.copy()

Returns a copy of the quadtree. All nodes in the returned quadtree are identical copies of the corresponding node in the quadtree.

# quadtree.size()

Returns the total number of points (leaf nodes) in the quadtree.

# quadtree.points()

Returns an array of all points (leaf nodes) in the quadtree.

# quadtree.find(x, y)

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

# quadtree.visit(callback)

Visits each node in the 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 the 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 the 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 the 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:

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

The length property may be used to distinguish leaf nodes from internal nodes: it is undefined for leaf nodes, and 4 for internal nodes. For example, to iterate over all points in a leaf node:

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

The point’s x- and y-coordinates must not be modified while the point is in the quadtree. To update a point’s position, remove the point and then re-add it to the quadtree at the new position. 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.