@4bitlabs/ennetree

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

Installing

$ npm install --save @4bitlabs/ennetree

$ yarn add @4bitlabs/ennetree

$ pnpm add @4bitlabs/ennetree

Documentation

Full documentation for the library can be found here

Usage

Similar to a quadtree, but instead of binary recursive subdivisions, an ennetree uses trinary (3×3) subdivisions. Depending on the use-case, this can sometimes yield more efficient spatial queries.

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

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

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

const space = ennetree<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 { ennetree, type Bounds } from '@4bitlabs/ennetree';

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

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

Options

ennetree() accept a third argument of options:

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

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

License

ISC