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