Skip to content

Instantly share code, notes, and snippets.

@park-brian
Last active October 12, 2020 21:53
Show Gist options
  • Save park-brian/828517178a3e1c37b3cb410ee7e25115 to your computer and use it in GitHub Desktop.
Save park-brian/828517178a3e1c37b3cb410ee7e25115 to your computer and use it in GitHub Desktop.
A simple quadtree for rapidly fetching spatial data
/**
* 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,
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment