Spatial partitioning class Quad tree

paulgoux · May 11, 2021, 8:13pm

Currently working on adding functionality to the lib.

Here is another class will be adding the QuadTree class. I currently have a quadGrid but trees are more efficient.

guilhermefarto/quadtree-processing/blob/master/QuadTreeProcessing/QuadTree.pde


import java.util.Iterator;
import java.util.Map;

final boolean LOCK_INSERTION_BY_MAX_OBJECTS = false;
final boolean ENABLE_RANDOM_COLOR_PER_QUAD = false;

class QuadTree {

  ArrayList<Object> objects = new ArrayList<Object>();

  int x;
  int y;
  int width;
  int height;

  int level; 
  int maxObjects;
  int maxLevels;

This file has been truncated. show original

This is the original code.

this is the new project pde files. (not yet imported to eclipse).
This produces a quadtree which is updated in realtime.

I would just need a little feedback if some you dont mind. Just need to iron out any flaws which this class may have however I’m unsure how to test further.

Anyways here are the pde files.

Summary


import java.awt.event.KeyEvent;

final int DEFAULT_SCALE = 4;
final int MAX_OBJECTS = 4;

int MAX_LEVELS;
int RANDOM_OBJECTS;

qContainer q;
boolean simulateQuadTrees = false;


void setup() {
  size(512, 512,FX2D);
  q = new qContainer(this);
}

void draw() {
  background(50);
  q.draw();
  fill(255);
  text(frameRate,200,200);
  text(q.objects.size(),200,220);
}

Summary


final int DEFAULT_SIZE = DEFAULT_SCALE;

class Object {
  qContainer parent;
  int value, id = -1, qid = -1;
  int x,bx;
  int y,by;


  Object(int id, int value, int x, int y) {
    id = id;
    this.value = value;
    this.x = x;
    this.y = y;
    bx = x;
    by = y;
  }

  Object(int value, int x, int y) {
    this.value = value;
    this.x = x;
    this.y = y;
    bx = x;
    by = y;
  }

  void draw(color colorForQuad) {
    fill(colorForQuad);
    stroke(255);

    ellipse(this.x * DEFAULT_SCALE, this.y * DEFAULT_SCALE, DEFAULT_SIZE, DEFAULT_SIZE);
    update();
  };
  
  void update(){
    x+= random(-1,2);
    y+= random(-1,2);
    //println("hhh", frameCount);
  };

  void log() {
    println("Logging Object for [value, x, y] = " + value + " , " + x + " , " + y);
  }
}

Summary


import java.util.Iterator;
import java.util.Map;

final boolean LOCK_INSERTION_BY_MAX_OBJECTS = false;
final boolean ENABLE_RANDOM_COLOR_PER_QUAD = false;

class QuadTree {
  qContainer parent;
  PApplet applet;
  ArrayList<Object> objects = new ArrayList<Object>();

  int x, bx, by, id;
  int y;
  int width;
  int height;

  int level; 
  int maxObjects;
  int maxLevels;

  color randomColorForObjects;

  QuadTree nw, ne, sw, se;
  HashMap<Integer, QuadTree> quads = new HashMap<Integer, QuadTree>();

  boolean isRoot = false;

  QuadTree(int level, int x, int y, int width, int height, int maxObjects, int maxLevels) {
    this(level, x, y, width, height, maxObjects, maxLevels, false);
  }

  QuadTree(int level, int x, int y, int width, int height, int maxObjects, int maxLevels, boolean isRoot) {
    this.level = level;

    this.x = x;
    this.y = y;
    this.bx = x;
    this.by = y;
    this.width = width;
    this.height = height;

    this.maxObjects = maxObjects;
    this.maxLevels = maxLevels;

    this.isRoot = isRoot;

    if (ENABLE_RANDOM_COLOR_PER_QUAD) {
      this.randomColorForObjects = color(int(random(0, 255)), int(random(0, 255)), int(random(0, 255)));
    } else {
      this.randomColorForObjects = color(150);
    }
  };

