bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/collections/QuadTree.java

   1 package org.simantics.utils.datastructures.collections;
   2
   3 import java.awt.geom.Point2D;
   4 import java.awt.geom.Rectangle2D;
   5 import java.util.HashSet;
   6 import java.util.Set;
   7
   8 public class QuadTree<T> {
   9
  10         Point2D center;
  11         Set<T> contains;
  12         double width;
  13         double height;
  14
  15         boolean leaf;
  16         QuadTree<T> pXpY;
  17         QuadTree<T> nXpY;
  18         QuadTree<T> pXnY;
  19         QuadTree<T> nXnY;
  20
  21         /**
  22          * Creates a quadtree
  23          * @param center center of the quadtree area
  24          * @param width width of the area
  25          * @param height height of the area
  26          * @param depth depth of the tree structure.
  27          */
  28         public QuadTree(Point2D center, double width, double height, int depth) {
  29                 this.center = center;
  30                 this.width = width;
  31                 this.height = height;
  32                 this.leaf = true;
  33                 split(depth);
  34         }
  35
  36         private QuadTree(Point2D center, double width, double height) {
  37                 this.center = center;
  38                 this.width = width;
  39                 this.height = height;
  40                 this.leaf = true;
  41         }
  42
  43         /**
  44          * Insets an object into the tree
  45          * @param object
  46          * @param bounds
  47          */
  48         public void insert(T object, Rectangle2D bounds) {
  49                 if (leaf) {
  50                         contains.add(object);
  51                 } else {
  52
  53                         boolean pX = bounds.getMinX() > center.getX();
  54                         boolean nX = bounds.getMaxX() < center.getX();
  55                         boolean pY = bounds.getMinY() > center.getY();
  56                         boolean nY = bounds.getMaxY() < center.getY();
  57
  58                         if (pX) {
  59                                 if (pY) {
  60                                         pXpY.insert(object, bounds);
  61                                 } else if (nY) {
  62                                         pXnY.insert(object, bounds);
  63                                 } else {
  64                                         pXpY.insert(object, bounds);
  65                                         pXnY.insert(object, bounds);
  66                                 }
  67                         } else if (nX) {
  68                                 if (pY) {
  69                                         nXpY.insert(object, bounds);
  70                                 } else if (nY) {
  71                                         nXnY.insert(object, bounds);
  72                                 } else {
  73                                         nXpY.insert(object, bounds);
  74                                         nXnY.insert(object, bounds);
  75                                 }
  76                         } else if (pY) {
  77                                 pXpY.insert(object, bounds);
  78                                 nXpY.insert(object, bounds);
  79                         } else if (nY) {
  80                                 pXnY.insert(object, bounds);
  81                                 nXnY.insert(object, bounds);
  82                         } else {
  83                                 pXpY.insert(object, bounds);
  84                                 pXnY.insert(object, bounds);
  85                                 nXpY.insert(object, bounds);
  86                                 nXnY.insert(object, bounds);
  87                         }
  88
  89                 }
  90         }
  91
  92         /**
  93          * Removes an object from the tree
  94          * @param object
  95          */
  96         public void remove(T object) {
  97                 if (leaf) {
  98                         contains.remove(object);
  99                 } else {
 100                         pXpY.remove(object);
 101                         pXnY.remove(object);
 102                         nXpY.remove(object);
 103                         nXnY.remove(object);
 104                 }
 105         }
 106
 107         public boolean contains(T object) {
 108                 if (leaf) {
 109                         return contains.contains(object);
 110                 } else {
 111                         return pXnY.contains(object) || pXpY.contains(object) || nXnY.contains(object) || nXpY.contains(object);
 112                 }
 113
 114         }
 115
 116         /**
 117          * Returns objects within the given area.
 118          * @param bounds
 119          * @param set
 120          */
 121         public void get(Rectangle2D bounds, Set<T> set) {
 122                 if (leaf) {
 123                         set.addAll(contains);
 124                 } else {
 125
 126                         boolean pX = bounds.getMinX() > center.getX();
 127                         boolean nX = bounds.getMaxX() < center.getX();
 128                         boolean pY = bounds.getMinY() > center.getY();
 129                         boolean nY = bounds.getMaxY() < center.getY();
 130
 131                         if (pX) {
 132                                 if (pY) {
 133                                         pXpY.get(bounds, set);
 134                                 } else if (nY) {
 135                                         pXnY.get(bounds, set);
 136                                 } else {
 137                                         pXpY.get(bounds, set);
 138                                         pXnY.get(bounds, set);
 139                                 }
 140                         } else if (nX) {
 141                                 if (pY) {
 142                                         nXpY.get(bounds, set);
 143                                 } else if (nY) {
 144                                         nXnY.get(bounds, set);
 145                                 } else {
 146                                         nXpY.get(bounds, set);
 147                                         nXnY.get(bounds, set);
 148                                 }
 149                         } else if (pY) {
 150                                 pXpY.get(bounds, set);
 151                                 nXpY.get(bounds, set);
 152                         } else if (nY) {
 153                                 pXnY.get(bounds, set);
 154                                 nXnY.get(bounds, set);
 155                         } else {
 156                                 pXpY.get(bounds, set);
 157                                 pXnY.get(bounds, set);
 158                                 nXpY.get(bounds, set);
 159                                 nXnY.get(bounds, set);
 160                         }
 161
 162                 }
 163         }
 164
 165         public void clear() {
 166                 if (leaf) {
 167                         contains.clear();
 168                 } else {
 169                         pXpY.clear();
 170                         pXnY.clear();
 171                         nXpY.clear();
 172                         nXnY.clear();
 173                 }
 174         }
 175
 176         private void split(int depth) {
 177                 if (!leaf) {
 178                         throw new IllegalStateException("Node is already split");
 179                 }
 180                 if (depth <= 0) {
 181                         this.contains = new HashSet<>();
 182                         return;
 183                 }
 184                 split();
 185                 depth--;
 186                 pXpY.split(depth);
 187                 nXpY.split(depth);
 188                 pXnY.split(depth);
 189                 nXnY.split(depth);
 190         }
 191
 192         private void split() {
 193                 double w = width * 0.5;
 194                 double h = height * 0.5;
 195                 double wd2 = w * 0.5;
 196                 double hd2 = h * 0.5;
 197                 pXpY = new QuadTree<T>(new Point2D.Double(center.getX()+wd2, center.getY()+hd2), w, h);
 198                 nXpY = new QuadTree<T>(new Point2D.Double(center.getX()-wd2, center.getY()+hd2), w, h);
 199                 pXnY = new QuadTree<T>(new Point2D.Double(center.getX()+wd2, center.getY()-hd2), w, h);
 200                 nXnY = new QuadTree<T>(new Point2D.Double(center.getX()-wd2, center.getY()-hd2), w, h);
 201                 leaf = false;
 202         }
 203
 204
 205 }