CorentinTh
A powerful quadtree implementation in javascript. It can be used for nodejs or directly in the browser.
Installation
Node JS
Quadtree-js can be installed using yarn or npm.
npm install js-quadtree
# or
yarn add js-quadtreeAnd import :
// EMAScript import
import {QuadTree, Box, Point, Circle} from 'js-quadtree';
// Or Common JS:
const {QuadTree, Box, Point, Circle} = require('js-quadtree');
const quadtree = new QuadTree(new Box(0, 0, 1000, 1000));
quadtree.insert(new Point(100, 200, {custom: 'data'}));
const results = quadtree.query(new Circle(150, 150, 100));Browser
You can use the CDN:
<script src="https://unpkg.com/js-quadtree"></script>And everything is globally accessible and prefixed with QT:
const quadtree = new QT.QuadTree(new QT.Box(0, 0, 1000, 1000));
quadtree.insert(new QT.Point(100, 200, {custom: 'data'}));
const results = quadtree.query(new QT.Circle(150, 150, 100));Usage
Creation
// Create the bounding area of the quadtree (x, y, width, height)
const boundingArea = new Box(0, 0, 1000, 1000);
// Instantiate the new quadtree
const quadtree = new QuadTree(boundingArea);You can also specify the following optional parameters:
// Create the bounding area of the quadtree (x, y, width, height)
const boundingArea = new Box(0, 0, 1000, 1000);
const config = {
capacity: 10, // Specify the maximum amount of point per node (default: 4)
removeEmptyNodes: true, // Specify if the quadtree has to remove subnodes if they are empty (default: false).
maximumDepth: 5, // Specify the maximum depth of the quadtree. -1 for no limit (default: -1).
// Specify a custom method to compare point for removal (default: (point1, point2) => point1.x === point2.x && point1.y === point2.y).
arePointsEqual: (point1, point2) => point1.data.foo === point2.data.foo
};
// An array of point to insert directly (same as quadtree.insert(points) )
const points = [new Point(10, 10), new Point(52, 64)];
const quadtree = new QuadTree(boundingArea, config, points);Insert
You can insert a Point element, an array of Point element, your own element as long as it has an x** and a **y property or an array of custom element.
const point = new Point(10, 25);
const pointArray = [
new Point(45, 22),
new Point(30, 60),
new Point(14, 12)
];
const customPoint = {
x: 94,
y: 23,
customField:{}
};
quadtree.insert(point);
quadtree.insert(pointArray);
quadtree.insert(customPoint);You can add your data in a Point element:
const myData = {
foo: 'bar'
};
const point = new Point(50, 50, myData);
console.log(point.data.foo); // 'bar'Remove
As the insert method, you can remove a Point element, an array of Point element, your own element as long as it has an x** and a **y property or an array of custom element.
By default, points having the same x** and **y values will be removed. To override this behavior, add a method under arePointsEqual in the config of the quadtree that takes two points in parameters and return a boolean if the points are equal.
Example: const quadtree = new QuadTree(boundingArea, {arePointsEqual: (point1, point2) => point1.data.foo === point2.data.foo});
const point = new Point(10, 25);
const pointArray = [
new Point(45, 22),
new Point(30, 60),
new Point(14, 12)
];
const customPoint = {
x: 94,
y: 23
};
quadtree.remove(point);
quadtree.remove(pointArray);
quadtree.remove(customPoint);Note: it doesn't have to be the same object, the test is done with the coordinates.
Query
Use the query method to get all the point within a range.
// This will return all the points in the given Box (x, y, width, height)
const points = quadtree.query(new Box(10, 10, 100, 100));// This will return all the points in the given Circle (x, y, radius)
const points = quadtree.query(new Circle(10, 10, 100));You can use a Box or a Circle as a range or even your own range element as long as it has the following methods:
- contains: return true if a point is within this range, false otherwise.
- intersects: return true if a Box intersects with this range, false otherwise. See the Box definition for a good example.
Get all the point
If want to retrieve all the point, you can use this method:
const points = quadtree.getAllPoints();Note: you may want to store your points in a side array since, it have to look trough all the child nodes.
Get Tree
You can get the amount of points by nodes with the getTree() method.
const qt = new QuadTree(new Box(0, 0, 10, 10));
qt.insert(new Point(5, 5));
qt.insert(new Point(6, 5));
qt.insert(new Point(4, 5));
qt.insert(new Point(3, 5));
qt.insert(new Point(2, 5));
qt.insert(new Point(1, 5));
console.log(qt.getTree());
// {
// ne: 2,
// nw: {
// ne: 0,
// nw: 0,
// se: 3,
// sw: 2
// },
// se: 2,
// sw: 3
// }Clear
Use this method to clear the quadtree. It remove all the points and sub-nodes.
quadtree.clear();Contribute
Pull requests are welcome ! Feel free to contribute.
Credits
Coded with ❤️ by Corentin Thomasset.
License
This project is under the MIT license.