  QuadTree(int level, int x, int y, int width, int height, int maxObjects, int maxLevels, boolean isRoot, qContainer q) {
    parent = q;
    this.level = level;

    this.x = x;
    this.y = y;
    this.bx = x;
    this.by = y;
    this.width = width;
    this.height = height;

    this.maxObjects = maxObjects;
    this.maxLevels = maxLevels;

    this.isRoot = isRoot;

    if (ENABLE_RANDOM_COLOR_PER_QUAD) {
      this.randomColorForObjects = color(int(random(0, 255)), int(random(0, 255)), int(random(0, 255)));
    } else {
      this.randomColorForObjects = color(150);
    }
  };

  void delete(Object o) {
    int quadIndex = getQuadIndex(o);
    if (o.id!=quadIndex) {
      //quads.remove(quadIndex);
      //quads.get(id).addObject(o);
    }
  };

  boolean addObjectN(Object object) {
    if (!this.quads.isEmpty()) {
      int quadIndex = getQuadIndex(object);
      //object.qid = quadIndex;
      if(object.qid!=quadIndex){
        int n = this.quads.get(quadIndex).objects.indexOf(object);
        if(n>-1&&object.id>-1)this.quads.get(object.id).objects.remove(n);
        object.qid = quadIndex;
      }
      if (quadIndex != -1) {
        this.quads.get(quadIndex).addObjectN(object);

        return true;
      }
    }

    if(!objects.contains(object))this.objects.add(object);
    //if (!parent.objects.contains(object))parent.objects.add(object);

    if (this.objects.size() > this.maxObjects) {
      if (this.level < this.maxLevels) {
        if (this.quads.isEmpty()) {
          this.split();
        }

        exchangeObjectsToQuads();
      } else {
        if (LOCK_INSERTION_BY_MAX_OBJECTS) {
          this.removeObject(object);
        }
      }
    }

    return true;
  };
  
  boolean addObject2(Object o) {
    if (!this.quads.isEmpty()) {
      int quadIndex = getQuadIndex(o);
      if(o.qid!=-1&&o.id!=o.qid){
        int n = this.quads.get(quadIndex).objects.indexOf(o);
        if(n>-1&&o.id>-1)this.quads.get(o.id).objects.remove(n);
        this.quads.get(quadIndex).addObject2(o);
        
      }else if (quadIndex != -1) {
        this.quads.get(quadIndex).addObject2(o);
        

        return true;
      }
    }
    if (this.objects.size() > this.maxObjects) {
      if (this.level < this.maxLevels) {
        if (this.quads.isEmpty()) {
          this.split();
        }

        exchangeObjectsToQuads();
      } else {
        if (LOCK_INSERTION_BY_MAX_OBJECTS) {
          this.removeObject(o);
        }
      }
    }

    return true;
  };

boolean addObject(Object object) {
    if (!this.quads.isEmpty()) {
      int quadIndex = getQuadIndex(object);
      object.qid = quadIndex;

      if (quadIndex != -1) {
        this.quads.get(quadIndex).addObject(object);

        return true;
      }
    }

    this.objects.add(object);
    if (!parent.objects.contains(object))parent.objects.add(object);

    if (this.objects.size() > this.maxObjects) {
      if (this.level < this.maxLevels) {
        if (this.quads.isEmpty()) {
          this.split();
        }

        exchangeObjectsToQuads();
      } else {
        if (LOCK_INSERTION_BY_MAX_OBJECTS) {
          this.removeObject(object);
        }
      }
    }

    return true;
  };

  boolean exchangeObjectsToQuads() {
    Iterator<Object> iObject = this.objects.iterator();

    while (iObject.hasNext()) { 
      Object object = iObject.next();

      int quadIndex = this.getQuadIndex(object);

      if (quadIndex != -1) {
        this.quads.get(quadIndex).addObject(object);

        iObject.remove();
      }
    }

    return true;
  }

  boolean removeObject(Object object) {
    this.objects.remove(object);

    return true;
  }

  boolean clear() {
    this.objects.clear();

    for (Map.Entry entry : this.quads.entrySet()) {
      ((QuadTree) entry.getValue()).clear();
    }

    this.quads.clear();

    return true;
  }

  int getQuadIndex(Object object) {
    int xForObject = object.x;
    int yForObject = object.y;

    boolean isLeftQuad = xForObject >= this.x && xForObject < (this.x + this.width / 2);
    boolean isTopQuad = yForObject >= this.y && yForObject < (this.y + this.height / 2);

    if (isLeftQuad && isTopQuad) { // nw quad
      return 1;
    } else if (!isLeftQuad && isTopQuad) { // ne quad
      return 2;
    } else if (isLeftQuad && !isTopQuad) { // sw quad
      return 3;
    } else if (!isLeftQuad && !isTopQuad) { // se quad
      return 4;
    }

    return -1;
  }

