Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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());
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement