Previously, we introduced the grid method, a basic form of spatial partitioning. In this article, we explore a more advanced and efficient technique: Quadtree structures.

I will cover the fundamental concepts, internal mechanisms, and structural details of Quadtrees, along with a step-by-step implementation in Processing.

1. What is a Quadtree?

A Quadtree is a tree-based structure that recursively divides a two-dimensional space into four quadrants. It is mainly used to optimize spatial queries by reducing the number of comparisons needed to find objects in a region.

The term “Quad” refers to the number four, indicating that each node can have up to four children.

1-1. Why Use a Quadtree?

When a large number of objects are scattered across a space, examining each one individually becomes inefficient. By focusing only on relevant areas, Quadtrees allow for significantly faster searches and reduced computational cost. For example, when checking for objects within a given radius on the screen, Quadtree structures greatly enhance efficiency.

1-2. How Does a Quadtree Work?

Node Composition
Each node in a Quadtree typically includes:

  • A spatial region (a rectangular boundary)
  • A list of contained objects
  • Four child nodes (NE, NW, SE, SW)
  • A maximum capacity (once exceeded, the node subdivides)

Subdivision Rules
When a node exceeds its capacity, it splits into four child nodes. The existing objects are then distributed among them. This recursive subdivision enables the space to be efficiently managed as a hierarchical tree.

Applications of Quadtrees
Quadtrees are used in various domains such as collision detection in game development, edge detection in image processing, and spatial indexing in GIS (Geographic Information Systems). They are particularly useful when dealing with large-scale spatial datasets.

2. Implementing a Quadtree in Processing

Based on the concepts outlined above, we will implement a Quadtree in Processing. This implementation can also be adapted to other platforms or languages.

For the complete sample code, please visit our Patreon:
https://patreon.com/barbe_generative_diary

2-1. Creating Necessary Classes for the Quadtree

Quadtree partitioning recursively divides space to optimize searches. The implementation requires three key classes:

  • Point Class: Represents the position of each particle.
  • Rectangle Class: Defines spatial boundaries.
  • QuadTree Class: Handles both subdivision and search.

class Point {
  float x, y;
  Point(float px, float py) {
    x = px;
    y = py;
  }
}

class Rectangle {
  float x, y, w, h;
  Rectangle(float rx, float ry, float rw, float rh) {
    this.x = rx;
    this.y = ry;
    this.w = rw;
    this.h = rh;
  }
}

class QuadTree {
  Rectangle boundary;
  int capacity;
  ArrayListpoints;
  boolean divided;

  QuadTree(Rectangle b, int cap) {
    boundary = b;
    capacity = cap;
    points = new ArrayList();
    divided = false;
  }
}
  • The Point class holds x and y coordinates.
  • The Rectangle class defines an area using its center position (x, y) and size (w, h).
  • The QuadTree class manages object storage and recursively subdivides the space once a node reaches its capacity. and the divided is set to false.

2-2. Enhancing the Rectangle Class

The Rectangle class requires two additional functions for the Quadtree operations:​

  • contains( ): Checks if a given point lies within the rectangle.
  • intersects( ): Determines whether two rectangles overlap.

These methods will be used in conjunction with the QuadTree implementation in the next section.

2-3. Developing the QuadTree Class

The QuadTree class includes three core functions:

  • insert( ): Adds a point to the quad tree, subdividing if necessary.
  • subdivide( ): Splits a node(space) into four children.
  • query( ): Searches for points within a specified range.

The insert( ) function determines the appropriate quadrant for each point(Northwest, Northeast, Southwest, Southeast).


QuadTree northeast, northwest, southeast, southwest;
boolean insert(Point pt){
   if(!boundary.contains(pt)){
     return false;
   }
  return false;
}

It begins by verifying whether the point lies within the current region using if (!boundary.contains(pt)). If the point is outside the bounds, it returns false.


boolean contains(Point pt){
  if(pt.x >= x - w &&
     pt.x < x + w &&
     pt.y >= y - h &&
     pt.y < y + h ){
     return true;
  }else{
     return false;
  }
}

The contains( ) function, defined in the Rectangle class, checks if a point is within a rectangle centered at (x, y) with width w*2 and height h*2.