  boolean split() {
    if (!this.quads.isEmpty()) {
      throw new java.lang.IllegalStateException("QuadTree already splitted...");
    }

    int halfWidth = this.width / 2;
    int halfHeight = this.height / 2;

    nw = new QuadTree(this.level + 1, this.x, this.y, halfWidth, halfHeight, maxObjects, maxLevels);
    nw.parent = parent;

    ne = new QuadTree(this.level + 1, this.x + halfWidth, this.y, halfWidth, halfHeight, maxObjects, maxLevels);
    ne.parent = parent;
    sw = new QuadTree(this.level + 1, this.x, this.y + halfHeight, halfWidth, halfHeight, maxObjects, maxLevels);
    sw.parent = parent;
    se = new QuadTree(this.level + 1, this.x + halfWidth, this.y + halfHeight, halfWidth, halfHeight, maxObjects, maxLevels);
    se.parent = parent;

    this.quads.put(1, nw);
    this.quads.put(2, ne);
    this.quads.put(3, sw);
    this.quads.put(4, se);

    return true;
  }

  void draw() {
    if (!this.quads.isEmpty()) {
      nw.draw();
      ne.draw();
      sw.draw();
      se.draw();
    }

    drawObjects();

    noFill();
    stroke(220, 220, 0);

    rect(x * DEFAULT_SCALE, y * DEFAULT_SCALE, width * DEFAULT_SCALE, height * DEFAULT_SCALE);
  }

  void drawObjects() {
    for (Object object : this.objects) {
      object.draw(this.randomColorForObjects);
    }
  }

  void simulate(QuadTree root, int scale, int maxLevels) {
    if (parent.simulate) {
      noFill();
      stroke(200, 200, 0);

      rect(root.x * scale, root.y * scale, root.width * scale, root.height * scale);
    }

    if (root.level < maxLevels) {
      int halfWidth = root.width / 2;
      int halfHeight = root.height / 2;

      simulate(new QuadTree(root.level + 1, root.x, root.y, halfWidth, halfHeight, maxObjects, maxLevels), scale, maxLevels);
      simulate(new QuadTree(root.level + 1, root.x + halfWidth, root.y, halfWidth, halfHeight, maxObjects, maxLevels), scale, maxLevels);
      simulate(new QuadTree(root.level + 1, root.x, root.y + halfHeight, halfWidth, halfHeight, maxObjects, maxLevels), scale, maxLevels);
      simulate(new QuadTree(root.level + 1, root.x + halfWidth, root.y + halfHeight, halfWidth, halfHeight, maxObjects, maxLevels), scale, maxLevels);
    }
  }

  void loadData(int[][] data) {
    this.clear();

    if (data != null) {
      for (int rowId = 0; rowId < data.length; rowId++) {
        for (int colId = 0; colId < data[0].length; colId++) {
          if (data[rowId][colId] == 1) {
            this.addObject(new Object(1, colId, rowId));
          }
        }
      }
    }
  };

  
  void loadData2(ArrayList<Object> data) {
    this.clear();

    for (int i =0;i< data.size(); i++) {
      Object o = data.get(i);
      
      if(o.bx!=o.x||o.by!=o.y)this.addObjectN(o);
    }
  };

  void print() {
    println("Logging QuadTree for [x, y, width, height] = " + this.x + " , " + this.y + " , " + this.width + " , " + this.height);
  };

