Climbing the QuadTree

In this post we'll discuss what a Quadtree data structure is, why it is useful and how to implement and use the data structure.

What's a Quadtree?

A Quadtree is a data structure that is useful for efficiently retrieving data based on two levels of search criteria. A Quadtree can be thought of as a two-dimensional binary search. Quadtrees are good choices for designing collision detection or geolocation search algorithms.

Quadtrees store data based on two data fields. For our example, we'll assume we are storing our Quadtree based on an X and Y coordinate (another popular data type often used to construct a Quadtree are latitude and longitude pairs). Quadtrees take a bounding box as input, which specifies the boundaries that each inserted point must fit within.

The first point added to the Quadtree will contain their own child Quadtrees that occupy the NW, NE, SE and SW quadrants of the boundary. When a second point is added, we will check which child quadrant the second point falls in and then place that point within the Quadtree of that quadrant. This new point then gets its own child Quadtrees occupying the four quadrants within its containing quadrant. This process continues with each point added.

Searching a Quadtree works in a similar manner to insertion. When searching for a point or points within a containing boundary box, the first action is to look at the initial point and determine which quadrant to search. We then query the point within that quadrant and determine which subquadrant to continue our search in. This process continues until we find the desired point(s).

By using this process, each search iteration searches only one quadrant and effectively disregards the other three quadrants thereby pruning our search area by 3/4 with each iteration. This should remind you of a binary search where each search iteration eliminates half of the search area. This characteristic demonstrates the logarithmic time complexity of searching a Quadtree.


Implementation

Now that we are familiar with the data structure, let's see how to implement a Quadtree.

// Takes coordinate box and creates a new Quadtree.
// Alternately, accepts a Box instance as only argument
var Quadtree = function(minX, minY, maxX, maxY) {
  // argument shifting
  if (arguments.length === 1) {
    this.box = arguments[0];
  } else {
    this.box = new Box(minX, minY, maxX, maxY);
  }
  this.point = null;
  this.SW = null;
  this.SE = null;
  this.NW = null;
  this.NE = null;
};

Our Quadtree class takes a bounding box as it's input and sets up its four quadrants to be populated the next time a point is entered. For convenience, this Quadtree class can also take a Box object as it's input which is why the argument shifting is used.

Insert method:

// Takes x and y coordinates as input and inserts point into the Quadtree.
// Alternately, accepts a Point instance as only argument.
Quadtree.prototype.insert = function(x, y) {
  var point;

  // argument shifting
  if (arguments.length === 1) {
    point = arguments[0];
  } else {
    point = new Point(x, y);
  }
  var currentTree = this;
  if (!currentTree.point) {
    currentTree.point = point;
    return;
  }

  var quadrant = currentTree.box.findQuadrantForPoint(point);
  while (currentTree[quadrant]) {
    currentTree = currentTree[quadrant];
    quadrant = currentTree.box.findQuadrantForPoint(point);
  }

  var quadtreeBox = currentTree.box.getQuadrant(quadrant);
  currentTree[quadrant] = new Quadtree(quadtreeBox);
  currentTree[quadrant].point = point;
};

Insert takes a point as it's input and traverses the Quadtree to find the correct location for placing the point.

Retrieve method:

// Takes 4 coordinates and returns an array of all Points within that box
// Alternately accepts a Box instance as it's only argument.
Quadtree.prototype.retrieve = function(minX, minY, maxX, maxY) {
  var searchBox;

  // argument shifting
  if (arguments.length === 1) {
    searchBox = arguments[0];
  } else {
    searchBox = new Box(minX, minY, maxX, maxY);
  }

  var foundPoints = [];
  if (searchBox.contains(this.point)) {
    foundPoints.push(this.point);
  }

  if (this.NE && this.NE.box.overlaps(searchBox)) {
    foundPoints = foundPoints.concat(this.NE.retrieve(searchBox));
  }
  if (this.NW && this.NW.box.overlaps(searchBox)) {
    foundPoints = foundPoints.concat(this.NW.retrieve(searchBox));
  }
  if (this.SW && this.SW.box.overlaps(searchBox)) {
    foundPoints = foundPoints.concat(this.SW.retrieve(searchBox));
  }
  if (this.SE && this.SE.box.overlaps(searchBox)) {
    foundPoints = foundPoints.concat(this.SE.retrieve(searchBox));
  }

  return foundPoints;
};

Retrieve takes a bounding box and traverses the Quadtree to find the child Quadtrees that are contained by the bounding box. Retrieve returns all points within the bounding box.

Find nearest point method:

/**
 * Takes a Point as the target point and an optional number as the initialSearchRadius input. 
 * Returns the nearest Point to the target Point.
 * Alternately, accepts a Point as first argument and a number in the second argument as initialSearchRadius.
 */
Quadtree.prototype.findNearestPointTo = function(x, y, initialSearchRadius) {
  var target;
  if (!this.point) {
    return null;
  }

  // argument shifting
  if (typeof arguments[0] === 'number') {
    target = new Point(x, y);
  } else {
    target = arguments[0];
    initialSearchRadius = arguments[1];
  }

  var findNearestPoints = function(quadtree) {
    var initialSearchRadius = initialSearchRadius || 1;
    var searchBox = new Box(target.x - initialSearchRadius,
                            target.y - initialSearchRadius,
                            target.x + initialSearchRadius,
                            target.y + initialSearchRadius);

    var nearestPoints = quadtree.retrieve(searchBox);
    while (nearestPoints.length === 0) {
      searchBox.expand();
      nearestPoints = quadtree.retrieve(searchBox);
    }
    return nearestPoints;
  };
  var findShortestDistance = function(points) {
    var shortestDistance;
    var nearestPoint = null;
    for (var i=0; i<points.length; i++) {
      var curDistance = target.distanceTo(points[i]);
      if (shortestDistance === undefined || curDistance < shortestDistance){
        shortestDistance = curDistance;
        nearestPoint = points[i];
      }
    }
    return nearestPoint;
  };

  var points = findNearestPoints(this);
  return findShortestDistance(points);
};

This method efficiently finds the closest point to a given point.

Note that this Quadtree implementation uses Box and Point helper classes. These classes are self-explanatory and are not essential for understanding how a Quadtree functions. If you are curious in how to implement these helper classes, please check out my full source code.


Usage

Below I've provided an example for creating a Quadtree that spans a 20x20 area centered on point (0, 0). The example inserts points in the Quadtree, retrieves points within a specified search area and also finds the nearest point to a given point.

//create a QuadTree of specified dimensions
var quadtree = new Quadtree(-10, -10, 10, 10);

//insert a point into the quadtree
quadtree.insert(5, 5);
quadtree.insert(-5, -5);
quadtree.insert(2, 6);
quadtree.insert(5, 10);
quadtree.insert(-2, 1);
quadtree.insert(4, -6);

//retrieves an array containing all points within specified dimensions
quadtree.retrieve(2, 2, 8, 8)
=> [ { x: 5, y: 5 }, { x: 2, y: 6 } ]

//returns the nearest point to the point argument
quadtree.findNearestPointTo(3, 8);
=> { x: 2, y: 6 }


Summary

Quadtrees are useful data structures for efficiently retrieving information in two dimensions. The concept is easily applied to n-dimensions, which will allow you to quicly understand how n-Tree data structures are implemented and used.

For more great Javascript data structure implementations check out the dslib npm module. Also, please visit the dslib open source code to see my full implementation of the Quadtree as well as a comprehensive test suite.