If the point lies within the region and the current number of points is below the capacity, it is added directly. Otherwise, the area is subdivided, and the insertion process continues recursively.


QuadTree northeast, northwest, southeast, southwest;
boolean insert(Point pt){
   if(!boundary.contains(pt)){
     return false;
   }
   if(this.points.size() < this.capacity){
     points.add(pt);
   }else{
    if(!this.divided){
       this.subdivide();
      }
    if(this.northwest.insert(pt)){
      return true;
    }else if(this.northeast.insert(pt)){
      return true;
    }else if(this.southwest.insert(pt)){
      return true;
    }else if(this.southeast.insert(pt)){
      return true;
    }
  }
  return false;
}

If the node(space) exceeds capacity, the subdivide( ) function is triggered.


void subdivide(){
  float tx = boundary.x;
  float ty = boundary.y;
  float tw = boundary.w;
  float th = boundary.h;
  Rectangle northwestbd = new Rectangle(tx - tw/2, ty - th/2 , tw/2, th/2);
  northwest = new QuadTree(northwestbd, capacity);
  Rectangle northeastbd = new Rectangle(tx + tw/2, ty - th/2 , tw/2, th/2);
  northeast = new QuadTree(northeastbd, capacity);
  Rectangle southwestbd = new Rectangle(tx - tw/2, ty + th/2 , tw/2, th/2);
  southwest = new QuadTree(southwestbd, capacity);
  Rectangle southeastbd = new Rectangle(tx + tw/2, ty + th/2 , tw/2, th/2);
  southeast = new QuadTree(southeastbd, capacity);
  divided = true;
}

In this function, the center coordinates and dimensions of the region to be subdivided are explicitly defined as tx, ty, tw, and th. New Rectangle objects are then created for each of the four child regions using these values. and, the divided flag is set to true to indicate that the node has been subdivided.

2-4. Checking QuadTree Subdivision

To visually confirm that the QuadTree is subdividing properly, a display( ) function is added inside the QuadTree class.


void display(){
  for(int i=0; i < points.size(); i++){
    strokeWeight(10);
    stroke(255);
    point(points.get(i).x, points.get(i).y);
  }

  rectMode(CENTER);
  noFill();
  stroke(255);
  strokeWeight(1);
  rect(boundary.x, boundary.y, boundary.w*2, boundary.h*2);
  if(this.divided){
    northwest.display();
    northeast.display();
    southwest.display();
    southeast.display();
  }
}

Inside the display( ) function, all points in the point list are drawn, and each subdivided region is outlined using rectangles. By setting rectMode(CENTER), each rectangle is drawn centered on its coordinates.

The subdivision behavior of the QuadTree is then visualized in the setup( ) and draw( ) functions.


QuadTree qt;
Rectangle bd;
Point p;
int ptnum = 100;
int qtCap = 2;

void setup() {
  size(900, 900);
  bd = new Rectangle(width/2, height/2, width/2, height/2);
  qt = new QuadTree(bd, qtCap);

  for (int i=0; i < ptnum; i++) {
    Point p = new Point(random(width), random(height));
    qt.insert(p);
  }
}

void draw() {
  background(0);
  qt.display();
}

In setup( ), a rectangular area is created and passed as an argument to the QuadTree. Then, random points are generated and inserted into the QuadTree using the insert( ) function.

In draw( ), the display( ) function is called to visually confirm whether subdivision has occurred correctly. (In the example code, subdivision occurs when there are more than 2 points in a given area, with 100 points generated.)

2-5. Creating query() to Search Points

After confirming the QuadTree structure, a query( ) function is created to perform searches. The following example searches within a rectangular region.


void query(Rectangle range, ArrayList found){
  if(!range.intersects(boundary)){
    return;
  }
}

An intersects( ) function is added to the Rectangle class, similar to the previously created contains() function used to check if a point exists within a given range.


boolean intersects(Rectangle boundary){
  float boundaryR = boundary.x + boundary.w;
  float boundaryL = boundary.x - boundary.w;
  float boundaryT = boundary.y - boundary.h;
  float boundaryB = boundary.y + boundary.h;

  float rangeR = x + w;
  float rangeL = x - w;
  float rangeT = y - h;
  float rangeB = y + h;

  if (boundaryR > rangeL &&
    boundaryL < rangeR &&
    boundaryT < rangeB &&
    boundaryB > rangeT) {
    return true;
  } else {
    return false;
  }
}

