This is my first Quadtree implementation and I’m not too impressed with it 
I started out because I wanted to speed up my Boids application (http://www.red3d.com/cwr/boids/).
- Boids move around
- Boids adapt their movement based on their closest neigbours
Without any form of spatial organisation I had a O(n^2) complexity for each update
Enter the StaticQuadtree…
My StaticQuadtree generates all lower levels of the tree on instantiation.
A StaticQuadtree with 1 level is basically the same as my original Vector.
After some performance tests I noticed that generating more than 5 levels starts to decrease performance. Especially when removing Boids from the Quadtree when they move and when searching in an area that contains several sub levels.
Is that a normal number of levels for a Quadtree, or can this code be improved by multitudes after a few simple optimizations? 
Also, am I correct in asuming that I have to remove and re-add all boids during update?
Wouldn’t it be easier (quicker even) to regenerate the Quadtree before each update?
My first implementation:
import java.util.Collection;
import java.util.Vector;
public class StaticQuadtree implements Quadtree {
private final static int DEFAULT_LEVELS = 5;
private final Collection<Entity> entities = new Vector<Entity>();
private final Node head;
public StaticQuadtree() {
this(DEFAULT_LEVELS);
}
public StaticQuadtree(int levels) {
if (levels < 0) throw new IllegalArgumentException();
head = new Node(levels, new BoundingBox(-256, -256, 256, 256));
}
@Override
public synchronized int size() {
return entities.size();
}
@Override
public synchronized Collection<Entity> get() {
return new Vector<Entity>(entities);
}
@Override
public synchronized void get(BoundingBox bb, Collection<Entity> result) {
head.get(bb, result);
}
@Override
public synchronized void add(Entity entity) {
if (entities.contains(entity)) throw new RuntimeException();
entities.add(entity);
head.add(entity);
}
@Override
public synchronized void remove(Entity entity) {
if (!entities.contains(entity)) throw new RuntimeException();
entities.remove(entity);
head.remove(entity);
}
@Override
public String toString() {
return "[QT "+ head +"]";
}
private final class Node {
private final int level;
private final BoundingBox bb;
private final Collection<Entity> entities;
private final Node minmin, minmax, maxmin, maxmax;
public Node(final int level, BoundingBox bb) {
if (level < 0) throw new IllegalArgumentException();
this.level = level;
this.bb = bb;
if (level > 0) {
entities = null;
final double dx = (bb.maxX - bb.minX)/2;
final double dy = (bb.maxY - bb.minY)/2;
minmin = new Node(level-1, new BoundingBox(bb.minX, bb.minY, bb.maxX-dx, bb.maxY-dy));
minmax = new Node(level-1, new BoundingBox(bb.minX, bb.minY+dy, bb.maxX-dx, bb.maxY));
maxmin = new Node(level-1, new BoundingBox(bb.minX+dx, bb.minY, bb.maxX, bb.maxY-dy));
maxmax = new Node(level-1, new BoundingBox(bb.minX+dx, bb.minY+dy, bb.maxX, bb.maxY));
} else {
entities = new Vector<Entity>();
minmin = null;
minmax = null;
maxmin = null;
maxmax = null;
}
}
public synchronized int size() {
if (level == 0) {
return entities.size();
}
int sum = 0;
sum += minmin.size();
sum += minmax.size();
sum += maxmin.size();
sum += maxmax.size();
return sum;
}
public synchronized void get(Collection<Entity> result) {
if (level == 0) {
result.addAll(entities);
} else {
minmin.get(result);
minmax.get(result);
maxmin.get(result);
maxmax.get(result);
}
}
public synchronized void get(BoundingBox bb, Collection<Entity> result) {
if (!this.bb.intersects(bb)) throw new RuntimeException();
if (level == 0) {
for (Entity entity : entities) {
if (bb.contains(entity.pos)) {
result.add(entity);
}
}
} else {
if (minmin.bb.intersects(bb)) minmin.get(bb, result);
if (minmax.bb.intersects(bb)) minmax.get(bb, result);
if (maxmin.bb.intersects(bb)) maxmin.get(bb, result);
if (maxmax.bb.intersects(bb)) maxmax.get(bb, result);
}
}
public synchronized void add(Entity entity) {
if (!this.bb.contains(entity.pos)) throw new RuntimeException();
if (level == 0) {
entities.add(entity);
} else {
if (minmin.bb.contains(entity.pos)) minmin.add(entity);
if (minmax.bb.contains(entity.pos)) minmax.add(entity);
if (maxmin.bb.contains(entity.pos)) maxmin.add(entity);
if (maxmax.bb.contains(entity.pos)) maxmax.add(entity);
}
}
public synchronized void remove(Entity entity) {
if (!this.bb.contains(entity.pos)) throw new RuntimeException();
if (level == 0) {
entities.remove(entity);
} else {
if (minmin.bb.contains(entity.pos)) minmin.remove(entity);
if (minmax.bb.contains(entity.pos)) minmax.remove(entity);
if (maxmin.bb.contains(entity.pos)) maxmin.remove(entity);
if (maxmax.bb.contains(entity.pos)) maxmax.remove(entity);
}
}
@Override
public String toString() {
StringBuffer sb = new StringBuffer();
if (entities != null) sb.append(entities);
if (minmin != null) sb.append(minmin);
if (minmax != null) sb.append(minmax);
if (maxmin != null) sb.append(maxmin);
if (maxmax != null) sb.append(maxmax);
return "[Node "+ sb.toString() +"]";
}
}
}
final class Entity {
public Point pos;
public Point vel;
public Entity(double x, double y) {
this.pos = new Point(x, y);
this.vel = new Point(0, 0);
}
@Override
public String toString() {
return "[Entity "+ pos.x +":"+ pos.y +"]";
}
}
final class Point {
public final double x, y;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
}
final class BoundingBox {
public final double minX, minY;
public final double maxX, maxY;
public BoundingBox(double minX, double minY, double maxX, double maxY) {
if (minX >= maxX) throw new IllegalArgumentException();
if (minY >= maxY) throw new IllegalArgumentException();
this.minX = minX;
this.minY = minY;
this.maxX = maxX;
this.maxY = maxY;
}
public boolean contains(double x, double y) {
return (minX < x && x <= maxX &&
minY < y && y <= maxY);
}
public boolean contains(Point that) {
return contains(that.x, that.y);
}
public boolean intersects(BoundingBox that) {
return (minX < that.maxX && that.minX <= maxX &&
minY < that.maxY && that.minY <= maxY);
}
}
Stay tuned for my DynamicQuadtree update…