  void init() {
    //clear();
    //smooth();
    //background(50);

    parent.rows = height / DEFAULT_SCALE;
    parent.cols = width / DEFAULT_SCALE;

    MAX_LEVELS = int((log(width / DEFAULT_SCALE) / log(2)));
    RANDOM_OBJECTS = int(pow(MAX_LEVELS, 2) * MAX_OBJECTS) * 2;

    parent.data = new int[parent.rows][parent.cols];

    if (parent.root == null) {
      parent.root = new QuadTree(1, 0, 0, parent.cols, parent.rows, MAX_OBJECTS, MAX_LEVELS, true);
      
    } else {
      parent.root.clear();
    }

    println("Logging for Grid [rows, cols] = " + parent.rows + " , " + parent.cols);
    println("Min. Level QuadTree: " + (parent.rows / int(pow(2, MAX_LEVELS - 1))));
  };
};

Summary

`class qContainer {
PApplet applet;
int rows, cols;
int[][] data,ndata;
QuadTree root = null;
boolean mdown, kdown,simulate = true,updateGrid,wait;
ArrayList objects = new ArrayList();
qContainer() {
};

qContainer(PApplet p) {
applet = p;
init();

};

void init() {
clear();
smooth();
background(50);

rows = applet.height / DEFAULT_SCALE;
cols = applet.width / DEFAULT_SCALE;

MAX_LEVELS = int((log(applet.width / DEFAULT_SCALE) / log(2)));
RANDOM_OBJECTS = int(pow(MAX_LEVELS, 2) * MAX_OBJECTS) * 2;

data = new int[rows][cols];

if (root == null) {
  root = new QuadTree(1, 0, 0, cols, rows, MAX_OBJECTS, MAX_LEVELS, true,this);
  root.parent = this;
} else {
  root.clear();
}

println("Logging for Grid [rows, cols] = " + rows + " , " + cols);
println("Min. Level QuadTree: " + (rows / int(pow(2, MAX_LEVELS - 1))));

};

void draw() {
//drawGrid();

if (simulateQuadTrees) {
  root.simulate(root, DEFAULT_SCALE, MAX_LEVELS);
} else {
  root.draw();
}
kPressed();
mPressed();
mDragged();
if(!mdown&&!kdown&&!wait)updateGrid();
//init();
if(wait){
  println("wait");
  wait = false;
  
}

};

public void update(){

};

void drawGrid() {
noFill();
stroke(70);

for (int rowId=0; rowId<data.length; rowId++) {
  for (int colId=0; colId<data[0].length; colId++) {
    rect(colId * DEFAULT_SCALE, rowId * DEFAULT_SCALE, DEFAULT_SCALE, DEFAULT_SCALE);
  }
}

};

void generateRandomObjects() {
for (int i = 0; i < RANDOM_OBJECTS; i++) {
data[int(random(0, rows))][int(random(0, cols))] = 1;
}
println(“data gen”);
root.loadData(data);
};

void updateGrid(){
//if(!updateGrid)
for (int i = 0; i < objects.size(); i++) {
Object o = objects.get(i);
data[o.by][o.bx] = 0;
if(o.x>-1&&o.x<data.length
&&o.y>-1&&o.y<data[0].length)
data[o.y][o.x] = 1;

}
//root.loadDataN(data);
//println("hello");
root.loadData2(objects);
//updateGrid = true;

};

void kPressed() {
if (keyPressed&&!kdown) {
String keyAsString = str(key).toUpperCase();
objects = new ArrayList();
wait = true;
if (keyAsString.equalsIgnoreCase(“C”)) { // Clear
init();
} else if (keyAsString.equalsIgnoreCase(“R”)) { // Generate random objects

    init();
    generateRandomObjects();
  } else if (key == CODED && keyCode == KeyEvent.VK_F2) { // Show or hide (simulate) QuadTrees
    simulateQuadTrees = !simulateQuadTrees;
  }
  kdown = false;
}
if (!keyPressed)kdown = false;

};

void mPressed() {
if (mousePressed&&!mdown) {
int colId = getSelectedCol(mouseX);
int rowId = getSelectedRow(mouseY);

  if (colId == -1 || rowId == -1) {
    return;
  }

  data[rowId][colId] = 1;
  Object o = new Object(1, colId, rowId);
  o.parent = this;
  root.addObject(o);
  mdown = true;
}
if (!applet.mousePressed)mdown = false;

};

void mDragged() {
if (mdown) {
int colId = getSelectedCol(applet.mouseX);
int rowId = getSelectedRow(applet.mouseY);

  if (colId == -1 || rowId == -1) {
    return;
  }

  data[rowId][colId] = 1;
  Object o = new Object(1, colId, rowId);
  o.parent = this;
  if(!root.objects.contains(o))root.addObject(o);
};

};

boolean hasObject(int rowId, int colId) {
return data[rowId][colId] == 1;
};

int getSelectedRow(int mouseY) {
return mouseY >=0 && mouseY < applet.height ? mouseY / DEFAULT_SCALE : -1;
};

int getSelectedCol(int mouseX) {
return mouseX >=0 && mouseX < applet.width ? mouseX / DEFAULT_SCALE : -1;
};
};`

paulgoux · May 11, 2021, 9:57pm

some improvements noted over the Quadgrid version 30 fps with over 1000 particles on mobile.

vs

35 fps for 600 entities

jafal · May 11, 2021, 11:22pm

great work and very nice

paulgoux · May 12, 2021, 1:55am

Ive just noticed that the previous versions were coded initially to work with integers only. Ive now updated with floats. now you should be able to change the size without any display issues.

Summary


import java.awt.event.KeyEvent;

final int DEFAULT_SCALE = 10;
final int MAX_OBJECTS = 2;

int MAX_LEVELS;
int RANDOM_OBJECTS;

qContainer q;
boolean simulateQuadTrees = false;


void setup() {
  size(600, 600,FX2D);
  q = new qContainer(this);
}

void draw() {
  background(50);
  q.draw();
  fill(255);
  text(frameRate,200,200);
  text(q.objects.size(),200,220);
}

Summary


final int DEFAULT_SIZE = DEFAULT_SCALE;

class Object {
  qContainer parent;
  int value, id = -1, qid = -1;
  float x, bx,y, by;
  int xpos,ypos,bxpos,bypos;

