@4bitlabs/quadtree

A simple 2D quadtree (2×2 spatial division) for fast, efficient spatial queries.

Installing

$ npm install --save @4bitlabs/quadtree

$ yarn add @4bitlabs/quadtree

$ pnpm add @4bitlabs/quadtree

Documentation

Full documentation for the library can be found here

Usage

An easy way to use this within a browser is to use the built-in DOMRect class, consider:

import { quadtree, type Bounds } from '@4bitlabs/quadtree';

const rectBounds = (r: DOMRect) => [r.left, r.top, r.right, r.bottom];

const space = quadtree<DOMRect>([0, 0, 1000, 1000], rectBounds);
space.insert(new DOMRect(25, 25, 50, 50));

const matches = space.search([20, 20, 80, 80]);

Or with custom objects:

import { quadtree, type Bounds } from '@4bitlabs/quadtree';

class Shape {
  bounds(): Bounds {
    /* TODO implement return bounds */
    return [0, 0, 0, 0];
  }
}

const space = quadtree<Shape>([0, 0, 1000, 1000], Shape.prototype.bounds);
space.insert(new Shape());
const matches = space.search([20, 20, 80, 80]);

Options

quadtree() accept a third argument of options:

| option | Description | Defaults | | ------------- | :----------------------------------------------------------- | -------- | | maxDepth | The maximum depth/subdivisions that the graph will divide. | 7 | | maxChildren | The maximum number of objects in a node before it will split | 10 |

const space = quadtree<DOMRect>([0, 0, 1000, 1000], rectBounds, {
  maxDepth: 5,
  maxChildren: 50,
});

License

ISC