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