  Object(int id, int value, float x, float y,QuadTree q) {
    parent = q.parent;
    id = id;
    this.value = value;
    this.x = x;
    this.y = y;
    bx = x;
    by = y;
    xpos = getxPos();
    xpos = getyPos();
    bxpos = xpos;
    bypos = ypos;
  }

  Object(int value, float x, float y,QuadTree q) {
    parent = q.parent;
    this.value = value;
    this.x = x;
    this.y = y;
    bx = x;
    by = y;
    xpos = getxPos();
    xpos = getyPos();
  }

  void draw(color colorForQuad) {
    fill(colorForQuad);
    stroke(255);

    ellipse(this.x , this.y , DEFAULT_SIZE, DEFAULT_SIZE);
    update();
  };

  void update() {
    float a = 2;
    x+= random(-a, a);
    y+= random(-a, a);
    xpos = getxPos();
    xpos = getyPos();
    //println("hhh", frameCount);
  };
  
  int getxPos(){
    return (int) (x/parent.root.w);
  };
  
  int getyPos(){
    return (int) (y/parent.root.h);
  };

  void log() {
    println("Logging Object for [value, x, y] = " + value + " , " + x + " , " + y);
  }
}

Summary


import java.util.Iterator;
import java.util.Map;

final boolean LOCK_INSERTION_BY_MAX_OBJECTS = false;
final boolean ENABLE_RANDOM_COLOR_PER_QUAD = false;

class QuadTree {
  qContainer parent;
  PApplet applet;
  ArrayList<Object> objects = new ArrayList<Object>();

  int  id,xpos,ypos,bxpos,bypos;
  float x, bx,y,by,w,h;
  
  int level; 
  int maxObjects;
  int maxLevels;

  color randomColorForObjects;

  QuadTree nw, ne, sw, se;
  HashMap<Integer, QuadTree> quads = new HashMap<Integer, QuadTree>();

  boolean isRoot = false;

  QuadTree(int level, float x, float y, float width, float height, int maxObjects, int maxLevels) {
    this(level, x, y, width, height, maxObjects, maxLevels, false);
  }

  QuadTree(int level, float x, float y, float width, float height, int maxObjects, int maxLevels, boolean isRoot) {
    this.level = level;

    this.x = x;
    this.y = y;
    this.bx = x;
    this.by = y;
    this.w = width;
    this.h = height;
    xpos = getxPos();
    xpos = getyPos();
    this.maxObjects = maxObjects;
    this.maxLevels = maxLevels;

    this.isRoot = isRoot;

    if (ENABLE_RANDOM_COLOR_PER_QUAD) {
      this.randomColorForObjects = color(int(random(0, 255)), int(random(0, 255)), int(random(0, 255)));
    } else {
      this.randomColorForObjects = color(150);
    }
  };

