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 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 n-body forces, or collision detection.

Installing

If you use NPM, npm install d3-quadtree. Otherwise, download the latest release. The released bundle supports AMD, CommonJS, and vanilla environments. Create a custom build using Rollup or your preferred bundler. You can also load directly from d3js.org:

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

In a vanilla environment, a d3_quadtree global is exported. Try d3-quadtree in your browser.

API Reference

# d3_quadtree.quadtree()

Creates a new quadtree factory with the default x-accessor, y-accessor and extent. The returned factory function can be used to create any number of quadtrees from data.

# quadtree([points])

Constructs a new quadtree for the specified array of data points, returning the root node of a new quadtree. The x- and y-coordinates of each point are determined using the current x- and y-accessor functions. To build a quadtree by adding points incrementally, the specified points array can be empty or omitted and then points can be later added to the returned root node; in this case, you must explicitly specify the extent of the quadtree.

Each node in the quadtree has several properties:

• nodes - a sparse array of four child nodes: top-left, top-right, bottom-left, bottom-right.
• leaf - a boolean indicating whether this is an internal node or a leaf node.
• point - the point associated with this node, if any; may apply to either internal or leaf nodes.
• x - the x-coordinate of the associated point, if any.
• y - the y-coordinate of the associated point, if any.

The returned root node also defines add and visit methods.

# root.add(point)

Adds the specified new point to this quadtree and returns root.

# root.visit(callback)

Visits each node in this quadtree, invoking the specified callback with arguments {node, x1, y1, x2, y2} for each node, where node is the node being visited, ⟨x1, y1⟩ is the top-left corner, and ⟨x2, y2⟩ is the bottom-right corner. Returns root. Nodes are traversed in pre-order. If the callback returns true for a given node, then the children of that node are not visited; otherwise, all child nodes are visited.

Note that the coordinate system used by the quadtree is arbitrary, so a more precise definition is that x1 <= x2 and y1 <= y2. In the typical coordinate system used by SVG and Canvas, the origin ⟨0,0⟩ is in the top-left corner, and thus ⟨x1, y1⟩ is also the top-left corner of the current node.

# root.find(x, y)

Given a point ⟨x,y⟩, returns the closest point in this quadtree.

# quadtree.x([x])

If x is specified, sets the x-coordinate accessor and returns this quadtree factory. If x is not specified, returns the current x-coordinate accessor, which defaults to:

function x(d) {
  return d[0];
}

For each point added to the quadtree, either during initial construction or lazily added, the x-accessor is invoked with the arguments {d, i}, where d is the current point and i is its index in the array of all points. The x-accessor must then return a numeric value indicating the x-coordinate of the given point. The x-accessor may also be defined as a constant number rather than a function, if desired.

# quadtree.y([y])

If y is specified, sets the y-coordinate accessor and returns this quadtree factory. If y is not specified, returns the current y-coordinate accessor, which defaults to:

function y(d) {
  return d[1];
}

For each point added to the quadtree, either during initial construction or lazily added, the y-accessor is invoked with the arguments {d, i}, where d is the current point and i is its index in the array of all points. The y-accessor must then return a numeric value indicating the y-coordinate of the given point. The y-accessor may also be defined as a constant number rather than a function, if desired.

# quadtree.extent([extent])

If extent is specified, sets the current extent and returns this quadtree factory. If extent is not specified, returns the current extent, which defaults to null. When the extent is null, an extent will be computed automatically by scanning the array of input points passed to the quadtree constructor. Otherwise, the extent must be specified as a two-dimensional array [​[x0, y0], [​x1, y1]​], where x0 and y0 are the lower bounds of the extent, and x1 and y1 are the upper bounds of the extent. Setting an extent is required when constructing a quadtree lazily from an initially-empty set of nodes.

# quadtree.size([size])

An alias for quadtree.extent where the minimum x and y of the extent are ⟨0,0⟩. Given a quadtree factory q, this is equivalent to:

q.extent([[0, 0], size])

Changes from D3 3.x:

• Removed deprecated constructor.

• root.add and root.visit now return root, allowing method chaining.

• root.find now takes two arguments {x, y} rather than a point object [x, y].