1 package cz.cuni.amis.pogamut.defcon.utils.quadtree;
2
3 import java.util.LinkedList;
4 import java.util.List;
5 import java.util.regex.Matcher;
6 import java.util.regex.Pattern;
7
8 import cz.cuni.amis.pogamut.base3d.worldview.object.Location;
9
10
11
12
13
14
15
16 public class QuadTreeNode {
17 private final QuadTree quadTree;
18 private final double EPSILON = 1d;
19
20 private double x1, x2, y1, y2;
21
22 private QuadTreeNode[] nodes = null;
23 private QuadTreeNode parent;
24 private LinkedList<List<Location>> subList;
25 private Location center;
26 private double inner_side;
27 private boolean label = false;
28 private static final Pattern pattern = Pattern.compile("\n");
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49 public QuadTreeNode(QuadTree quadTree, double x1, double y1, double x2,
50 double y2,
51 QuadTreeNode parent, List<List<Location>> subList) {
52 this.quadTree = quadTree;
53 this.x1 = x1;
54 this.x2 = x2;
55 this.y1 = y1;
56 this.y2 = y2;
57 this.parent = parent;
58 inner_side = (x2 - x1) / 2;
59 center = new Location(x1 + inner_side, y1 + inner_side);
60
61 this.subList = findVerticesFormingIntersectingLines(subList);
62
63 if (inner_side < EPSILON)
64 return;
65
66 subdivide();
67 }
68
69 public final double getX1() {
70 return x1;
71 }
72
73 public final double getX2() {
74 return x2;
75 }
76
77 public final double getY1() {
78 return y1;
79 }
80
81 public final double getY2() {
82 return y2;
83 }
84
85
86
87
88
89 private void subdivide() {
90 if (subList.isEmpty())
91 return;
92
93 if (RectangularFillTester.isSameRectangle(
94 subList.getFirst(),
95 x1,
96 y1,
97 x2,
98 y2))
99 return;
100
101 nodes = new QuadTreeNode[4];
102
103 nodes[0] = new QuadTreeNode(
104 this.quadTree,
105 x1,
106 y1,
107 x1 + inner_side,
108 y1 + inner_side,
109 this,
110 subList);
111 nodes[1] = new QuadTreeNode(
112 this.quadTree,
113 x1 + inner_side,
114 y1,
115 x2,
116 y1 + inner_side,
117 this,
118 subList);
119 nodes[2] = new QuadTreeNode(
120 this.quadTree,
121 x1,
122 y1 + inner_side,
123 x1 + inner_side,
124 y2,
125 this,
126 subList);
127 nodes[3] = new QuadTreeNode(
128 this.quadTree,
129 x1 + inner_side,
130 y1 + inner_side,
131 x2,
132 y2,
133 this,
134 subList);
135 }
136
137
138
139
140
141
142
143
144
145 private LinkedList<List<Location>> findVerticesFormingIntersectingLines(
146 List<List<Location>> sections) {
147
148 LinkedList<List<Location>> filteredVertices =
149 new LinkedList<List<Location>>();
150
151 if (sections.isEmpty())
152 return filteredVertices;
153
154 LinkedList<Location> current = new LinkedList<Location>();
155
156 for (List<Location> vertices : sections) {
157 Location last = null;
158
159 for (Location vertex : vertices) {
160
161 if (last == null) {
162 last = vertex;
163 continue;
164 }
165
166 if (lineIntersectsRectangle(last.getX(), last.getY(),
167 vertex.getX(), vertex.getY(),
168 x1, y1, x2, y2)) {
169 if (current.isEmpty()
170 || current.getLast() != last) {
171 current.add(last);
172 }
173 current.add(vertex);
174 label = true;
175 } else {
176 if (!current.isEmpty()) {
177 filteredVertices.add(current);
178 current = new LinkedList<Location>();
179 }
180 }
181
182 last = vertex;
183 }
184
185 if (!current.isEmpty()) {
186 filteredVertices.add(current);
187 current = new LinkedList<Location>();
188 }
189 }
190
191 if (!filteredVertices.isEmpty()
192 && ((LinkedList<Location>) filteredVertices.getFirst())
193 .getFirst() ==
194 ((LinkedList<Location>) filteredVertices.getLast())
195 .getLast()) {
196 LinkedList<Location> tmp = (LinkedList<Location>) filteredVertices
197 .pollLast();
198 tmp.pollLast();
199 if (!filteredVertices.isEmpty()) {
200 tmp.addAll(filteredVertices.pollFirst());
201 }
202 filteredVertices.addFirst(tmp);
203 }
204
205 return filteredVertices;
206 }
207
208
209
210
211
212
213
214
215
216
217
218
219
220 private boolean pointInRectangle(double px, double py, double x1,
221 double y1, double x2, double y2) {
222 return (px >= x1 && px < x2 && py >= y1 && py < y2);
223 }
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239 private boolean lineIntersectsRectangle(
240 double lx1, double ly1, double lx2, double ly2,
241 double x1, double y1, double x2, double y2) {
242
243 if (pointInRectangle(lx1, ly1, x1, y1, x2, y2))
244 return true;
245
246 if (pointInRectangle(lx2, ly2, x1, y1, x2, y2))
247 return true;
248
249
250 if (ly2 - ly1 == 0) {
251 return (y1 <= ly1 && ly1 < y2 && ((lx1 < x1 && x1 <= lx2) || (lx2 < x1 && x1 <= lx1)));
252 }
253
254 if (lx2 - lx1 == 0) {
255 return (x1 <= lx1 && lx1 < x2 && ((ly1 < y1 && y1 <= ly2) || (ly2 < y1 && y1 <= ly1)));
256 }
257
258 double t = (lx2 - lx1) / (ly2 - ly1), x = 0, y = 0;
259
260
261
262
263
264
265
266
267 if (ly1 > y1 && ly2 <= y1 ||
268 ly1 <= y1 && ly2 > y1) {
269
270
271 x = lx1 + t * (y1 - ly1);
272
273 if (x1 <= x && x < x2)
274 return true;
275 }
276
277
278
279 if (ly1 > y2 && ly2 <= y2 ||
280 ly1 <= y2 && ly2 > y2) {
281
282
283 x = lx1 + t * (y2 - ly1);
284
285 if (x1 <= x && x < x2)
286 return true;
287
288 }
289
290
291
292
293 if (lx1 > x1 && lx2 <= x1 ||
294 lx1 <= x1 && lx2 > x1) {
295
296
297 y = ly1 + (x1 - lx1) / t;
298
299 if (y1 <= y && y < y2)
300 return true;
301 }
302
303
304
305
306
307 return false;
308 }
309
310
311
312
313
314
315 public Location getCenter() {
316 return center;
317 }
318
319
320
321
322
323
324
325 public final QuadTreeNode getFirst() {
326 return nodes[0];
327 }
328
329
330
331
332
333
334
335 public final QuadTreeNode getSecond() {
336 return nodes[1];
337 }
338
339
340
341
342
343
344
345 public final QuadTreeNode getThird() {
346 return nodes[2];
347 }
348
349
350
351
352
353
354
355 public final QuadTreeNode getFourth() {
356 return nodes[3];
357 }
358
359
360
361
362
363
364
365 public final QuadTreeNode[] getNodes() {
366 return nodes;
367 }
368
369
370
371
372
373
374 public final QuadTreeNode getParent() {
375 return parent;
376 }
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410 @Override
411 public String toString() {
412 StringBuilder builder = new StringBuilder();
413
414 builder.append(String.format(
415 "o{%.1f, %.1f, %.1f, %.1f}[",
416 x1,
417 y1,
418 x2,
419 y2));
420
421 builder.append(label);
422
423 if (nodes == null) {
424 builder.append("]");
425 return builder.toString();
426 }
427
428 builder.append("\n");
429
430 Matcher matcher;
431
432 if (nodes[0] != null) {
433 matcher = pattern.matcher(nodes[0].toString());
434
435 builder.append(" ");
436 builder.append(matcher.replaceAll("\n "));
437 builder.append("\n");
438 }
439 if (nodes[1] != null) {
440 matcher = pattern.matcher(nodes[1].toString());
441
442 builder.append(" ");
443 builder.append(matcher.replaceAll("\n "));
444 builder.append("\n");
445 }
446 if (nodes[2] != null) {
447 matcher = pattern.matcher(nodes[2].toString());
448
449 builder.append(" ");
450 builder.append(matcher.replaceAll("\n "));
451 builder.append("\n");
452 }
453 if (nodes[3] != null) {
454 matcher = pattern.matcher(nodes[3].toString());
455
456 builder.append(" ");
457 builder.append(matcher.replaceAll("\n "));
458 builder.append("\n");
459 }
460 if (subList != null && !subList.isEmpty()) {
461 builder.append(" ");
462 builder.append("{");
463 builder.append(subList.toString());
464 builder.append("}\n");
465 }
466 builder.append("]");
467 return builder.toString();
468 }
469
470
471
472
473
474
475
476 public final boolean isLabeled() {
477 return label;
478 }
479
480
481
482
483
484
485
486
487 public final void setLabel(boolean value) {
488 label = value;
489 }
490
491
492
493
494
495
496 public double getSize() {
497 return Math.abs(x2 - x1);
498 }
499 }