d3-quadtree

d3-quadtree provides a comprehensive implementation of a quadtree data structure that recursively partitions two-dimensional space into squares for efficient spatial operations. It offers methods for adding/removing points, spatial searches, nearest neighbor queries, and tree traversal, making it ideal for collision detection, Barnes-Hut approximation, and spatial indexing.

Package Information

• Package Name: d3-quadtree
• Package Type: npm
• Language: JavaScript/TypeScript
• Installation: npm install d3-quadtree
• License: ISC

Core Imports

// Default import (recommended)
import quadtree from "d3-quadtree";

CommonJS:

// Default require
const quadtree = require("d3-quadtree").quadtree;

UMD (browser):

<script src="https://cdn.jsdelivr.net/npm/d3-quadtree@3"></script>
<script>
const tree = d3.quadtree();
</script>

Basic Usage

import quadtree from "d3-quadtree";

// Create sample data points
const points = [
  {x: 100, y: 100},
  {x: 200, y: 200},
  {x: 300, y: 100},
  {x: 400, y: 300}
];

// Create quadtree with custom accessors
const tree = quadtree(points, d => d.x, d => d.y);

// Add individual points
tree.add({x: 150, y: 250});

// Find nearest point
const nearest = tree.find(160, 160);

// Get all data
const allData = tree.data();
console.log(`Tree contains ${tree.size()} points`);

Architecture

The quadtree consists of two main node types:

• Internal nodes: Four-element arrays representing quadrants [top-left, top-right, bottom-left, bottom-right]
• Leaf nodes: Objects containing data points with data and next properties for handling coincident points

Capabilities

Quadtree Creation

Creates a new quadtree for spatial indexing of 2D points.

function quadtree<T>(
  data?: T[],
  x?: (d: T) => number,
  y?: (d: T) => number
): Quadtree<T>;

Parameters:

• data (optional): Array of data points to add to the quadtree
• x (optional): Function to extract x-coordinate from data points (defaults to d => d[0])
• y (optional): Function to extract y-coordinate from data points (defaults to d => d[1])

Returns: A new Quadtree instance

Coordinate Accessors

X-Coordinate Accessor

Gets or sets the x-coordinate accessor function.

quadtree.x(x?: (d: T) => number): Quadtree<T> | ((d: T) => number);

Parameters:

• x (optional): Function to extract x-coordinate from data points

Returns: Current x-accessor (getter) or quadtree instance (setter)

Y-Coordinate Accessor

Gets or sets the y-coordinate accessor function.

quadtree.y(y?: (d: T) => number): Quadtree<T> | ((d: T) => number);

Parameters:

• y (optional): Function to extract y-coordinate from data points

Returns: Current y-accessor (getter) or quadtree instance (setter)

Spatial Management

Extent Management

Gets or sets the quadtree's extent (bounding box).

quadtree.extent(extent?: [[number, number], [number, number]]): Quadtree<T> | [[number, number], [number, number]] | undefined;

Parameters:

• extent (optional): Array [[x0, y0], [x1, y1]] defining bounding box

Returns: Current extent (getter) or quadtree instance (setter)

Expand Coverage

Expands the quadtree to cover the specified point.

quadtree.cover(x: number, y: number): Quadtree<T>;

Parameters:

• x: X-coordinate to cover
• y: Y-coordinate to cover

Returns: Quadtree instance

Data Manipulation

Add Single Point

Adds a single data point to the quadtree.

quadtree.add(datum: T): Quadtree<T>;

Parameters:

• datum: Data point to add

Returns: Quadtree instance

Usage Example:

const tree = quadtree();
tree.add({x: 100, y: 200, value: "point1"});

Add Multiple Points

Adds an array of data points to the quadtree efficiently.

quadtree.addAll(data: T[]): Quadtree<T>;

Parameters:

• data: Array of data points to add

Returns: Quadtree instance

Usage Example:

const points = [{x: 100, y: 100}, {x: 200, y: 200}];
tree.addAll(points);

Remove Single Point

Removes a specific data point from the quadtree.

quadtree.remove(datum: T): Quadtree<T>;

Parameters:

• datum: Data point to remove (must be the exact same object reference)

Returns: Quadtree instance

Remove Multiple Points

Removes an array of data points from the quadtree.

quadtree.removeAll(data: T[]): Quadtree<T>;

Parameters:

• data: Array of data points to remove

Returns: Quadtree instance

Data Retrieval

Get All Data

Returns all data points in the quadtree as an array.

quadtree.data(): T[];

Returns: Array of all data points

Get Size

Returns the total number of data points in the quadtree.

quadtree.size(): number;

