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 boolean contains(T object) {
109 return contains.contains(object);
111 return pXnY.contains(object) || pXpY.contains(object) || nXnY.contains(object) || nXpY.contains(object);
117 * Returns objects within the given area.
121 public void get(Rectangle2D bounds, Set<T> set) {
123 set.addAll(contains);
126 boolean pX = bounds.getMinX() > center.getX();
127 boolean nX = bounds.getMaxX() < center.getX();
128 boolean pY = bounds.getMinY() > center.getY();
129 boolean nY = bounds.getMaxY() < center.getY();
133 pXpY.get(bounds, set);
135 pXnY.get(bounds, set);
137 pXpY.get(bounds, set);
138 pXnY.get(bounds, set);
142 nXpY.get(bounds, set);
144 nXnY.get(bounds, set);
146 nXpY.get(bounds, set);
147 nXnY.get(bounds, set);
150 pXpY.get(bounds, set);
151 nXpY.get(bounds, set);
153 pXnY.get(bounds, set);
154 nXnY.get(bounds, set);
156 pXpY.get(bounds, set);
157 pXnY.get(bounds, set);
158 nXpY.get(bounds, set);
159 nXnY.get(bounds, set);
165 public void clear() {
176 private void split(int depth) {
178 throw new IllegalStateException("Node is already split");
181 this.contains = new HashSet<>();
192 private void split() {
193 double w = width * 0.5;
194 double h = height * 0.5;
195 double wd2 = w * 0.5;
196 double hd2 = h * 0.5;
197 pXpY = new QuadTree<T>(new Point2D.Double(center.getX()+wd2, center.getY()+hd2), w, h);
198 nXpY = new QuadTree<T>(new Point2D.Double(center.getX()-wd2, center.getY()+hd2), w, h);
199 pXnY = new QuadTree<T>(new Point2D.Double(center.getX()+wd2, center.getY()-hd2), w, h);
200 nXnY = new QuadTree<T>(new Point2D.Double(center.getX()-wd2, center.getY()-hd2), w, h);