1 package org.simantics.utils.datastructures.collections;
\r
3 import java.awt.geom.Point2D;
\r
4 import java.awt.geom.Rectangle2D;
\r
5 import java.util.HashSet;
\r
6 import java.util.Set;
\r
8 public class QuadTree<T> {
\r
22 * Creates a quadtree
\r
23 * @param center center of the quadtree area
\r
24 * @param width width of the area
\r
25 * @param height height of the area
\r
26 * @param depth depth of the tree structure.
\r
28 public QuadTree(Point2D center, double width, double height, int depth) {
\r
29 this.center = center;
\r
31 this.height = height;
\r
36 private QuadTree(Point2D center, double width, double height) {
\r
37 this.center = center;
\r
39 this.height = height;
\r
44 * Insets an object into the tree
\r
48 public void insert(T object, Rectangle2D bounds) {
\r
50 contains.add(object);
\r
53 boolean pX = bounds.getMinX() > center.getX();
\r
54 boolean nX = bounds.getMaxX() < center.getX();
\r
55 boolean pY = bounds.getMinY() > center.getY();
\r
56 boolean nY = bounds.getMaxY() < center.getY();
\r
60 pXpY.insert(object, bounds);
\r
62 pXnY.insert(object, bounds);
\r
64 pXpY.insert(object, bounds);
\r
65 pXnY.insert(object, bounds);
\r
69 nXpY.insert(object, bounds);
\r
71 nXnY.insert(object, bounds);
\r
73 nXpY.insert(object, bounds);
\r
74 nXnY.insert(object, bounds);
\r
77 pXpY.insert(object, bounds);
\r
78 nXpY.insert(object, bounds);
\r
80 pXnY.insert(object, bounds);
\r
81 nXnY.insert(object, bounds);
\r
83 pXpY.insert(object, bounds);
\r
84 pXnY.insert(object, bounds);
\r
85 nXpY.insert(object, bounds);
\r
86 nXnY.insert(object, bounds);
\r
93 * Removes an object from the tree
\r
96 public void remove(T object) {
\r
98 contains.remove(object);
\r
100 pXpY.remove(object);
\r
101 pXnY.remove(object);
\r
102 nXpY.remove(object);
\r
103 nXnY.remove(object);
\r
108 * Returns objects within the given area.
\r
112 public void get(Rectangle2D bounds, Set<T> set) {
\r
114 set.addAll(contains);
\r
117 boolean pX = bounds.getMinX() > center.getX();
\r
118 boolean nX = bounds.getMaxX() < center.getX();
\r
119 boolean pY = bounds.getMinY() > center.getY();
\r
120 boolean nY = bounds.getMaxY() < center.getY();
\r
124 pXpY.get(bounds, set);
\r
126 pXnY.get(bounds, set);
\r
128 pXpY.get(bounds, set);
\r
129 pXnY.get(bounds, set);
\r
133 nXpY.get(bounds, set);
\r
135 nXnY.get(bounds, set);
\r
137 nXpY.get(bounds, set);
\r
138 nXnY.get(bounds, set);
\r
141 pXpY.get(bounds, set);
\r
142 nXpY.get(bounds, set);
\r
144 pXnY.get(bounds, set);
\r
145 nXnY.get(bounds, set);
\r
147 pXpY.get(bounds, set);
\r
148 pXnY.get(bounds, set);
\r
149 nXpY.get(bounds, set);
\r
150 nXnY.get(bounds, set);
\r
156 public void clear() {
\r
167 private void split(int depth) {
\r
169 throw new IllegalStateException("Node is already split");
\r
172 this.contains = new HashSet<>();
\r
183 private void split() {
\r
184 double w = width * 0.5;
\r
185 double h = height * 0.5;
\r
186 double wd2 = w * 0.5;
\r
187 double hd2 = h * 0.5;
\r
188 pXpY = new QuadTree<T>(new Point2D.Double(center.getX()+wd2, center.getY()+hd2), w, h);
\r
189 nXpY = new QuadTree<T>(new Point2D.Double(center.getX()-wd2, center.getY()+hd2), w, h);
\r
190 pXnY = new QuadTree<T>(new Point2D.Double(center.getX()+wd2, center.getY()-hd2), w, h);
\r
191 nXnY = new QuadTree<T>(new Point2D.Double(center.getX()-wd2, center.getY()-hd2), w, h);
\r