math/SpacialRectIndex.js

import RBush from 'rbush';
import knn from 'rbush-knn';

import SpacialIndex from './SpacialIndex.js';

/**
 * 2D spatial indexing for rectangles
 * @see https://www.npmjs.com/package/rbush
 * @see https://www.npmjs.com/package/rbush-knn
 */
class SpacialRectIndex extends SpacialIndex {
    constructor(getBBox) {
        super(null, null);

        this.items = [];

        this.getBBox = getBBox;

        this.dirty = true;
    }

    _update() {
        let rects = this.items.map((r, i) => {
            return {
                ...this.getBBox(r),
                index: i
            };
        });

        this.tree = new RBush();
        this.tree.load(rects);

        this.dirty = false;
    }

    /**
     * Get all rects that intersect the given rectangle
     * @param {Number} minX 
     * @param {Number} minY 
     * @param {Number} maxX 
     * @param {Number} maxY 
     * @returns {Array} array of items in the rectangle
     */
    getInRect(minX, minY, maxX, maxY) {
        if (this.dirty) this._update();
        return this.tree.search({ minX, minY, maxX, maxY }).map(i => this.items[i.index]);
    }

    /**
     * Get all rects that intersect the circle around x|y
     * @param {Number} x coordinate
     * @param {Number} y coordinate
     * @param {Number} radius radius
     * @returns {Array} array of items in the radius
     */
    getInRadius(x, y, radius) {
        return this.getInRect(x - radius, y - radius, x + radius, y + radius).filter(i => {
            let dx = Math.abs(x - i.x1);
            let dy = Math.abs(x - i.x1);

            if (dx > i.w * 0.5 + radius || dy > i.h * 0.5 + radius) return false;
            if (dx <= i.w * 0.5 || dy <= i.h * 0.5) return true;

            let corner_sq = Math.pow(dx - i.w * 0.5, 2) + Math.pow(dy - i.h * 0.5, 2);

            return corner_sq <= radius * radius;
        });
    }

    /**
     * Get the nearest rectangle(s) (k-nearest-neighbour)
     * @param {Number} x coordinate
     * @param {Number} y coordinate
     * @param {Number} n amount of items to return
     * @returns {*|Array} an item if n = 1, otherwise an array
     */
    getNearest(x, y, n = 1, filter) {
        if (this.dirty) this._update();
        let result = knn(this.tree, x, y, n, filter);

        if (n === 1) return result.length ? this.items[result[0].index] : null
        return result.map(i => this.items[i.index]);
    }
}

export default SpacialRectIndex