# Spatial partitioning class Quad tree

**URL:** <https://discourse.processing.org/t/spatial-partitioning-class-quad-tree/30058>\
**Category:** Gallery\
**Created:** [May 11, 2021, 8:13pm UTC](https://discourse.processing.org/t/spatial-partitioning-class-quad-tree/30058 "2021-05-11T20:13:31Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![paulgoux](https://avatars.discourse-cdn.com/v4/letter/p/b9bd4f/32.png) [@paulgoux](https://discourse.processing.org/u/paulgoux)\
**Post date:** [May 11, 2021, 8:13pm UTC](https://discourse.processing.org/t/spatial-partitioning-class-quad-tree/30058/1 "2021-05-11T20:13:31Z")

</div>

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.

> <https://github.com/guilhermefarto/quadtree-processing/blob/master/QuadTreeProcessing/QuadTree.pde>

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**
>
> ```auto
> 
> 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**
>
> ```auto
> 
> 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**
>
> ```auto
> 
> 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;  
> };  
> };`

 ![image](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/7/7a916abcf713568a573c6482b7b13ddef4bd30dc.png)

---

<div class="post-metadata">

**Author:** ![paulgoux](https://avatars.discourse-cdn.com/v4/letter/p/b9bd4f/32.png) [@paulgoux](https://discourse.processing.org/u/paulgoux)\
**Post date:** [May 11, 2021, 9:57pm UTC](https://discourse.processing.org/t/spatial-partitioning-class-quad-tree/30058/2 "2021-05-11T21:57:49Z")

</div>

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

 ![Screenshot_20210511_225912_processing.test.quadtreeprocessing](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/d/d0ac648c39be1867b507ac513182297e0f8a225f.jpeg)

vs

35 fps for 600 entities

 ![Screenshot_20210511_225539_processing.test.entities](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/6/6645602aed51389f6c0cf1049898cde2670bc0e9.jpeg)

---

<div class="post-metadata">

**Author:** ![jafal](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jafal/32/19112_2.png) [@jafal](https://discourse.processing.org/u/jafal)\
**Post date:** [May 11, 2021, 11:22pm UTC](https://discourse.processing.org/t/spatial-partitioning-class-quad-tree/30058/3 "2021-05-11T23:22:13Z")

</div>

great work and very nice

---

<div class="post-metadata">

**Author:** ![paulgoux](https://avatars.discourse-cdn.com/v4/letter/p/b9bd4f/32.png) [@paulgoux](https://discourse.processing.org/u/paulgoux)\
**Post date:** [May 12, 2021, 1:55am UTC](https://discourse.processing.org/t/spatial-partitioning-class-quad-tree/30058/4 "2021-05-12T01:55:07Z")

</div>

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**
>
> ```auto
> 
> 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**
>
> ```auto
> 
> 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**
>
> ```auto
> 
> 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**
>
> ```auto
> 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;
> };
> };
> 
> ```