Quadtree

Introduction

Quadtrees are tree data structures used to represent two-dimensional spatial data. Each node in a quadtree subdivides the space it represents into four equal quadrants. This hierarchical partitioning allows for efficient operations on spatial data, such as range queries and collision detection.

Basics of Quadtrees

• Node Structure: Each node in a quadtree represents a rectangular section of space. It may contain a data point and up to four child nodes, each representing one of the four quadrants.
• Insertion: When inserting a point into a quadtree, we start at the root and traverse down the tree. At each node, we determine in which quadrant the point lies and move to the corresponding child node until we reach a suitable position for insertion.

Benefits of Using Quadtrees

• Efficiency: Quadtrees allow us to quickly ignore large portions of data by eliminating sections of space that are of no interest.
• Dynamic: They can grow or shrink as needed, allowing for efficient insertions and deletions.
• Flexibility: Quadtrees can adapt to varying densities in spatial data.

Time Complexity: Construction and Collision Detection

Quadtrees are particularly advantageous when it comes to optimizing search operations like collision detection. However, it's important to understand the time complexities associated with both constructing the quadtree and using it for search operations:

1. Building a Quadtree

The time complexity of building a quadtree largely depends on the distribution of data and the depth of the tree. In the worst case, if points are evenly distributed such that each node is subdivided until the maximum allowable depth, the time complexity becomes for points. However, in practice, most datasets won't need to subdivide every node to the maximum depth, making the average case often much better than the worst

1. Collision Detection Without Quadtrees

Using a brute-force method, checking for collisions or proximity of points would require comparisons since every point would be checked against every other point.

1. Collision Detection With Quadtrees

When utilizing quadtrees, the space is partitioned, enabling the algorithm to quickly eliminate large sections that don't need checking. For well-distributed data, a quadtree can reduce the number of checks significantly. Ideally, if each region (node) in the quadtree contains a constant number of points (let's say points), and if the depth of the quadtree is , then the complexity for searching collisions would be roughly . For a well-balanced quadtree, would be proportional to , making this far more efficient than the brute force method.

Code example of the Algorithm

class QuadTree {
  private capacity: number;

  private points: Point[] = [];
  public ne: QuadTree | null = null;
  public nw: QuadTree | null = null;
  public se: QuadTree | null = null;
  public sw: QuadTree | null = null;

  public container: Box;

  constructor(container: Box, capacity: number = 4) {
    this.capacity = capacity;
    this.container = container;
  }

  insert(point: Point): boolean {
    if (!this.container.contains(point)) {
      return false;
    }

    if (this.points.length < this.capacity) {
      this.points.push(point);
      return true;
    }

    if (!this.ne) {
      this.subdivide();
    }

    return (
      this.ne.insert(point) ||
      this.nw.insert(point) ||
      this.se.insert(point) ||
      this.sw.insert(point)
    );
  }

  private intersects(circle: Circle): boolean {
    const { x, y, w, h } = this.container;

    const dx = Math.abs(circle.x - x - w / 2);
    const dy = Math.abs(circle.y - y - h / 2);

    if (dx > w / 2 + circle.r) {
      return false;
    }

    if (dy > h / 2 + circle.r) {
      return false;
    }

    if (dx <= w / 2) {
      return true;
    }

    if (dy <= h / 2) {
      return true;
    }

    const cornerDistanceSq = (dx - w / 2) ** 2 + (dy - h / 2) ** 2;

    return cornerDistanceSq <= circle.r ** 2;
  }

  subdivide() {
    const { x, y, w, h } = this.container;

    const ne = new Box(x + w / 2, y, w / 2, h / 2);
    const nw = new Box(x, y, w / 2, h / 2);
    const se = new Box(x + w / 2, y + h / 2, w / 2, h / 2);
    const sw = new Box(x, y + h / 2, w / 2, h / 2);

    this.ne = new QuadTree(ne, this.capacity);
    this.nw = new QuadTree(nw, this.capacity);
    this.se = new QuadTree(se, this.capacity);
    this.sw = new QuadTree(sw, this.capacity);
  }

  query(circle: Circle): Point[] {
    const points: Point[] = [];

    if (!this.intersects(circle)) {
      return points;
    }

    for (const point of this.points) {
      if (circle.contains(point)) {
        points.push(point);
      }
    }

    if (!this.ne) {
      return points;
    }

    return [
      ...points,
      ...this.ne.query(circle),
      ...this.nw.query(circle),
      ...this.se.query(circle),
      ...this.sw.query(circle),
    ];
  }
}

Benchmark: Quadtree vs. Brute Force

Settings