This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Jul 13th, 2012  |  syntax: Java  |  size: 3.96 KB  |  views: 21  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import java.util.Random;
  4.  
  5. /**
  6.  *
  7.  * @author matheusdev
  8.  *
  9.  */
  10. public class Quadtree {
  11.        
  12.         private final QuadRect bounds;
  13.         private QuadtreeElement[] elements;
  14.        
  15.         private Quadtree topLeft;
  16.         private Quadtree topRight;
  17.         private Quadtree botLeft;
  18.         private Quadtree botRight;
  19.        
  20.         public Quadtree(float size, int elemPerQuad) {
  21.                 this(0, 0, size, elemPerQuad);
  22.         }
  23.        
  24.         public Quadtree(float x, float y, float size, int elemPerQuad) {
  25.                 bounds = new QuadRect(x, y, size);
  26.                 elements = new QuadtreeElement[elemPerQuad];
  27.         }
  28.        
  29.         protected boolean set(QuadtreeElement e) {
  30.                 for (int i = 0; i < maxElem(); i++) {
  31.                         if (elements[i] == null) {
  32.                                 elements[i] = e;
  33.                                 return true;
  34.                         }
  35.                 }
  36.                 return false;
  37.         }
  38.        
  39.         public int maxElem() {
  40.                 return elements.length;
  41.         }
  42.        
  43.         public boolean insert(QuadtreeElement e) {
  44.                 if (!bounds.contains(e.getX(), e.getY())) {
  45.                         return false;
  46.                 }
  47.                 if (set(e)) {
  48.                         return true;
  49.                 } else {
  50.                         subdivide();
  51.                         if (topRight.insert(e)) return true;
  52.                         if (topLeft.insert(e)) return true;
  53.                         if (botRight.insert(e)) return true;
  54.                         if (botLeft.insert(e)) return true;
  55.                        
  56.                         throw new ImpossibleException();
  57.                 }
  58.         }
  59.        
  60.         public void query(StaticRect range, List<? super QuadtreeElement> results) {
  61.                 if (!bounds.intersects(range)) {
  62.                         return;
  63.                 }
  64.                 for (int i = 0; i < maxElem(); i++) {
  65.                         if (elements[i] != null) {
  66.                                 if (range.contains(elements[i].getX(), elements[i].getY())) {
  67.                                         results.add(elements[i]);
  68.                                 }
  69.                         }
  70.                 }
  71.                 if (!hasChildren()) {
  72.                         return;
  73.                 }
  74.                 topLeft.query(range, results);
  75.                 topRight.query(range, results);
  76.                 botLeft.query(range, results);
  77.                 botRight.query(range, results);
  78.         }
  79.        
  80.         public boolean hasChildren() {
  81.                 return topLeft != null;
  82.         }
  83.        
  84.         /**
  85.          * <p>
  86.          * Subdivides this Quadtree into 4 other quadtrees.
  87.          * </p>
  88.          * <p>
  89.          * This is usually used, when this Quadtree already has an
  90.          * Element.
  91.          * </p>
  92.          * @return whether this Quadtree was subdivided, or didn't subdivide,
  93.          * because it was already subdivided.
  94.          */
  95.         protected boolean subdivide() {
  96.                 if (hasChildren()) {
  97.                         return false;
  98.                 }
  99.                 float hs = bounds.s/2;
  100.                 topLeft = new Quadtree(bounds.x, bounds.y, hs, maxElem());
  101.                 topRight = new Quadtree(bounds.x+hs, bounds.y, hs, maxElem());
  102.                 botLeft = new Quadtree(bounds.x, bounds.y+hs, hs, maxElem());
  103.                 botRight = new Quadtree(bounds.x+hs, bounds.y+hs, hs, maxElem());
  104.                 return true;
  105.         }
  106.        
  107.         public static void main(String[] args) {
  108.                 // Quadtree memory/performance testing:
  109.                 final float range = 100;
  110.                 final int elementsPerQuad = 16;
  111.                 Quadtree tree = new Quadtree(range, elementsPerQuad);
  112.                
  113.                 final Random rand = new Random();
  114.                 System.out.println("Starting Tree generation and insertion");
  115.                 final long startTime = System.currentTimeMillis();
  116.                
  117.                 for (int i = 0; i < 1000; i++) {
  118.                         tree.insert(new Elem(rand.nextFloat()*range, rand.nextFloat()*range));
  119.                 }
  120.                
  121.                 System.out.println("Insertion took " + (System.currentTimeMillis() - startTime) + " ms.");
  122.                 System.out.println("Memory usage: " + memoryInMB() + "mb - " + memoryInBytes() + " bytes.");
  123.  
  124.                 ArrayList<Elem> elementList = new ArrayList<Elem>();
  125.                 System.out.println("Starting query.");
  126.                 for (int i = 0; i < 100000; i++) {
  127.                         tree.query(new StaticRect(rand.nextFloat()*100, rand.nextFloat()*100, rand.nextFloat()*100, rand.nextFloat()*100), elementList);
  128.                         elementList.clear();
  129.                 }
  130.                 System.out.println("Finished query.");
  131.         }
  132.        
  133.         private static class Elem implements QuadtreeElement {
  134.                 float x, y;
  135.                 public Elem(float x, float y) {
  136.                         this.x = x;
  137.                         this.y = y;
  138.                 }
  139.                
  140.                 public float getX() {
  141.                         return x;
  142.                 }
  143.                
  144.                 public float getY() {
  145.                         return y;
  146.                 }
  147.         }
  148.  
  149.        
  150.         private static long memoryInMB() {
  151.                 return memoryInKB()/1024;
  152.         }
  153.        
  154.         private static long memoryInKB() {
  155.                 return (memoryInBytes())/1024;
  156.         }
  157.        
  158.         private static long memoryInBytes() {
  159.                 return (Runtime.getRuntime().totalMemory()-Runtime.getRuntime().freeMemory());
  160.         }
  161.        
  162. }
clone this paste RAW Paste Data