Advertisement
Guest User

Untitled

a guest
Jul 13th, 2012
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.96 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement