(another) Simple QuadTree implementation that doesn't use any rectangle classes

Shared Code
#1

I put together my own quadtree implementation that I mostly didn’t write but I made it easy for you to put into your own projects.
Go look at KaiHH’s implementation instead. My “implementation” was really just code stolen from a tutorial that I thought “worked” but clearly doesn’t.

Classes here

Example:
In order for your entities to be compatible with the QuadTree implementation, you must implement the interface Sizeable which returns X, Y, and width and height.


QuadTree quadtree = new QuadTree(<your width>, <your height>);

// every game update (preferably not every frame)
quadtree.clear();
for (int i = 0; i < entities.size; i++) {
	quadtree.insert(<your entity that implements Sizeable here>);
}

// to return a list of entities near a given entity
ArrayList<Sizeable> array = new ArrayList<>();

array.clear();
// fills the arraylist with entities near a given entity
quadtree.retrieve(array, <your entity>);

I didn’t make most of this, I just wanted to share (and have a little bit of competition from the other one submitted here ;D). Supports floats.

#2

I am trying to use this in a little Processing sketch, but it seems that the retrieve() function only ever returns the border objects. Here is an example where I’m polling the green area and receiving the red objects.

ArrayList<Ball> balls = new ArrayList<Ball>();

void setup() {
  size(500, 500);

  for (int i = 0; i < 10000; i++) {
    balls.add(new Ball());
  }
}

void draw() {
  background(0);

  QuadTree qt = new QuadTree(500, 500);
  for (Ball b : balls) {
    qt.insert(b);
  }
  
  ArrayList<Ball> near = new ArrayList<Ball>();
  qt.retrieve(near, new Ball(mouseX, mouseY, 50, 50));

  for (Ball b : balls) {
    b.draw(near.contains(b));
  }
  
  fill(0, 255, 0);
  ellipse(mouseX, mouseY, 50, 50);
}

class Ball {
  float x;
  float y;
  float width;
  float height;


  public Ball(float x, float y, float width, float height){
   this.x = x;
   this.y = y;
   this.width = width;
   this.height = height;
  }

  public Ball() {
    x = random(500);
    y = random(500);
    width = 10;
    height = 10;
  }

  public float getX() {
    return x;
  }

  public float getY() {
    return y;
  }

  public float getWidth() {
    return width;
  }

  public float getHeight() {
    return height;
  }

  void draw(boolean near) {
    if(near){
      fill(255, 0, 0);
    }
    else{
      fill(255);
    }
    ellipse(x, y, width, height);
  }
}
#3

That mentioned quadtree algorithm indeed does not work at all, because it assumes that the query for a rectangular area can fully be satisfied/answered by one child (via the getIndex method), which is not at all the case.
It also wrongly just returns all objects of the current level regardless of whether their bounds are within the query.
But it was the basis of my own class which I then heavily redesigned, and in the end…: just wrote new from scratch.

Here it is:
http://pastebin.java-gaming.org/4af3b227b3d1a

Though it does use a Rectangle class :wink: …but hey, we have no dynamic language with Java and don’t even have duck typing, so there has to be some Rectangle/Sizeable/Boundable/… class/interface. :slight_smile:
Also, one likely wants to decouple the “things” that one can insert into a quadtree from the representation of their rectangular bounds, so as not to have to instantiate a “Sizeable” object just to query what other Sizeables are inside the quadtree, i.e. one wants to query by rectangle and not by Sizeable having the properties of a rectangle.

It can freely be used and works fine for me. I currently use it in my own simple OpenStreetMap mapserver when inserting and querying the map objects. In particular it allows to query rectangular areas and have any object inserted into it that has rectangular bounds (i.e. by implementing the “Boundable” interface).

#4

Thanks, your approach does seem to work much better.

I didn’t even see that silly “doesn’t use any rectangle class” of the original post- I’m not sure why that’s a bonus, plus it does use a Sizeable interface, so I’m not sure why OP mentioned it.

#5

There was a tiny bug when determining in which child to distribute/insert an element, which caused the element to be inserted suboptimally into the parent instead. Correct querying was however not affected by this, only the suboptimal insertion of elements causing the parent node to become overful too fast.
It’s fixed with: http://pastebin.java-gaming.org/2bdab7a763e19
Now everything should work as expected.

EDIT: There was a very obvious performance improvement I missed :slight_smile: No need to check all objects of a node individually iff the query rectangle completely contains the node bounds. Also added the possibility to just count the objects selected by the query and not have them added to the “res” list.
All fixed with: http://pastebin.java-gaming.org/bdaba867e391e