+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