Quadtree

Overview

A blazing fast, space-efficient quadtree written in TypeScript. No dependencies, works on both Node and the browser.

Motivation

I needed an extremely fast and space-efficient 2D collision system for my tooltip positioning system.

┌──────────────┬─────────────┬──────────────┐
│ │ │ C │
│ │ │ │
│ tooltip a │ tooltip b ├──────────────┤
│ │ │ │
│ │ │ D │
│ │ │ │
└──────────────┴─────────────┴──────────────┘ ┌────────┐
│ │
┌──────────────────────────────────────────┐ │ │
│ run of text │ │ │
└──────────────────────────────────────────┘ │tooltip │
│ h │
│ │
┌───────┬───────┬────────────────┬ ─ ─ ─ ─ ┐ │ │
│ │ │ Tooltip g │ │ │
│Tooltip│Tooltip│ │ (verify │ └────────┘
│ e │ f ├────────────────┘ tooltip
│ │ │ │position │
│ │ │ before
└───────┴───────┘ │ placing │
└ ─ ─ ─ ─ ┘

To place multiple tooltips so that they do not overlap, we need

• a data structure that allows expressing objcts in 2D space
• an algorithm that is capable of finding potential object collisions in a 2D search space efficiently and quickly.
• (not part of this package) a way to 'best guess' a tooltip position and resolve conflicts and correctly place a tooltip

In normal UX, when a tooltip is triggered, the tooltip needs to be dynamically positioned near instantly, so finding a valid position for a tooltip needs to be fast.

What makes it tricky?

• Multiple tooltips on the page, in arbitrary places

Tooltips can show up in arbitrary places on a webpage, with arbitrary dimensions and contents. I needed a flexible system for placing, moving, comparing, traversing, and removing 2D objects.

• 4K resolutions imply a 4K * 4K search space, as we need pixel-level positioning granularity. With a naive implementation, the space complexity is usually exponential i.e. O(n^2). Without proper architecture, the memory requirements become too large.

Being able to place tooltips in an {x,y} Cartesian coordinate system, and quickly detect collisions for incoming and existing tooltips allows for performantly displaying multiple tooltips on a page.

Other considerations

Other alternative considered was spatial hashing which is a popular game development solution which builds a 2D hash map.

Prior Art

Implementation borrowed from quadtree-lib which I've updated and started to further customize.

Usage

Import

import{QuadTree}from"quadtree";

Initialize

First step is to initialize a new Quadtree object.

constquadtree=newQuadTree({width: 500,height: 500,maxElements: 5// Optional});

width and height are mandatory attributes.

maxElements (default 1) is the maximum number of elements contained in a leaf before it splits into child trees.

Adding elements

Elements must be objects, with coordinates set.

Optionally, you can pass a boolean argument which, if set to true, will remove/push the object into the quadtree each time its coordinates or dimensions are set (ex: item.x = ... or item.width = ...).

Without this flag, x / y / width / height properties shouldnotbe changed after insertion.

quadtree.push({x: 10,y: 10,width: 1,height: 2},true);

To insert an array of elements, use the pushAll method which is faster than inserting each element with push.

quadtree.pushAll([{x: 1,y: 1,width: 5,height: 5},{x: 2,y: 2,width: 10,heigh: 10}// ... //]);

Removing elements

Removes an item by reference.

quadtree.remove(item);

Clearing the tree

Removes the tree contents and restores it to pristine state.

quatree.clear();

Filtering the tree

Filters the quadtree and returns a clone containing only the elements determined by a predicate function.

constfiltered=quadtree.filter(element=>element.x>50);

Opposite: quadtree.reject

Retrieve colliding elements

Gets every element that collides with the parameter 2d object.

constcolliding=quadtree.colliding({x: 10,y: 10,width: 5,//Optionalheight: 5//Optional});

The default collision function is a basic bounding box algorithm. You can change it by providing a function as a second argument.

constcolliding=quadtree.colliding({x: 10,y: 10},(element1,element2)=>{return;// Place collision algorithm here //});

Perform an action on colliding elements

Performs an action on every element that collides with the parameter 2d object.

onCollision({x: 10,y: 20},item=>{});

Retrieve by properties

Gets every element that match the parameter properties.

quadtree.push({x: 0,y: 0,foo: "bar"});constmatch=quadtree.where({foo: "bar"});

Retrieve by predicate

Gets every element that validate the given predicate.

quadtree.find(element=>element.color==='red'});

Iterate over the elements

Performs an action on each element of the Quadtree (breadth first traversal).

quadtree.each(element=>console.log(element.color));