Quad Tree Visualization

quadtree.pde

/**
 * Quad Tree implementation and visualization in Processing. Executes
 * with Processing 1.5.1
 *
 * Adds points to a quad tree and shows visually as the quad tree
 * splits and repushes the values as new values are added.
 *
 * Restart QuadTree with new values with a key press.
 */

int w = 512;
int h = 512;
int amountToPut = 64;
color backCol = color(255, 255, 255);
color borderCol = color(10, 50, 175);
color valueCol = color(240, 10, 50);
int delayTime = 10;
int delayRestartTime = 5000;
boolean logEnabled = false;

void setup() {
  size(w*2, h);
  buffer = createGraphics(w, h, JAVA2D);
  root = new QTreeNode(0, 0, w, h);
  background(backCol);
}

PGraphics buffer;
QTreeNode root;
int currentStep = 0;

ClusterPoint[] clusters = {
  new ClusterPoint(100, 50, 400, 200),
  new ClusterPoint(300, 400, 100, 400),
  new ClusterPoint(300, 150, 400, 400),
  new ClusterPoint(150, 390, 350, 100),
};

class ClusterPoint {
  float x;
  float y;
  float diffX;
  float diffY;
  public ClusterPoint(float x, float y, float diffX, float diffY) {
    this.x = x;
    this.y = y;
    this.diffX = diffX;
    this.diffY = diffY;
  }
  
  public QTreeVal getRandomPoint() {
    float rX = -1f;
    while (rX > w || rX < 0f) {
      rX = x + random(diffX) - (diffX/2f);      
    }
    float rY = -1f;
    while (rY > h || rY < 0f) {
      rY = y + random(diffY) - (diffY/2f);
    }
    return new QTreeVal(rX, rY);
  }
}

void addToRoot() {
  ClusterPoint cp = clusters[(int) random(clusters.length)];
  root.put(cp.getRandomPoint());
}

void draw() {
  if (currentStep < amountToPut) {
    currentStep++;
    addToRoot();
  }
  stroke(borderCol);
  noFill();
  buffer.beginDraw();
  buffer.background(backCol);
  buffer.pushMatrix();
  // Tree Graph
  drawTree(buffer);
  image(buffer, width/2, 0);

  // Draw Graph
  buffer.background(backCol);
  buffer.scale(0.95, 0.95);
  buffer.translate(w*0.025, h*0.025);
  drawGraph(buffer);
  buffer.popMatrix();
  buffer.endDraw();
  image(buffer, 0, 0);
  delay(delayTime);
}

void drawTree(PGraphics buffer) {
  buffer.beginDraw();
  buffer.smooth();
  buffer.background(backCol);
  drawTreeNode(buffer, root, width/4f, 20, 1);
  buffer.endDraw();
}

void drawTreeNode(PGraphics buffer, QTreeNode node, float x, float y, int depth) {
  float a = 255-((depth-1)*40);
  if (a < 1f) a = 1f;
  float r = 20 - ((depth-1)*5.5f);
  if (r < 1f) r = 1f;
  buffer.stroke(borderCol, a);
  float sWidth = 3.5 - (depth-1);
  if (sWidth < 1) sWidth = 1;
  buffer.strokeWeight(sWidth);
  if(!node.isSplit) {
    if(node.val == null) {
      // quad has no value, blue border
      buffer.stroke(borderCol, a);
      buffer.fill(255);      
    } else {
      // quad has a value, red border
      buffer.stroke(valueCol, a);
      buffer.fill(255);
    }
    buffer.ellipse(x, y, r*0.8, r*0.8);
  }
  else {
    float w = ((width/2f)/(pow(4f, depth)));
    float w2 = w/2f;
    float x1 = x - (w2 * 3);
    float x2 = x - (w2 * 1);
    float x3 = x + (w2 * 1);
    float x4 = x + (w2 * 3);
    float yfac = (depth*0.60);
    float y1 = y+((height/3f)/depth);
    float y2 = y1;
    float y3 = y2;
    float y4 = y3;
    buffer.line(x, y, x1, y1);
    buffer.line(x, y, x2, y2);
    buffer.line(x, y, x3, y3);
    buffer.line(x, y, x4, y4);
    drawTreeNode(buffer, node.ne, x1, y1, depth+1);
    drawTreeNode(buffer, node.nw, x2, y2, depth+1);
    drawTreeNode(buffer, node.sw, x3, y3, depth+1);
    drawTreeNode(buffer, node.se, x4, y4, depth+1);
    buffer.strokeWeight(sWidth);
    buffer.stroke(borderCol, a);
    buffer.fill(backCol);
    buffer.rect(x-(r/2), y-(r/2), r, r);
  }
}

