import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/**
*
* @author matheusdev
*
*/
public class Quadtree {
private final QuadRect bounds;
private QuadtreeElement[] elements;
private Quadtree topLeft;
private Quadtree topRight;
private Quadtree botLeft;
private Quadtree botRight;
public Quadtree(float size, int elemPerQuad) {
this(0, 0, size, elemPerQuad);
}
public Quadtree(float x, float y, float size, int elemPerQuad) {
bounds = new QuadRect(x, y, size);
elements = new QuadtreeElement[elemPerQuad];
}
protected boolean set(QuadtreeElement e) {
for (int i = 0; i < maxElem(); i++) {
if (elements[i] == null) {
elements[i] = e;
return true;
}
}
return false;
}
public int maxElem() {
return elements.length;
}
public boolean insert(QuadtreeElement e) {
if (!bounds.contains(e.getX(), e.getY())) {
return false;
}
if (set(e)) {
return true;
} else {
subdivide();
if (topRight.insert(e)) return true;
if (topLeft.insert(e)) return true;
if (botRight.insert(e)) return true;
if (botLeft.insert(e)) return true;
throw new ImpossibleException();
}
}
public void query(StaticRect range, List<? super QuadtreeElement> results) {
if (!bounds.intersects(range)) {
return;
}
for (int i = 0; i < maxElem(); i++) {
if (elements[i] != null) {
if (range.contains(elements[i].getX(), elements[i].getY())) {
results.add(elements[i]);
}
}
}
if (!hasChildren()) {
return;
}
topLeft.query(range, results);
topRight.query(range, results);
botLeft.query(range, results);
botRight.query(range, results);
}
public boolean hasChildren() {
return topLeft != null;
}
/**
* <p>
* Subdivides this Quadtree into 4 other quadtrees.
* </p>
* <p>
* This is usually used, when this Quadtree already has an
* Element.
* </p>
* @return whether this Quadtree was subdivided, or didn't subdivide,
* because it was already subdivided.
*/
protected boolean subdivide() {
if (hasChildren()) {
return false;
}
float hs = bounds.s/2;
topLeft = new Quadtree(bounds.x, bounds.y, hs, maxElem());
topRight = new Quadtree(bounds.x+hs, bounds.y, hs, maxElem());
botLeft = new Quadtree(bounds.x, bounds.y+hs, hs, maxElem());
botRight = new Quadtree(bounds.x+hs, bounds.y+hs, hs, maxElem());
return true;
}
public static void main(String[] args) {
// Quadtree memory/performance testing:
final float range = 100;
final int elementsPerQuad = 16;
Quadtree tree = new Quadtree(range, elementsPerQuad);
final Random rand = new Random();
System.out.println("Starting Tree generation and insertion");
final long startTime = System.currentTimeMillis();
for (int i = 0; i < 1000; i++) {
tree.insert(new Elem(rand.nextFloat()*range, rand.nextFloat()*range));
}
System.out.println("Insertion took " + (System.currentTimeMillis() - startTime) + " ms.");
System.out.println("Memory usage: " + memoryInMB() + "mb - " + memoryInBytes() + " bytes.");
ArrayList<Elem> elementList = new ArrayList<Elem>();
System.out.println("Starting query.");
for (int i = 0; i < 100000; i++) {
tree.query(new StaticRect(rand.nextFloat()*100, rand.nextFloat()*100, rand.nextFloat()*100, rand.nextFloat()*100), elementList);
elementList.clear();
}
System.out.println("Finished query.");
}
private static class Elem implements QuadtreeElement {
float x, y;
public Elem(float x, float y) {
this.x = x;
this.y = y;
}
public float getX() {
return x;
}
public float getY() {
return y;
}
}
private static long memoryInMB() {
return memoryInKB()/1024;
}
private static long memoryInKB() {
return (memoryInBytes())/1024;
}
private static long memoryInBytes() {
return (Runtime.getRuntime().totalMemory()-Runtime.getRuntime().freeMemory());
}
}