quadtree.pde

import processing.pdf.*;

int MARGIN = 0;

class Circle {
  float x;
  float y;
  float r;
  Circle(float x, float y, float r) {
    this.x = x;
    this.y = y;
    this.r = r;
  }
  boolean collides(Circle c) {
    float dist = sq(c.x - x) + sq(c.y - y);
    if (dist <= sq(r + c.r + MARGIN))
      return true;
    return false;
  }
}

ArrayList<Circle> circles;

float r;
float minr = 16;
int iteration = 0;
int failed = 0;
ArrayList<Circle> collision_objects;

void find_stroke() {
  float x, y;
  boolean collides;
  
  while (r >= minr) {
    x = random(width);
    y = random(height);
    Circle nc = new Circle(x, y, r);
    Circle nc2 = new Circle(x, y, r + MARGIN/2);
    
    collides = false;
    collision_objects.clear();
    quad.retrieve(collision_objects, nc2);
    for (int k = 0; k < collision_objects.size(); k++) {
      // Run collision detection algorithm between objects
      if (collision_objects.get(k).collides(nc2)) {
        collides = true;
        break;
      }
    }

    if (collides) {
      failed++;
      if (failed % 100000 == 0)
        println(failed + " tries completed");
      if (failed > 1024 * 1024 / (r*r*r)) {
        println(failed + " tries completed");
        println("new radius: " + r/1.1);
        failed = 0;
        r = r/1.2;
        return;
      }
      continue;
    }

    colorMode(HSB, 360, 255, 255);
    fill(random(280, 300), 255, 255);
    //ellipse(x, y, 2*r, 2*r);
    ellipse(x, y, 2*r, 2*r);
    circles.add(nc);
    quad.insert(nc2);
    break;
  }
}

class Rectangle {
  double x, y, w, h;
  Rectangle(double x, double y, double w, double h) {
    this.x = x;
    this.y = y;
    this.w = w;
    this.h = h;
  }

  double getX() { 
    return x;
  }
  double getY() { 
    return y;
  }
  double getWidth() { 
    return w;
  }
  double getHeight() { 
    return h;
  }
}

class Quadtree {
  int MAX_OBJECTS = 10;
  int MAX_LEVELS = 20;

  int level;                  /* The level of this QuadTree node */
  int quad;
  ArrayList<Circle> objects;  /* Objects at this level */
  Rectangle bounds;           /* The bounds of this QuadTree node */
  Quadtree[] nodes;           /* Nodes for each child quadrant */
  boolean is_split;

  /* Constructor */
  Quadtree(int pLevel, int pQuad, Rectangle pBounds) {
    level = pLevel;
    quad = pQuad;
    objects = new ArrayList<Circle>();
    bounds = pBounds;
    nodes = new Quadtree[4];
    is_split = false;
  }

  void clear() {
    objects.clear(); 
    for (int i = 0; i < nodes.length; i++) {
      if (nodes[i] != null) {
        nodes[i].clear();
        nodes[i] = null;
        nodes[i].is_split = false;
      }
    }
  }

  void split() {
    double x = bounds.getX();
    double y = bounds.getY();
    double subWidth = bounds.getWidth() / 2;
    double subHeight = bounds.getHeight() / 2;
    
    println("Splitting new level: " + (level + 1));

    /* Top-right */
    nodes[0] = new Quadtree(level+1, 0, new Rectangle(x + subWidth, y, subWidth, subHeight));
    /* Top-left */
    nodes[1] = new Quadtree(level+1, 1, new Rectangle(x, y, subWidth, subHeight));
    /* Bottom-left */
    nodes[2] = new Quadtree(level+1, 2, new Rectangle(x, y + subHeight, subWidth, subHeight));
    /* Bottom-right */
    nodes[3] = new Quadtree(level+1, 3, new Rectangle(x + subWidth, y + subHeight, subWidth, subHeight));
    
    is_split = true;
  }
  
  boolean intersects(Circle circle, Rectangle rect)
  {
      float circleDistance_x = abs((float)(circle.x - (rect.x + rect.getWidth()/2)));
      float circleDistance_y = abs((float)(circle.y - (rect.y + rect.getHeight()/2)));
  
      if (circleDistance_x > (rect.getWidth()/2 + circle.r)) { return false; }
      if (circleDistance_y > (rect.getHeight()/2 + circle.r)) { return false; }
  
      if (circleDistance_x <= (rect.getWidth()/2)) { return true; } 
      if (circleDistance_y <= (rect.getHeight()/2)) { return true; }
  
      float cornerDistance_sq = sq((float)(circleDistance_x - rect.getWidth()/2)) + sq((float)(circleDistance_y - rect.getHeight()/2));
  
      return (cornerDistance_sq <= sq(circle.r));
  }

