A simple quadtree for rapidly fetching spatial data

QuadTree.js

/**
 * A simple quadtree for rapidly fetching spatial data
 * @param {number} xMin 
 * @param {number} xMax 
 * @param {number} yMin 
 * @param {number} yMax 
 */
function QuadTree(xMin, xMax, yMin, yMax) {
    // swap xMin/xMax and yMin/yMax if needed
    if (xMin > xMax) [xMin, xMax] = [xMax, xMin];
    if (yMin > yMax) [yMin, yMax] = [yMax, yMin];

    /** 
     * The root node, which contains bounds, midpoints, 
     * and placeholders for children or data 
     */
    const root = createNode(xMin, xMax, yMin, yMax);

    /**
     * Creates a node, which contains bounds and
     * either an array of children or an array 
     * of data (as a leaf node)
     * @param {number} xMin 
     * @param {number} xMax 
     * @param {number} yMin 
     * @param {number} yMax 
     */
    function createNode(xMin, xMax, yMin, yMax) {
        return { xMin, xMax, yMin, yMax, data: [], children: [] }
    }

    /**
     * Creates a child node for each quadrant
     * @param {object} node 
     */
    function createChildren({xMin, xMax, yMin, yMax}) {
        const xMid = (xMax - xMin) / 2;
        const yMid = (yMax - yMin) / 2;

        return [
            createNode(xMin, xMid, yMin, yMid), // top left
            createNode(xMid, xMax, yMin, yMid), // top right
            createNode(xMin, xMid, yMid, yMax), // bottom left
            createNode(xMid, xMax, yMid, yMax), // bottom right
        ];
    }


    /**
     * Retrieves the deepest child node containing the x/y coordinates
     * @param {number} x 
     * @param {number} y 
     */
    function getNode(root, x, y) {
        let node = root;

        if (x < node.xMin || x > node.xMax || y < node.yMin || y > node.yMax)
            return null;

        while (node.children.length) {
            for (let i = 0; i < node.children.length; i ++) {
                let child = node.children[i];
                if (x >= child.xMin && x <= child.xMax && y >= child.yMin && y <= child.yMax) {
                    node = child;
                    break;
                }
            }
        }

        return node;
    }

    /**
     * 
     * @param {number} x 
     * @param {number} y 
     * @param {any} data 
     */
    function addData(x, y, data) {
        // traverse to the leaf node containing the specified coordinates
        let node = getNode(root, x, y);
        let done = false;

        while (!done) {
            // we can add data if the current node is empty or has data at the same coordinates
            if (!node.children.length && (!node.data.length || (x === node.data[0].x && y === node.data[0].y))) {
                node.data.push({x, y, data}); // add data to the current node
                done = true;
            } else {
                // otherwise, the current node already has data and must move its data to a child
                node.children = createChildren(node);

                // find children for existing/new data (may resolve to the same child)
                const child = getNode(node, node.data[0].x, node.data[0].y);
                const newChild = getNode(node, x, y);

                // move existing data to a child node
                child.data = node.data;
                node.data = [];

                // continue drilling down as needed (eg: child === newChild)
                node = newChild;
            }
        }

        return node;
    }

    function getData(x, y) {
        return getNode(root, x, y).data;
    }

    return {
        root: root,
        addData: addData,
        getData: getData,
        getNode: getNode,
    }
}