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);
107 public void remove(T object, Rectangle2D bounds) {
109 contains.remove(object);
112 boolean pX = bounds.getMinX() > center.getX();
113 boolean nX = bounds.getMaxX() < center.getX();
114 boolean pY = bounds.getMinY() > center.getY();
115 boolean nY = bounds.getMaxY() < center.getY();
119 pXpY.remove(object, bounds);
121 pXnY.remove(object, bounds);
123 pXpY.remove(object, bounds);
124 pXnY.remove(object, bounds);
128 nXpY.remove(object, bounds);
130 nXnY.remove(object, bounds);
132 nXpY.remove(object, bounds);
133 nXnY.remove(object, bounds);
136 pXpY.remove(object, bounds);
137 nXpY.remove(object, bounds);
139 pXnY.remove(object, bounds);
140 nXnY.remove(object, bounds);
142 pXpY.remove(object, bounds);
143 pXnY.remove(object, bounds);
144 nXpY.remove(object, bounds);
145 nXnY.remove(object, bounds);
151 public boolean contains(T object) {
153 return contains.contains(object);
155 return pXnY.contains(object) || pXpY.contains(object) || nXnY.contains(object) || nXpY.contains(object);
161 * Returns objects within the given area.
165 public void get(Rectangle2D bounds, Set<T> set) {
167 set.addAll(contains);
170 boolean pX = bounds.getMinX() > center.getX();
171 boolean nX = bounds.getMaxX() < center.getX();
172 boolean pY = bounds.getMinY() > center.getY();
173 boolean nY = bounds.getMaxY() < center.getY();
177 pXpY.get(bounds, set);
179 pXnY.get(bounds, set);
181 pXpY.get(bounds, set);
182 pXnY.get(bounds, set);
186 nXpY.get(bounds, set);
188 nXnY.get(bounds, set);
190 nXpY.get(bounds, set);
191 nXnY.get(bounds, set);
194 pXpY.get(bounds, set);
195 nXpY.get(bounds, set);
197 pXnY.get(bounds, set);
198 nXnY.get(bounds, set);
200 pXpY.get(bounds, set);
201 pXnY.get(bounds, set);
202 nXpY.get(bounds, set);
203 nXnY.get(bounds, set);
209 public void clear() {
220 private void split(int depth) {
222 throw new IllegalStateException("Node is already split");
225 this.contains = new HashSet<>();
236 private void split() {
237 double w = width * 0.5;
238 double h = height * 0.5;
239 double wd2 = w * 0.5;
240 double hd2 = h * 0.5;
241 pXpY = new QuadTree<T>(new Point2D.Double(center.getX()+wd2, center.getY()+hd2), w, h);
242 nXpY = new QuadTree<T>(new Point2D.Double(center.getX()-wd2, center.getY()+hd2), w, h);
243 pXnY = new QuadTree<T>(new Point2D.Double(center.getX()+wd2, center.getY()-hd2), w, h);
244 nXnY = new QuadTree<T>(new Point2D.Double(center.getX()-wd2, center.getY()-hd2), w, h);