  int get_indices(Circle c) {
    int index = 0;

    double xmin = bounds.getX();
    double ymin = bounds.getY();
    double xmax = xmin + bounds.getWidth();
    double ymax = ymin + bounds.getHeight();
    double xmid = xmin + (bounds.getWidth() / 2);
    double ymid = ymin + (bounds.getHeight() / 2);
    double nwidth = bounds.getWidth();
    double nheight = bounds.getHeight();

    double cxmin = c.x - c.r;
    double cxmax = c.x + c.r;
    double cymin = c.y - c.r;
    double cymax = c.y + c.r;

    boolean top =    (cymin <= ymid && cymax >= ymin);
    boolean bottom = (cymax >= ymid && cymin <  ymax);
    boolean left =   (cxmin <= xmid && cxmax >= xmin);
    boolean right =  (cxmax >= xmid && cxmin <  xmax);
    
    top = intersects(c, new Rectangle(xmin, ymin, nwidth, nheight/2));
    bottom = intersects(c, new Rectangle(xmin, ymid, nwidth, nheight/2));
    left = intersects(c, new Rectangle(xmin, ymin, nwidth/2, nheight));
    right = intersects(c, new Rectangle(xmid, ymin, nwidth/2, nheight));
    
    //println(top + "," + bottom + "," + left + "," + right);
    //println("xmin=" + xmin + ",xmax=" + xmax + ",ymin=" + ymin + ",ymax=" + ymax);
    //println("cxmin=" + cxmin + ",cxmax=" + cxmax + ",cymin=" + cymin + ",cymax=" + cymax);
    //println("xmid=" + xmid + ",ymid=" + ymid);

    if (left) {
      if (top)    { index |= 1 << 1; }
      if (bottom) { index |= 1 << 2; }
    }
    if (right) {
      if (top)    { index |= 1 << 0; }
      if (bottom) { index |= 1 << 3; }
    }

    return index;
  }

  void insert(Circle c) {
    if (is_split) {
      int index = get_indices(c);
      if (index != 0) {
        for (int k = 0; k < 4; k++) {
          if ((index & (1 << k)) != 0)
            nodes[k].insert(c);
        }
      }
      return;
    } else {
      objects.add(c);
      //println("Inserting into quadrant " + (quad + 1) + " at level " + level);
      if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS) {
        //println("Split and rehashed " + objects.size() + " objects at quadrant " + quad + " @ level " + level);
        split();
        while (objects.size() > 0) {
          Circle x = objects.remove(0);
          int index = get_indices(x);
          if (index != 0) {
            for (int k = 0; k < 4; k++) {
              if ((index & (1 << k)) != 0)
                nodes[k].insert(x);
            }
          } else {
            println("Whoops unable to find place for object at quadrant " + quad + " @ level " + level);
            stroke(0);
            noFill();
            //ellipse(x.x, x.y, 2*x.r, 2*x.r);
            //line((float)bounds.getX(), (float)bounds.getY() + (float)bounds.getHeight()/2, (float)bounds.getX() + (float)bounds.getWidth(), (float)bounds.getY() + (float)bounds.getHeight()/2);
            //line((float)bounds.getX() + (float)bounds.getWidth()/2, (float)bounds.getY(), (float)bounds.getX() + (float)bounds.getWidth()/2, (float)bounds.getY() + (float)bounds.getHeight());
            //rect((float)bounds.getX(), (float)bounds.getY(), (float)bounds.getWidth(), (float)bounds.getHeight()); 
          }
        }
        objects.clear();
      }
    }
  }

  ArrayList<Circle> retrieve(ArrayList<Circle> ret, Circle c) {
    if (is_split) {
      int index = get_indices(c);
      for (int i = 0; i < 4; i++) {
        if ((index & (1 << i)) != 0)
          nodes[i].retrieve(ret, c);
      }
    } else {
      ret.addAll(objects);
    }
    return ret;
  }
}

PImage img;
Quadtree quad;

void setup() {
  size(500, 500); //, PDF, "scape" + n + ".pdf");
  background(255);
  noStroke();
  circles = new ArrayList<Circle>();
  quad = new Quadtree(0, 0, new Rectangle(0, 0, width, height));
  quad.clear();
  r = 128;
  minr = 1;
  failed = 0;
  iteration = 0;
  collision_objects = new ArrayList<Circle>();
}

void draw() {
  noStroke();
  if (r >= minr)
    find_stroke();
  else {
    //filter(BLUR, 1);
    noLoop();
  }
  //stroke(0);
  //line(0, height/2, width, height/2);
  //line(width/2, 0, width/2, height);
}