Story

Quadtrees

by: Damien Raymond

In this article, I discuss approaches to implement collision detection and indexes for spatial queries using a simple example to illustrate.

Within Flutter, most systems are streaming applications. We use Backstage as a software catalogue. Backstage is great, but I find the graph showing the relation between the components not very helpful. I wanted to create a plugin that shows the message flow between applications better for streaming applications.

This plugin is a 2D tool that plots geometrical shapes on a canvas. To simplify, let us consider only points (x,y coordinates). As the mouse moves over the plan, we want to find the point the closest to the cursor and show its label. This happens in the real time so the operation must be fast. Out of curiosity, I wanted to look at approaches to implement such logic.

Options for Finding Points

One approach is to do a lineal search on the points. This iterates through the list of points to find the hovered point using Pythagoras Theorem. The major drawback is the performance: linear complexity (O(n)). For a real-time application, it’s not good enough.

Another approach is to use a HashMap with the coordinates as a key and the point as a value (e.g., Map[(Int, Int), Point]). The complexity would then be O(1) which would be ideal. A significant limitation though is that the mouse cursor needs to be at the same coordinates as the point itself. In practice, that would not work well and provide a poor user experience.

A special type of data structure exists for this problem: a quadtree. A quadtree is like a binary tree, but in two dimensions. It divides the range of data by 4 rather than 2. It is expressed as a Tree ADT where a Node contains the four quadrants that are themselves Trees; the leaf containing the data; and an empty leaf.

enum QuadtreeStructure[+T] {
  case Node(
      topLeft: QuadtreeStructure[T],
      topRight: QuadtreeStructure[T],
      bottomRight: QuadtreeStructure[T],
      bottomLeft: QuadtreeStructure[T]
  ) extends QuadtreeStructure[T]
  case Leaf(t: T) extends QuadtreeStructure[T]
  case EmptyLeaf extends QuadtreeStructure[Nothing]
}

Scala 3 tree ADT definition

Quadtree Building

Building a quadtree is analogous to building a binary tree. Adding a new element depends on the number of points in the quadrant: (1) if the quadrant is empty (empty leaf), it is replaced by a leaf containing the new element; (2) if the quadrant contains one leaf (leaf object), the leaf object gets replaced by a node object, the existing leaf gets moved to the relevant sub-quadrant, the new point is itself added to its relevant sub-quadrant; (3) if the current tree is a Node, then, the algorithm zooms in the relevant quadrant.

Now let us see how we can find a point in our tree.

Finding Points in a Quadtree

The naïve approach would be to apply a binary tree search: recursively zoom into the tree to find either the point or an empty tree. It finds a point fast (as the range get divided by four at each level) but there is no guarantee that this point is the closest to the mouse cursor.

Even if the cursor is near a point, if the square contains no point, it fails to select any point.

Fortunately, an algorithm exists for this use case: the nearest neighbour algorithm. The way this algorithm works is like Dijkstra’s algorithm (in a way). It involves traversing the tree in a Breadth-First search fashion (level by level). At each step, keeping the closest point and returning the point at the end.

The algorithm starts with the four largest squares, let us call them current squares. Collect the points for each current square (leaf trees) and find the closest point. Then, find, within the current squares, the sub-quadrants closer than the closest point. Start again till the last level of the tree is reached and return the closest point.

Click to show the steps

There is a problem with this algorithm. Given the tree structure that we use (values stored in the leaves the tree), the complexity for the worse case (when the tree forms a perfect triangle) is linear (O(n)). It is not possible to eliminate any quadrant before the last level resulting in having to scan through each point.

A minor change can drastically improve the performance. It consists of adding a “representative point” at each node of the tree. It can be any child point; it does not matter. Now, for each level of the tree, there is a best point for this level. It means that any quadrant further away from the current best point can be eliminated significantly reducing the number of nodes to explore. The complexity is now closer to O(n log n) according to the paper [1].

enum QuadtreeStructure[+T] {
  case Node(
      topLeft: QuadtreeStructure[T],
      topRight: QuadtreeStructure[T],
      bottomRight: QuadtreeStructure[T],
      bottomLeft: QuadtreeStructure[T],
      representativePoint: T // <--- here
  ) extends QuadtreeStructure[T]
  case Leaf(t: T) extends QuadtreeStructure[T]
  case EmptyLeaf extends QuadtreeStructure[Nothing]
}

Click to show the steps

Other Quadtree Applications, Optimisations and Going Further

Quadtrees have a plethora of application. Image compression: it allows to eliminate similar contiguous pixels from an image by replacing them with a single colour. Spatial indexing [8]: to improve the performance of database special queries. Hidden-surface determination [7]: used in video games to determine objects not visible to the camera (objects to not render). Collision detection: if two objects end up in the same spatial sub-quadrant, then they need to be checked for intersection [6].

With this wide field of applications and heavy usage in real time applications, many optimisations exist to suit different use cases [5]. For instance: reducing the memory footprint of the quadtree data structure using compression [4]. If the tree is sparse, it is possible to remove many empty nodes, then apply a total order on the element and store them in a sorted set. Some research paper also demonstrates implementations of the nearest neighbour algorithm in constant time [3]. It consists in representing the tree using binary numbers. Then an algorithm leveraging binary operations (shift, OR, AND, etc.) finds the neighbours.

Quadtrees were also generalised in multiple dimensions: octrees (3D) and kd-trees (in k dimensions). Kd-trees are built in a different way: alternating the dimensions for each level of the tree. Where the quadtree would split the space in 4 squares, the kd-tree would split horizontally, then vertically, then horizontally again and so on. The principle stays the same: split the space in sub-sections to divide and conquer [2].

The initial problem was to find the point the closest to the mouse cursor. The solution needed to be real-time suitable. Out of the 3 approaches that we mentioned (List, HashMap, and Quadtree), the quadtree offers the best of both worlds. Reasonable performance: the finding operation had a complexity of O(n log n) for the average case and perfect accuracy: finding the closest point is guaranteed. Both points ensure a great user experience.

References:

by: Damien Raymond
in:
tags: Flutter Global Tech
category: Story