1 package org.djutils.quadtree;
2
3 import static org.junit.Assert.assertEquals;
4 import static org.junit.Assert.assertFalse;
5 import static org.junit.Assert.assertTrue;
6
7 import java.awt.geom.Point2D;
8 import java.util.Arrays;
9 import java.util.Iterator;
10
11 import org.junit.Test;
12
13
14
15
16
17
18
19
20
21
22
23 public class QuadTreeTests
24 {
25
26
27
28
29 @Test
30 public void testBasics()
31 {
32 QuadTree<Bounded> qt = new QuadTree<>(10, 10.0, 0, 0, 100, 100);
33 assertTrue("The toString method returns something descriptive", qt.toString().startsWith("QuadTree"));
34
35 assertEquals("quad tree is empty", 0, qt.size());
36 assertTrue("quad tree is empty", qt.isEmpty());
37 Bounded[] b = new Bounded[324];
38 for (int i = 0; i < b.length; i++)
39 {
40 double cX = (i * 5) % 90 + 7;
41 double cY = i / 18 * 5 + 6;
42 Point2D.Double[] points = new Point2D.Double[5];
43 points[0] = new Point2D.Double(cX - 6, cY);
44 points[1] = new Point2D.Double(cX - 4, cY + 4);
45 points[2] = new Point2D.Double(cX, cY + 6);
46 points[3] = new Point2D.Double(cX + 4, cY + 4);
47 points[4] = new Point2D.Double(cX, cY + 6);
48 b[i] = new Bounded(points, "Test object " + i);
49
50 assertFalse("shape is not yet in quad tree", qt.contains(b[i]));
51 assertTrue("adding the shape modifies the quad tree", qt.add(b[i]));
52 assertEquals("quad tree now contains one more item", i + 1, qt.size());
53 if (!qt.contains(b[i]))
54 {
55 qt.contains(b[i]);
56 }
57 assertTrue("shape was added", qt.contains(b[i]));
58 assertFalse("quad tree is not empty", qt.isEmpty());
59 }
60 for (int i = 0; i < b.length; i++)
61 {
62 assertTrue("shape is in the quad tree", qt.contains(b[i]));
63 assertFalse("Adding shape " + i + " again does not modify the quad tree", qt.add(b[i]));
64 }
65 assertEquals("quad tree contains the expected number of shapes", b.length, qt.size());
66
67
68 boolean[] seen = new boolean[b.length];
69 int totalSeen = 0;
70 for (Bounded bounded : qt)
71 {
72 for (int i = 0; i < b.length; i++)
73 {
74 if (bounded.equals(b[i]))
75 {
76 assertFalse("each one is returned only once", seen[i]);
77 seen[i] = true;
78 totalSeen++;
79 }
80 }
81 }
82 assertEquals("all elements have been returned", b.length, totalSeen);
83 for (int i = 0; i < b.length; i++)
84 {
85 assertFalse("Element can not be added again", qt.add(b[i]));
86 }
87 assertEquals("quad tree contains the expected number of shapes", b.length, qt.size());
88
89 for (int i = -10; i < 100; i++)
90 {
91 for (int j = -10; j < 100; j++)
92 {
93 seen = new boolean[b.length];
94 Rectangle area = new Rectangle(i, j, i + 20, j + 20);
95 Iterator<Bounded> iterator = qt.iterator(area);
96
97 while (iterator.hasNext())
98 {
99 Bounded bounded = iterator.next();
100
101 for (int k = 0; k < b.length; k++)
102 {
103 if (bounded.equals(b[k]))
104 {
105 assertFalse("each one is returned only once", seen[k]);
106 seen[k] = true;
107 }
108 }
109 }
110
111 for (int k = 0; k < b.length; k++)
112 {
113 if (b[k].intersects(area))
114 {
115 assertTrue("Intersecting object was found", seen[k]);
116 }
117 }
118 }
119 }
120
121 for (int i = 0; i < b.length; i++)
122 {
123 assertTrue("quad tree changes on removal of object", qt.remove(b[i]));
124 assertEquals("size of quad tree is now one less", b.length - i - 1, qt.size());
125 assertFalse("shape is no longer in quad tree", qt.contains(b[i]));
126 }
127 assertEquals("quad tree is empty when all shapes have been removed", 0, qt.size());
128 assertTrue("quad tree is empty", qt.isEmpty());
129 }
130
131 }
132
133
134
135
136 class Bounded implements Envelope
137 {
138
139 private final Point2D.Double[] points;
140
141
142 private final Rectangle boundingRectangle;
143
144
145 private final String id;
146
147
148
149
150
151
152 Bounded(final Point2D.Double[] points, final String id)
153 {
154 this.points = points;
155 double left = java.lang.Double.MAX_VALUE;
156 double bottom = java.lang.Double.MAX_VALUE;
157 double right = java.lang.Double.MIN_VALUE;
158 double top = java.lang.Double.MIN_VALUE;
159 for (Point2D.Double point : points)
160 {
161 left = Math.min(left, point.x);
162 bottom = Math.min(bottom, point.y);
163 right = Math.max(right, point.x);
164 top = Math.max(top, point.y);
165 }
166 this.boundingRectangle = new Rectangle(left, bottom, right + Math.ulp(right), top + Math.ulp(top));
167 this.id = id;
168 }
169
170
171 @Override
172 public Rectangle getBoundingRectangle()
173 {
174 return this.boundingRectangle;
175 }
176
177
178
179
180
181
182
183 public boolean intersects(final Rectangle rectangle)
184 {
185 for (Point2D.Double point : this.points)
186 {
187 if (rectangle.contains(point.x, point.y))
188 {
189 return true;
190 }
191 }
192 return false;
193 }
194
195
196 @Override
197 public String toString()
198 {
199 return "Bounded [id=" + this.id + ", boundingRectangle=" + this.boundingRectangle + ", points="
200 + Arrays.toString(this.points) + "]";
201 }
202
203 }