The intersects() function determines whether a given search area overlaps with a QuadTree boundary. It returns true if they intersect, and false otherwise.

Next, conditions are added to query( ) to collect a list of points found within the search area.


void query(Rectangle range, ArrayList found){
  if(!range.intersects(boundary)){
    return;
  } else {
    for(int i=0; i < points.size(); i++){
      if(range.contains(points.get(i))){
        found.add(this.points.get(i));
      }
    }
    if (divided) {
      if (range.intersects(northeast.boundary)) {
          northeast.query(range, found);
      }
      if (range.intersects(northwest.boundary)) {
          northwest.query(range, found);
      }
      if (range.intersects(southeast.boundary)) {
          southeast.query(range, found);
      }
      if (range.intersects(southwest.boundary)) {
          southwest.query(range, found);
      }
    }
  }
}

The contains( ) function is used to determine whether a point lies within the search range. If it does, the point is added to a list named found. This process is performed recursively within the QuadTree structure. When a node is divided (divided == true), child regions are checked, and any matching points are added to the found list.

2-6. Verifying Search with query()

To confirm that the search is functioning correctly within a specific area, a movable search range is implemented using mouseX and mouseY. A rectangle is created as the search area and drawn with rect( ).


void draw() {
  background(0);

  Rectangle range = new Rectangle(mouseX, mouseY, 100, 100);
  noFill();
  stroke(0, 255, 0);
  strokeWeight(1);
  rectMode(CENTER);
  rect(range.x, range.y, range.w * 2, range.h *2);

  ArrayList foundPoints = new ArrayList();
  qt.query(range, foundPoints);

  qt.display();
  for (int i=0; i < foundPoints.size(); i++) {
    stroke(255, 255, 0);
    strokeWeight(15);
    point(foundPoints.get(i).x, foundPoints.get(i).y);
  }
}

A list is prepared to store points found within the range. An empty list is passed to query( ), and any found points are added to it. To verify visually, the color of the points found within the range is changed and drawn using a for loop.

2-7. Searching with a Circle

To perform searches using a circle, a new Circle class is created. This class works similarly to Rectangle, but represents the area with a circle. The query( ) function of the QuadTree is then modified to accept a Circle as the search range.


class Circle{
  float x, y, radius;
  Circle(float theX, float theY, float theR) {
    x = theX;
    y = theY;
    radius = theR;
  }

  boolean contains(Point point) {
    float distX = x - point.x;
    float distY = y - point.y;
    float distance = sqrt(pow(distX, 2) + pow(distY, 2));

    if (distance <= radius) {
      return true;
    } else {
      return false;
    }
  }

  boolean intersects(Rectangle boundary) {
    float closeX = x;
    float closeY = y;
    if (x < boundary.x - boundary.w) {
      closeX = boundary.x - boundary.w;
    } else if (closeX > boundary.x + boundary.w) {
      closeX = boundary.x + boundary.w;
    }

    if (y < boundary.y - boundary.h) {
      closeY = boundary.y - boundary.h;
    } else if (y > boundary.y + boundary.h) {
      closeY = boundary.y + boundary.h;
    }

    float distX = abs(x - closeX);
    float distY = abs(y - closeY);
    float distance = sqrt(pow(distX, 2) + pow(distY, 2));

    if (distance <= radius) {
      return true;
    } else {
      return false;
    }
  }
}

The constructor of Circle takes the center coordinates (x, y) and a radius.

In contains( ), the Euclidean distance between a point and the center is calculated. If the point is within the radius, the function returns true.

In intersects(), the distance from the center of the circle to the rectangle is calculated. If this distance is less than or equal to the radius, the function determines that the circle and rectangle intersect.