  QuadTree(int level, int x, int y, int width, int height, int maxObjects, int maxLevels, boolean isRoot, qContainer q) {
    parent = q;
    this.level = level;

    this.x = x;
    this.y = y;
    this.bx = x;
    this.by = y;
    this.w = width;
    this.h = height;
    xpos = getxPos();
    xpos = getyPos();
    

    this.maxObjects = maxObjects;
    this.maxLevels = maxLevels;

    this.isRoot = isRoot;

    if (ENABLE_RANDOM_COLOR_PER_QUAD) {
      this.randomColorForObjects = color(int(random(0, 255)), int(random(0, 255)), int(random(0, 255)));
    } else {
      this.randomColorForObjects = color(150);
    }
  };

  void delete(Object o) {
    int quadIndex = getQuadIndex(o);
    if (o.id!=quadIndex) {
      //quads.remove(quadIndex);
      //quads.get(id).addObject(o);
    }
  };

  boolean addObjectN(Object object) {
    if (!this.quads.isEmpty()) {
      int quadIndex = getQuadIndex(object);
      //object.qid = quadIndex;
      if (object.qid!=quadIndex) {
        int n = this.quads.get(quadIndex).objects.indexOf(object);
        if (n>-1&&object.id>-1)this.quads.get(object.id).objects.remove(n);
        object.qid = quadIndex;
      }
      if (quadIndex != -1) {
        this.quads.get(quadIndex).addObjectN(object);

        return true;
      }
    }

    if (!objects.contains(object))this.objects.add(object);
    //if (!parent.objects.contains(object))parent.objects.add(object);

    if (this.objects.size() > this.maxObjects) {
      if (this.level < this.maxLevels) {
        if (this.quads.isEmpty()) {
          this.split();
        }

        exchangeObjectsToQuads();
      } else {
        if (LOCK_INSERTION_BY_MAX_OBJECTS) {
          this.removeObject(object);
        }
      }
    }

    return true;
  };

  boolean addObject(Object object) {
    if (!this.quads.isEmpty()) {
      int quadIndex = getQuadIndex(object);
      object.qid = quadIndex;

      if (quadIndex != -1) {
        this.quads.get(quadIndex).addObject(object);

        return true;
      }
    }

    this.objects.add(object);
    if (!parent.objects.contains(object))parent.objects.add(object);

    if (this.objects.size() > this.maxObjects) {
      if (this.level < this.maxLevels) {
        if (this.quads.isEmpty()) {
          this.split();
        }

        exchangeObjectsToQuads();
      } else {
        if (LOCK_INSERTION_BY_MAX_OBJECTS) {
          this.removeObject(object);
        }
      }
    }

    return true;
  };

  boolean exchangeObjectsToQuads() {
    Iterator<Object> iObject = this.objects.iterator();

    while (iObject.hasNext()) { 
      Object object = iObject.next();

      int quadIndex = this.getQuadIndex(object);

      if (quadIndex != -1) {
        this.quads.get(quadIndex).addObject(object);

        iObject.remove();
      }
    }

    return true;
  }

  boolean removeObject(Object object) {
    this.objects.remove(object);

    return true;
  }

  boolean clear() {
    this.objects.clear();

    for (Map.Entry entry : this.quads.entrySet()) {
      ((QuadTree) entry.getValue()).clear();
    }

    this.quads.clear();

    return true;
  }

  int getQuadIndex(Object object) {
    float xForObject = object.x;
    float yForObject = object.y;

    boolean isLeftQuad = xForObject >= this.x && xForObject < (this.x + this.w / 2);
    boolean isTopQuad = yForObject >= this.y && yForObject < (this.y + this.h / 2);

    if (isLeftQuad && isTopQuad) { // nw quad
      return 1;
    } else if (!isLeftQuad && isTopQuad) { // ne quad
      return 2;
    } else if (isLeftQuad && !isTopQuad) { // sw quad
      return 3;
    } else if (!isLeftQuad && !isTopQuad) { // se quad
      return 4;
    }

    return -1;
  }

  boolean split() {
    if (!this.quads.isEmpty()) {
      throw new java.lang.IllegalStateException("QuadTree already splitted...");
    }

    float halfWidth = this.w / 2;
    float halfHeight = this.h / 2;

    nw = new QuadTree(this.level + 1, this.x, this.y, halfWidth, halfHeight, maxObjects, maxLevels);
    nw.parent = parent;

    ne = new QuadTree(this.level + 1, this.x + halfWidth, this.y, halfWidth, halfHeight, maxObjects, maxLevels);
    ne.parent = parent;
    sw = new QuadTree(this.level + 1, this.x, this.y + halfHeight, halfWidth, halfHeight, maxObjects, maxLevels);
    sw.parent = parent;
    se = new QuadTree(this.level + 1, this.x + halfWidth, this.y + halfHeight, halfWidth, halfHeight, maxObjects, maxLevels);
    se.parent = parent;

    this.quads.put(1, nw);
    this.quads.put(2, ne);
    this.quads.put(3, sw);
    this.quads.put(4, se);

    return true;
  }