void drawGraph(PGraphics buffer) {
  buffer.noSmooth();
  buffer.strokeWeight(1);
  root.drawBorders(buffer, 1);
  buffer.strokeWeight(1);
  buffer.smooth();
  root.drawValues(buffer, 1);
}

class QTreeVal {
  float x;
  float y;
  QTreeVal(float x, float y){
    this.x = x;
    this.y = y;
  }
  public String toString() {
    return "value (" + x + "," + y + ")";
  }
}

class QTreeNode {
  float x, y, w, h, midw, midh, midx, midy;
  QTreeVal val;
  boolean isSplit = false;
  QTreeNode nw, ne, se, sw;
  
  QTreeNode(float x, float y, float w, float h) {
    this.x = x;
    this.y = y;
    this.w = w;
    this.h = h;
    this.midw = w/2f;
    this.midh = h/2f;
    this.midx = x+midw;
    this.midy = y+midh;
  }
  public void drawBorders(PGraphics pg, int depth) {
    float sW = 4.5f/(depth);
    if(sW < 0.5f) sW = 0.5f;
    pg.strokeWeight(sW);
    pg.stroke(borderCol);
    pg.noFill();
    pg.rect(x, y, w, h);
    if (isSplit) {
      int d = depth + 1;
      nw.drawBorders(pg, d);
      ne.drawBorders(pg, d);
      se.drawBorders(pg, d);
      sw.drawBorders(pg, d);
    }
  }
  public void drawValues(PGraphics pg, int depth) {
    float sW = 3f/(depth);
    if(sW < 1f) sW = 1f;
    pg.strokeWeight(sW);
    if (val != null) {
      pg.stroke(valueCol);
      pg.fill(255);
      //pg.fill(valueCol);
      pg.ellipse(val.x, val.y, 4, 4);
    }
    if (isSplit) {
      int d = depth+1;
      nw.drawValues(pg, d);
      ne.drawValues(pg, d);
      se.drawValues(pg, d);
      sw.drawValues(pg, d);
    }
  }
  public boolean isInside(QTreeVal val) {
    return val.x >= x && val.x <= x+w && val.y >= y && val.y <= y+h;
  }
  public void push(QTreeVal val) {
    this.val = val;
  }
  public void put(QTreeVal val) {
    if (isSplit) {
      if (ne.isInside(val)) ne.put(val);
      if (nw.isInside(val)) nw.put(val);
      if (sw.isInside(val)) sw.put(val);
      if (se.isInside(val)) se.put(val);
    }
    else if (this.val != null) {
      isSplit = true;
      nw = new QTreeNode(x, y, midw, midh);
      ne = new QTreeNode(x+midw, y, midw, midh);
      se = new QTreeNode(x+midw, y+midh, midw, midh);
      sw = new QTreeNode(x, y+midh, midw, midh);
      doprint("Repushing... ");
      put(this.val);
      this.val = null;
      put(val);
    }
    else {
      doprintln("Pushed " + val + " into " + this);
      push(val);
    }
  }
  public String toString() {
    return "quad (" + x + "," + y + "," + (x+w) + "," + (y+h) + ")";
  }
}

void restart() {
    currentStep = 0;
    root = new QTreeNode(0, 0, w, h);
}

void mousePressed() {
  restart();
}

void keyPressed() {
  restart();
}

public void doprint(String s) {
  if (logEnabled) {
    print(s);
  }
}

public void doprintln(String s) {
  if (logEnabled) {
    println(s);
  }
}

Screenshot of the graph and tree view of a quad tree that has stored 15 two-dimensional points as data.

The graph shows where the points, marked by red dots, are in the bounded space (256 x 256). It also shows the partitions of the quadtree, marked by blue bounding boxes. The tree view shows how the Quad Tree looks internally as a tree structure (though some nodes may overlap in the view). It is all animated to show what happens to the Quad Tree as points are added with a configurable delay time.

Updated the visualization with stroke weight and fixed the branch overlap. Also added handling of point data clustering.