Returns: Number (count of data points)

Tree Structure Access

Get Root Node

Returns the root node of the quadtree.

quadtree.root(): QuadNode<T> | undefined;

Returns: Root node (internal node array or leaf node object)

Copy Quadtree

Creates a deep copy of the quadtree structure.

quadtree.copy(): Quadtree<T>;

Returns: New quadtree instance (copy)

Spatial Queries

Find Nearest Point

Finds the closest data point to the specified coordinates within optional radius.

quadtree.find(x: number, y: number, radius?: number): T | undefined;

Parameters:

• x: X-coordinate to search from
• y: Y-coordinate to search from
• radius (optional): Search radius (defaults to Infinity)

Returns: Closest data point or undefined if none found

Usage Example:

// Find nearest point within unlimited radius
const nearest = tree.find(150, 150);

// Find nearest point within specific radius
const nearestInRadius = tree.find(150, 150, 50);

Tree Traversal

Pre-order Traversal

Performs pre-order traversal of quadtree nodes.

quadtree.visit(callback: (node: QuadNode<T>, x0: number, y0: number, x1: number, y1: number) => boolean | void): Quadtree<T>;

Parameters:

• callback: Function called for each node with arguments (node, x0, y0, x1, y1)

Returns: Quadtree instance

Callback Return: true to skip children, falsy to continue traversal

Usage Example:

// Find all points within a rectangular region
function search(quadtree, xmin, ymin, xmax, ymax) {
  const results = [];
  quadtree.visit((node, x1, y1, x2, y2) => {
    if (!node.length) {
      do {
        let d = node.data;
        if (d.x >= xmin && d.x < xmax && d.y >= ymin && d.y < ymax) {
          results.push(d);
        }
      } while (node = node.next);
    }
    return x1 >= xmax || y1 >= ymax || x2 < xmin || y2 < ymin;
  });
  return results;
}

Post-order Traversal

Performs post-order traversal of quadtree nodes.

quadtree.visitAfter(callback: (node: QuadNode<T>, x0: number, y0: number, x1: number, y1: number) => void): Quadtree<T>;

Parameters:

• callback: Function called for each node with arguments (node, x0, y0, x1, y1)

Returns: Quadtree instance

Types

Note: d3-quadtree is written in JavaScript and does not include TypeScript definitions. The following interfaces are provided as reference for TypeScript users and may require separate type definitions.

Quadtree Interface

interface Quadtree<T> {
  x(x?: (d: T) => number): Quadtree<T> | ((d: T) => number);
  y(y?: (d: T) => number): Quadtree<T> | ((d: T) => number);
  extent(extent?: [[number, number], [number, number]]): Quadtree<T> | [[number, number], [number, number]] | undefined;
  cover(x: number, y: number): Quadtree<T>;
  add(datum: T): Quadtree<T>;
  addAll(data: T[]): Quadtree<T>;
  remove(datum: T): Quadtree<T>;
  removeAll(data: T[]): Quadtree<T>;
  copy(): Quadtree<T>;
  root(): QuadNode<T> | undefined;
  data(): T[];
  size(): number;
  find(x: number, y: number, radius?: number): T | undefined;
  visit(callback: (node: QuadNode<T>, x0: number, y0: number, x1: number, y1: number) => boolean | void): Quadtree<T>;
  visitAfter(callback: (node: QuadNode<T>, x0: number, y0: number, x1: number, y1: number) => void): Quadtree<T>;
}

Node Types

Internal Node

type InternalNode<T> = [
  QuadNode<T> | undefined,  // top-left quadrant
  QuadNode<T> | undefined,  // top-right quadrant
  QuadNode<T> | undefined,  // bottom-left quadrant
  QuadNode<T> | undefined   // bottom-right quadrant
];

Leaf Node

interface LeafNode<T> {
  data: T;                    // the associated data point
  next?: LeafNode<T>;         // next data point for coincident points
  length: undefined;          // distinguishes from internal nodes
}

Quad Node Union

type QuadNode<T> = InternalNode<T> | LeafNode<T>;

Important Notes

• Coordinate Consistency: X and Y accessors must be consistent - they should return the same value for the same input
• Immutable Coordinates: Data point coordinates must not be modified while in the tree
• NaN Handling: NaN coordinate values are ignored during operations
• Coincident Points: Multiple points at the same location are stored as a linked list in leaf nodes
• Extent Management: Tree automatically expands to accommodate points outside current extent
• Node Identification: Use node.length to distinguish node types (undefined for leaf nodes, 4 for internal nodes)
• Memory Sharing: copy() creates new tree structure but data objects are shared by reference