  void draw() {
    if (!this.quads.isEmpty()) {
      nw.draw();
      ne.draw();
      sw.draw();
      se.draw();
    }

    drawObjects();

    noFill();
    stroke(220, 220, 0);

    rect(x , y , w, h);
  }

  void drawObjects() {
    for (Object object : this.objects) {
      object.draw(this.randomColorForObjects);
    }
  }

  void simulate(QuadTree root, int scale, int maxLevels) {
    if (parent.simulate) {
      noFill();
      stroke(200, 200, 0);

      rect(root.x , root.y , root.w , root.h );
    }

    if (root.level < maxLevels) {
      float halfWidth = root.w / 2;
      float halfHeight = root.h / 2;

      simulate(new QuadTree(root.level + 1, root.x, root.y, halfWidth, halfHeight, maxObjects, maxLevels), scale, maxLevels);
      simulate(new QuadTree(root.level + 1, root.x + halfWidth, root.y, halfWidth, halfHeight, maxObjects, maxLevels), scale, maxLevels);
      simulate(new QuadTree(root.level + 1, root.x, root.y + halfHeight, halfWidth, halfHeight, maxObjects, maxLevels), scale, maxLevels);
      simulate(new QuadTree(root.level + 1, root.x + halfWidth, root.y + halfHeight, halfWidth, halfHeight, maxObjects, maxLevels), scale, maxLevels);
    }
  }

  void loadData(int[][] data) {
    this.clear();

    if (data != null) {
      for (int rowId = 0; rowId < data.length; rowId++) {
        for (int colId = 0; colId < data[0].length; colId++) {
          if (data[rowId][colId] == 1) {
            float rx = colId *w ;
            float ry = rowId *h ;
            this.addObject(new Object(1, rx, ry,this));
          }
        }
      }
    }
  };


  void loadData2(ArrayList<Object> data) {
    this.clear();

    for (int i =0; i< data.size(); i++) {
      Object o = data.get(i);
      parent.data[o.bypos][o.bxpos] = 0;
      if (o.x>-1&&o.x<parent.data.length
        &&o.y>-1&&o.y<parent.data[0].length)
        parent.data[o.ypos][o.xpos] = 1;
      if (o.bx!=o.x||o.by!=o.y)this.addObjectN(o);
    }
  };

  void print() {
    println("Logging QuadTree for [x, y, width, height] = " + this.x + " , " + this.y + " , " + this.w + " , " + this.w);
  };

  void init() {
    //clear();
    //smooth();
    //background(50);

    parent.rows = height / DEFAULT_SCALE;
    parent.cols = width / DEFAULT_SCALE;

    MAX_LEVELS = int((log(width / DEFAULT_SCALE) / log(2)));
    RANDOM_OBJECTS = int(pow(MAX_LEVELS, 2) * MAX_OBJECTS) * 2;

    parent.data = new int[parent.rows][parent.cols];

    if (parent.root == null) {
      parent.root = new QuadTree(1, 0, 0, parent.cols, parent.rows, MAX_OBJECTS, MAX_LEVELS, true);
    } else {
      parent.root.clear();
    }

    println("Logging for Grid [rows, cols] = " + parent.rows + " , " + parent.cols);
    println("Min. Level QuadTree: " + (parent.rows / int(pow(2, MAX_LEVELS - 1))));
  };
  
  int getxPos(){
    return (int) (x/w);
  };
  
  int getyPos(){
    return (int) (y/h);
  };
};

Summary

class qContainer {
  PApplet applet;
  int rows, cols;
  int[][] data, ndata;
  QuadTree root = null;
  boolean mdown, kdown, simulate = true, updateGrid, wait;
  ArrayList<Object> objects = new ArrayList<Object>();
  qContainer() {
  };

  qContainer(PApplet p) {
    applet = p;
    init();
  };

