Migrated source code from Simantics SVN

[simantics/platform.git] / bundles / org.simantics.utils.datastructures / src / org / simantics / utils / datastructures / collections / QuadTree.java

diff --git a/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/collections/QuadTree.java b/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/collections/QuadTree.java
new file mode 100644 (file)
index 0000000..b3fae46
--- /dev/null
+++ b/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/collections/QuadTree.java
@@ -0,0 +1,196 @@
+package org.simantics.utils.datastructures.collections;\r
+\r
+import java.awt.geom.Point2D;\r
+import java.awt.geom.Rectangle2D;\r
+import java.util.HashSet;\r
+import java.util.Set;\r
+\r
+public class QuadTree<T> {\r
+       \r
+       Point2D center;\r
+       Set<T> contains;\r
+       double width;\r
+       double height;\r
+       \r
+       boolean leaf;\r
+       QuadTree<T> pXpY;\r
+       QuadTree<T> nXpY;\r
+       QuadTree<T> pXnY;\r
+       QuadTree<T> nXnY;\r
+       \r
+       /**\r
+        * Creates a quadtree\r
+        * @param center center of the quadtree area\r
+        * @param width width of the area\r
+        * @param height height of the area\r
+        * @param depth depth of the tree structure. \r
+        */\r
+       public QuadTree(Point2D center, double width, double height, int depth) {\r
+               this.center = center;\r
+               this.width = width;\r
+               this.height = height;\r
+               this.leaf = true;\r
+               split(depth);\r
+       }\r
+       \r
+       private QuadTree(Point2D center, double width, double height) {\r
+               this.center = center;\r
+               this.width = width;\r
+               this.height = height;\r
+               this.leaf = true;\r
+       }\r
+       \r
+       /**\r
+        * Insets an object into the tree\r
+        * @param object\r
+        * @param bounds\r
+        */\r
+       public void insert(T object, Rectangle2D bounds) {\r
+               if (leaf) {\r
+                       contains.add(object);\r
+               } else {\r
+                       \r
+                       boolean pX = bounds.getMinX() > center.getX();\r
+                       boolean nX = bounds.getMaxX() < center.getX();\r
+                       boolean pY = bounds.getMinY() > center.getY();\r
+                       boolean nY = bounds.getMaxY() < center.getY();\r
+                       \r
+                       if (pX) {\r
+                               if (pY) {\r
+                                       pXpY.insert(object, bounds);\r
+                               } else if (nY) {\r
+                                       pXnY.insert(object, bounds);\r
+                               } else {\r
+                                       pXpY.insert(object, bounds);\r
+                                       pXnY.insert(object, bounds);\r
+                               }\r
+                       } else if (nX) {\r
+                               if (pY) {\r
+                                       nXpY.insert(object, bounds);\r
+                               } else if (nY) {\r
+                                       nXnY.insert(object, bounds);\r
+                               } else {\r
+                                       nXpY.insert(object, bounds);\r
+                                       nXnY.insert(object, bounds);\r
+                               }\r
+                       } else if (pY) {\r
+                               pXpY.insert(object, bounds);\r
+                               nXpY.insert(object, bounds);\r
+                       } else if (nY) {\r
+                               pXnY.insert(object, bounds);\r
+                               nXnY.insert(object, bounds);\r
+                       } else {\r
+                               pXpY.insert(object, bounds);\r
+                               pXnY.insert(object, bounds);\r
+                               nXpY.insert(object, bounds);\r
+                               nXnY.insert(object, bounds);\r
+                       }\r
+                       \r
+               }\r
+       }\r
+       \r
+       /**\r
+        * Removes an object from the tree\r
+        * @param object\r
+        */\r
+       public void remove(T object) {\r
+               if (leaf) {\r
+                       contains.remove(object);\r
+               } else {\r
+                       pXpY.remove(object);\r
+                       pXnY.remove(object);\r
+                       nXpY.remove(object);\r
+                       nXnY.remove(object);\r
+               }\r
+       }\r
+       \r
+       /**\r
+        * Returns objects within the given area.\r
+        * @param bounds\r
+        * @param set\r
+        */\r
+       public void get(Rectangle2D bounds, Set<T> set) {\r
+               if (leaf) {\r
+                       set.addAll(contains);\r
+               } else {\r
+                       \r
+                       boolean pX = bounds.getMinX() > center.getX();\r
+                       boolean nX = bounds.getMaxX() < center.getX();\r
+                       boolean pY = bounds.getMinY() > center.getY();\r
+                       boolean nY = bounds.getMaxY() < center.getY();\r
+                       \r
+                       if (pX) {\r
+                               if (pY) {\r
+                                       pXpY.get(bounds, set);\r
+                               } else if (nY) {\r
+                                       pXnY.get(bounds, set);\r
+                               } else {\r
+                                       pXpY.get(bounds, set);\r
+                                       pXnY.get(bounds, set);\r
+                               }\r
+                       } else if (nX) {\r
+                               if (pY) {\r
+                                       nXpY.get(bounds, set);\r
+                               } else if (nY) {\r
+                                       nXnY.get(bounds, set);\r
+                               } else {\r
+                                       nXpY.get(bounds, set);\r
+                                       nXnY.get(bounds, set);\r
+                               }\r
+                       } else if (pY) {\r
+                               pXpY.get(bounds, set);\r
+                               nXpY.get(bounds, set);\r
+                       } else if (nY) {\r
+                               pXnY.get(bounds, set);\r
+                               nXnY.get(bounds, set);\r
+                       } else {\r
+                               pXpY.get(bounds, set);\r
+                               pXnY.get(bounds, set);\r
+                               nXpY.get(bounds, set);\r
+                               nXnY.get(bounds, set);\r
+                       }\r
+                       \r
+               }\r
+       }\r
+       \r
+       public void clear() {\r
+               if (leaf) {\r
+                       contains.clear();\r
+               } else {\r
+                       pXpY.clear();\r
+                       pXnY.clear();\r
+                       nXpY.clear();\r
+                       nXnY.clear();\r
+               }\r
+       }\r
+       \r
+       private void split(int depth) {\r
+               if (!leaf) {\r
+                       throw new IllegalStateException("Node is already split");\r
+               }\r
+               if (depth <= 0) {\r
+                       this.contains = new HashSet<>();\r
+                       return;\r
+               }\r
+               split();\r
+               depth--;\r
+               pXpY.split(depth);\r
+               nXpY.split(depth);\r
+               pXnY.split(depth);\r
+               nXnY.split(depth);\r
+       }\r
+       \r
+       private void split() {\r
+               double w = width * 0.5;\r
+               double h = height * 0.5;\r
+               double wd2 = w * 0.5;\r
+               double hd2 = h * 0.5;\r
+               pXpY = new QuadTree<T>(new Point2D.Double(center.getX()+wd2, center.getY()+hd2), w, h);\r
+               nXpY = new QuadTree<T>(new Point2D.Double(center.getX()-wd2, center.getY()+hd2), w, h);\r
+               pXnY = new QuadTree<T>(new Point2D.Double(center.getX()+wd2, center.getY()-hd2), w, h);\r
+               nXnY = new QuadTree<T>(new Point2D.Double(center.getX()-wd2, center.getY()-hd2), w, h);\r
+               leaf = false;\r
+       }\r
+       \r
+\r
+}\r