SHARE
TWEET

QuadTree

a guest Feb 3rd, 2019 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package _01QuadTree;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.List;
  5.  
  6. import static _01QuadTree.Node.MAX_ITEM_COUNT;
  7.  
  8. public class QuadTree<T extends Boundable> {
  9.  
  10.     public static final int DEFAULT_MAX_DEPTH = 5;
  11.  
  12.     private int maxDepth;
  13.  
  14.     private Node<T> root;
  15.  
  16.     private Rectangle bounds;
  17.  
  18.     private int count;
  19.  
  20.     public QuadTree(int width, int height) {
  21.         this(width, height, DEFAULT_MAX_DEPTH);
  22.     }
  23.  
  24.     public QuadTree(int width, int height, int maxDepth) {
  25.         this.root = new Node<>(0, 0, width, height);
  26.         this.bounds = this.root.getBounds();
  27.         this.maxDepth = maxDepth;
  28.     }
  29.  
  30.     public Rectangle getBounds() {
  31.         return this.bounds;
  32.     }
  33.  
  34.     private void setBounds(Rectangle bounds) {
  35.         this.bounds = bounds;
  36.     }
  37.  
  38.     public int getCount() {
  39.         return this.count;
  40.     }
  41.  
  42.     private void setCount(int count) {
  43.         this.count = count;
  44.     }
  45.  
  46.     public boolean insert(T item) {
  47.         return this.insert(item, 1);
  48.     }
  49.  
  50.     private boolean insert(T item, int depth) {
  51.  
  52.         if (!item.getBounds().isInside(this.bounds)) {
  53.             return false;
  54.         }
  55.  
  56.         Node<T> current = this.root;
  57.  
  58.         while (current.getChildren() != null) {
  59.             int quadrant = getQuadrant(current, item.getBounds());
  60.  
  61.             try {
  62.                 current = current.getChildren()[quadrant];
  63.                 depth++;
  64.             } catch (IndexOutOfBoundsException iob) {
  65.                 break;
  66.             }
  67.         }
  68.  
  69.         current.getItems().add(item);
  70.  
  71.         split(current, depth);
  72.  
  73.         this.count++;
  74.  
  75.         return true;
  76.     }
  77.  
  78.     public List<T> report(Rectangle bounds) {
  79.  
  80.         List<T> collisions = new ArrayList<>();
  81.  
  82.         getCollisions(this.root, bounds, collisions);
  83.  
  84.         return collisions;
  85.     }
  86.  
  87.     private void getCollisions(Node<T> node, Rectangle bounds,
  88.                                List<T> collisions) {
  89.  
  90.         int quadrant = getQuadrant(node, bounds);
  91.  
  92.         if (quadrant == -1) {
  93.             //bounds doesnt fit in quadrant
  94.             //check all items in node children for intersection
  95.             //add all node items and children intersections
  96.             getSubtreeElements(node, bounds, collisions);
  97.             return;
  98.         }
  99.  
  100.         if (node.getChildren() != null) {
  101.             getCollisions(node.getChildren()[quadrant],
  102.                     bounds, collisions);
  103.         }
  104.  
  105.         collisions.addAll(node.getItems());
  106.     }
  107.  
  108.     private void getSubtreeElements(Node<T> node, Rectangle bounds,
  109.                                     List<T> collisions) {
  110.  
  111.         if (node.getChildren() != null) {
  112.             for (Node<T> child : node.getChildren()) {
  113.                 if (child.getBounds().intersects(bounds)) {
  114.                     getSubtreeElements(child, bounds,
  115.                             collisions);
  116.                 }
  117.             }
  118.         }
  119.  
  120.         collisions.addAll(node.getItems());
  121.     }
  122.  
  123.     private int getQuadrant(Node<T> node, Rectangle bounds) {
  124.  
  125.         Node<T>[] nodeChildren = node.getChildren();
  126.  
  127.         if (nodeChildren != null) {
  128.  
  129.             for (int quadrant = 0; quadrant < MAX_ITEM_COUNT; quadrant++) {
  130.  
  131.                 if (bounds.isInside(nodeChildren[quadrant].getBounds())) {
  132.                     return quadrant;
  133.                 }
  134.             }
  135.         }
  136.  
  137.         return -1;
  138.     }
  139.  
  140.     private void split(Node<T> node, int depth) {
  141.  
  142.         if (!node.shouldSplit()
  143.                 || depth >= this.maxDepth) {
  144.             return;
  145.         }
  146.  
  147.         Rectangle nodeBounds = node.getBounds();
  148.  
  149.         int leftWidth = nodeBounds.getWidth() / 2;
  150.         int rightWidth = nodeBounds.getWidth() - leftWidth;
  151.         int topHeight = nodeBounds.getHeight() / 2;
  152.         int bottomHeight = nodeBounds.getHeight() - topHeight;
  153.  
  154.         int horMidpoint = nodeBounds.getMidX();
  155.         int verMidpoint = nodeBounds.getMidY();
  156.  
  157.         int boundsX1 = nodeBounds.getX1();
  158.         int boundsY1 = nodeBounds.getY1();
  159.  
  160.         node.setChildren(new Node[4]);
  161.  
  162.         // x is horizontal axis
  163.         // x0,y0 is top left corner
  164.         // topLeft = 1, topRight = 0
  165.         // bottomLeft = 2; bottomRight = 3
  166.         node.getChildren()[0] = new Node<>(horMidpoint,
  167.                 boundsY1, rightWidth, topHeight);
  168.         node.getChildren()[1] = new Node<>(boundsX1,
  169.                 boundsY1, leftWidth, topHeight);
  170.         node.getChildren()[2] = new Node<>(boundsX1,
  171.                 verMidpoint, leftWidth, bottomHeight);
  172.         node.getChildren()[3] = new Node<>(horMidpoint,
  173.                 verMidpoint, rightWidth, bottomHeight);
  174.  
  175.         for (int i = 0; i < node.getItems().size(); i++) {
  176.  
  177.             T item = node.getItems().get(i);
  178.             int quadrant = getQuadrant(node, item.getBounds());
  179.  
  180.             if (quadrant != -1) {
  181.                 node.getItems().remove(i--);
  182.  
  183.                 node.getChildren()[quadrant]
  184.                         .getItems()
  185.                         .add(item);
  186.             }
  187.         }
  188.  
  189.         for (Node<T> child : node.getChildren()) {
  190.             split(child, depth + 1);
  191.         }
  192.     }
  193. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top