  void init() {
    clear();
    smooth();
    background(50);

    rows = applet.height / DEFAULT_SCALE;
    cols = applet.width / DEFAULT_SCALE;

    MAX_LEVELS = int((log(applet.width / DEFAULT_SCALE) / log(2)));
    RANDOM_OBJECTS = int(pow(MAX_LEVELS, 2) * MAX_OBJECTS) * 2;

    data = new int[rows][cols];

    if (root == null) {
      root = new QuadTree(1, 0, 0, width, height, MAX_OBJECTS, MAX_LEVELS, true, this);
      root.parent = this;
    } else {
      root.clear();
    }

    println("Logging for Grid [rows, cols] = " + rows + " , " + cols);
    println("Min. Level QuadTree: " + (rows / int(pow(2, MAX_LEVELS - 1))));
  };

  void draw() {
    drawGrid();

    if (simulateQuadTrees) {
      root.simulate(root, DEFAULT_SCALE, MAX_LEVELS);
    } else {
      root.draw();
    }
    kPressed();
    mPressed();
    mDragged();
    if (!mdown&&!kdown&&!wait)updateGrid();
    //init();
    if (wait) {
      println("wait");
      wait = false;
    }
  };

  public void update() {
  };

  void drawGrid() {
    noFill();
    stroke(70);

    for (int rowId=0; rowId<data.length; rowId++) {
      for (int colId=0; colId<data[0].length; colId++) {
        rect(colId * DEFAULT_SCALE, rowId * DEFAULT_SCALE, DEFAULT_SCALE, DEFAULT_SCALE);
      }
    }
  };

  void generateRandomObjects() {
    for (int i = 0; i < RANDOM_OBJECTS; i++) {
      data[int(random(0, rows))][int(random(0, cols))] = 1;
    }
    println("data gen");
    root.loadData(data);
  };

  void updateGrid() {
    root.loadData2(objects);
    //updateGrid = true;
  };


  void kPressed() {
    if (keyPressed&&!kdown) {
      String keyAsString = str(key).toUpperCase();
      objects = new ArrayList<Object>();
      wait = true;
      if (keyAsString.equalsIgnoreCase("C")) { // Clear
        init();
      } else if (keyAsString.equalsIgnoreCase("R")) { // Generate random objects

        init();
        generateRandomObjects();
      } else if (key == CODED && keyCode == KeyEvent.VK_F2) { // Show or hide (simulate) QuadTrees
        simulateQuadTrees = !simulateQuadTrees;
      }
      kdown = false;
    }
    if (!keyPressed)kdown = false;
  };

  void mPressed() {
    if (mousePressed&&!mdown) {
      int colId = getSelectedCol(mouseX);
      int rowId = getSelectedRow(mouseY);

      if (colId == -1 || rowId == -1) {
        return;
      }

      data[rowId][colId] = 1;
      Object o = new Object(1, applet.mouseX, applet.mouseY,root);
      o.parent = this;
      root.addObject(o);
      mdown = true;
    }
    if (!applet.mousePressed)mdown = false;
  };

  void mDragged() {
    if (mdown) {
      int colId = getSelectedCol(applet.mouseX);
      int rowId = getSelectedRow(applet.mouseY);

      if (colId == -1 || rowId == -1) {
        return;
      }

      data[rowId][colId] = 1;
      Object o = new Object(1, applet.mouseX, applet.mouseY,root);
      o.parent = this;
      if (!root.objects.contains(o))root.addObject(o);
    };
  };

  boolean hasObject(int rowId, int colId) {
    return data[rowId][colId] == 1;
  };

  int getSelectedRow(int mouseY) {
    return mouseY >=0 && mouseY < applet.height ? mouseY / DEFAULT_SCALE : -1;
  };

  int getSelectedCol(int mouseX) {
    return mouseX >=0 && mouseX < applet.width ? mouseX / DEFAULT_SCALE : -1;
  };
};

Topic		Replies	Views
Quadtree vs grid Project Guidance	4	1242	September 10, 2019
Quadtree Demonstrator Gallery	3	234	October 7, 2022
Quad grid collisions and spacial partitioning Gallery	3	527	July 24, 2020
Quadtrees image compression Coding Questions	5	679	January 9, 2024
[SOLVED] Importing other Processing classes Processing	7	819	September 25, 2018

Spatial partitioning class Quad tree

Related topics