CorentinTh/quadtree-js

npm install js-quadtree
# or
yarn add js-quadtree

// 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));

<script src="https://unpkg.com/js-quadtree"></script>

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));

// 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);

// 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);

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);

const myData = {
    foo: 'bar'
};

const point = new Point(50, 50, myData);

console.log(point.data.foo); // 'bar'

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);

// 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));

const points = quadtree.getAllPoints();

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
// }

quadtree.clear();