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.
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. 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.3.min.js"></script>
<script>
var quadtree = d3_quadtree.quadtree();
</script>
Try d3-quadtree in your browser.
API Reference
# d3.quadtree()
Creates a new quadtree generator with the default x-accessor, y-accessor and extent. The returned generator can be used to create any number of quadtree roots from data.
# quadtree(data)
Constructs a new quadtree root node for the specified array of data. The x- and y-coordinates of each data point are determined using the current x- and y-accessors; each point in the quadtree is represented as a two-element array of numbers [x, y] with the following additional properties:
data
- the datum associated with this node.index
- the index of the datum associated with this node.
# quadtree.x([x])
If x is specified, sets the x-coordinate accessor and returns this quadtree generator. 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, the x-accessor is invoked, being passed the current datum d
and index i
. The x-accessor must then return a numeric value indicating the x-coordinate of the point corresponding to the given datum. 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 generator. 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, the y-accessor is invoked, being passed the current datum d
and index i
. The y-accessor must then return a numeric value indicating the y-coordinate of the point corresponding to the given datum. 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 generator. The extent must be specified as a two-dimensional array [[x0, y0], [x1, y1]], where x0 and y0 are the inclusive lower bounds of the extent and x1 and y1 are the exclusive upper bounds, or null. If extent is not specified, returns the current extent, which defaults to null. When the extent is not null, any point outside the extent is ignored when constructing the quadtree.
# quadtree.size([size])
If size is specified, sets the current extent and returns this quadtree generator. The size must be specified as a two-element array of numbers [[x1, y1]], where x1 and y1 are the exclusive upper bounds, or null; the lower bounds of the extent are implicitly ⟨0,0⟩. If size is not specified, returns the current upper bounds of the extent, which defaults to null. When the extent is not null, any point outside the extent is ignored when constructing the quadtree.
This is a convenience method for setting the extent where the lower bounds of the extent are ⟨0,0⟩. For example, this:
quadtree.size([960, 500]);
Is equivalent to this:
quadtree.extent([[0, 0], [960, 500]]);
Quadtree Nodes
Internal nodes of the quadtree are represented as sparse four-element arrays in left-to-right, top-to-bottom order:
0
- the top-left quadrant1
- the top-right quadrant2
- the bottom-left quadrant3
- the bottom-right quadrant
Leaf nodes of the quadtree are represent as objects with the following property:
point
- a two-element array of numbers [x, y]
If there are multiple coincident points in the quadtree, then point.next forms a linked list of coincident points.
# root.add(point)
Adds the specified new point to this quadtree and returns root. The point must be represented as a two-element array of numbers [x, y].
# root.find(x, y)
Given a point ⟨x,y⟩, returns the closest point in this quadtree.
# root.eachBefore(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. (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. If the callback returns true for a given node, then the children of that node are not visited; otherwise, all child nodes are visited.
# root.eachAfter(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. (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.