//void query(Rectangle range, ArrayList found){
void query(Circle range, ArrayList found){

The query() function of the QuadTree is modified to accept Circle as an argument.

2-8. Verifying Search with a Circle

To confirm the implementation, the search range inside draw( ) is replaced with a Circle instance.


void draw() {
  background(0);

  //Rectangle range = new Rectangle(mouseX, mouseY, 100, 100);
  float radius = 100;
  Circle range = new Circle(mouseX, mouseY, radius);
  noFill();
  stroke(0, 255, 0);
  strokeWeight(1);
  //rectMode(CENTER);
  //rect(range.x, range.y, range.w * 2, range.h *2);
  circle(range.x, range.y, radius*2);

  ArrayList foundPoints = new ArrayList();
  qt.query(range, foundPoints);

  qt.display();
  for (int i=0; i < foundPoints.size(); i++) {
    stroke(255, 255, 0);
    strokeWeight(15);
    point(foundPoints.get(i).x, foundPoints.get(i).y);
  }
}

2-9. Searching Moving Points in draw()

Finally, the method for using a QuadTree to search moving particles is summarized. When particles move inside draw(), the QuadTree structure must be updated each frame.

A function called clearQuadTree( ) is created to reset the QuadTree. The point list is reconstructed, and the divided flag is reset to false.


void clearQuadTree() {
  points = new ArrayList();
  divided = false;
}

As a sample for this section, I create a set of moving particles. The Particle class used here simply makes the particles bounce off the edges of the screen.


class Particle {
  float x, y, vx, vy;
  Particle(float theX, float theY) {
    x = theX;
    y = theY;
    vx = random(-3, 3);
    vy = random(-3, 3);
  }

  void update() {
    bounce();
    x += vx;
    y += vy;
  }

  void bounce() {
    if (x > width || x < 0) {
      vx *= -1;
    }
    if (y > height || y < 0) {
      vy *= -1;
    }
  }
}

Next, the Point class is modified as shown below so that it can be used by the Particle class


class Point{
  float x,y;
  Particle userData;
  Point(float px, float py){
    x = px;
    y = py;
  }
}

The setup( ) and draw( ) functions are rewritten as follows.


QuadTree qt;
Rectangle bd;
ArrayList particles;
int particleNum = 100;
int qtCap = 2;
float radius = 100;

void setup() {
  size(900, 900);
  bd = new Rectangle(width/2, height/2, width/2, height/2);
  qt = new QuadTree(bd, qtCap);

  particles = new ArrayList();
  for (int i=0; i < particleNum; i++) {
    particles.add(new Particle(random(width), random(height)));
  }
}

void draw() {
  background(0);

  qt.clearQuadTree();

  for (Particle pa : particles) {
    pa.update();
    qt.insert(new Point(pa.x, pa.y));
  }

  Circle range = new Circle(mouseX, mouseY, radius);
  noFill();
  stroke(0, 255, 0);
  strokeWeight(1);
  circle(range.x, range.y, radius*2);

  ArrayList foundPoints = new ArrayList();
  qt.query(range, foundPoints);

  qt.display();
  for (int i=0; i < foundPoints.size(); i++) {
    stroke(255, 255, 0);
    strokeWeight(15);
    point(foundPoints.get(i).x, foundPoints.get(i).y);
  }
}

In this code, multiple particles are created in setup( ). In draw( ), the QuadTree is updated each frame. Points within a circular range are searched using the QuadTree, and particles found within the radius are highlighted with a different color.

Recommended Book

"Grid Systems in Graphic Design" by Josef Müller-Brockmann"

This book discusses grid systems, a layout method that enhances design coherence and readability by arranging text and images based on continuous rows and columns. Originally conceived for print layouts, grid systems are now utilized in all design fields, including web design. Even when creating 2D graphics with tools like Processing or P5.js, there is much to learn from this system. First published in 1981.

Grid-Systems-Raster-Systeme

DISCLAIMER: This page contains affiliate links. If you purchase through these links, I may receive a small commission. This helps support my content and allows me to keep creating valuable articles. Thank you for your support! barbe_generative_diary peco:)

BGD_SOUNDS (barbe_generative_diary SOUNDS)

barbe_generative_diary SOUNDS will start sharing and selling a variety of field recordings collected for use in my artwork “Sound Visualization” experiments. All sounds are royalty-free.

Link / BGD_SOUNDS on bandcamp