1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.geometry.core.partitioning.bsp;
18
19 import java.util.ArrayList;
20 import java.util.Arrays;
21 import java.util.HashMap;
22 import java.util.Iterator;
23 import java.util.List;
24 import java.util.Map;
25 import java.util.NoSuchElementException;
26 import java.util.stream.Collectors;
27 import java.util.stream.Stream;
28 import java.util.stream.StreamSupport;
29
30 import org.apache.commons.geometry.core.Transform;
31 import org.apache.commons.geometry.core.partitioning.BoundarySource;
32 import org.apache.commons.geometry.core.partitioning.bsp.BSPTree.FindNodeCutRule;
33 import org.apache.commons.geometry.core.partitioning.test.PartitionTestUtils;
34 import org.apache.commons.geometry.core.partitioning.test.TestBSPTree;
35 import org.apache.commons.geometry.core.partitioning.test.TestBSPTree.TestNode;
36 import org.apache.commons.geometry.core.partitioning.test.TestLine;
37 import org.apache.commons.geometry.core.partitioning.test.TestLineSegment;
38 import org.apache.commons.geometry.core.partitioning.test.TestLineSegmentCollection;
39 import org.apache.commons.geometry.core.partitioning.test.TestPoint2D;
40 import org.apache.commons.geometry.core.partitioning.test.TestTransform2D;
41 import org.junit.jupiter.api.Assertions;
42 import org.junit.jupiter.api.Test;
43
44 class AbstractBSPTreeTest {
45
46 @Test
47 void testInitialization() {
48
49 final TestBSPTree tree = new TestBSPTree();
50
51
52 final TestNode root = tree.getRoot();
53
54 Assertions.assertNotNull(root);
55 Assertions.assertNull(root.getParent());
56
57 PartitionTestUtils.assertIsLeafNode(root);
58 Assertions.assertFalse(root.isPlus());
59 Assertions.assertFalse(root.isMinus());
60
61 Assertions.assertSame(tree, root.getTree());
62 }
63
64 @Test
65 void testNodeStateGetters() {
66
67 final TestBSPTree tree = new TestBSPTree();
68
69 final TestNode root = tree.getRoot();
70 root.cut(TestLine.X_AXIS);
71
72 final TestNode plus = root.getPlus();
73 final TestNode minus = root.getMinus();
74
75
76 Assertions.assertFalse(root.isLeaf());
77 Assertions.assertTrue(root.isInternal());
78 Assertions.assertFalse(root.isPlus());
79 Assertions.assertFalse(root.isMinus());
80
81 Assertions.assertTrue(plus.isLeaf());
82 Assertions.assertFalse(plus.isInternal());
83 Assertions.assertTrue(plus.isPlus());
84 Assertions.assertFalse(plus.isMinus());
85
86 Assertions.assertTrue(minus.isLeaf());
87 Assertions.assertFalse(minus.isInternal());
88 Assertions.assertFalse(minus.isPlus());
89 Assertions.assertTrue(minus.isMinus());
90 }
91
92 @Test
93 void testInsertCut() {
94
95 final TestBSPTree tree = new TestBSPTree();
96 final TestLine line = TestLine.X_AXIS;
97
98
99 final boolean result = tree.getRoot().insertCut(line);
100
101
102 Assertions.assertTrue(result);
103
104 final TestNode root = tree.getRoot();
105 PartitionTestUtils.assertIsInternalNode(root);
106
107 Assertions.assertSame(line, root.getCut().getHyperplane());
108
109 PartitionTestUtils.assertIsLeafNode(root.getMinus());
110 PartitionTestUtils.assertIsLeafNode(root.getPlus());
111 }
112
113 @Test
114 void testInsertCut_fitsCutterToCell() {
115
116 final TestBSPTree tree = new TestBSPTree();
117
118 final TestNode node = tree.getRoot()
119 .cut(TestLine.X_AXIS)
120 .getMinus()
121 .cut(TestLine.Y_AXIS)
122 .getPlus();
123
124
125 final boolean result = node.insertCut(new TestLine(0.5, 1.5, 1.5, 0.5));
126
127
128 Assertions.assertTrue(result);
129 PartitionTestUtils.assertIsInternalNode(node);
130
131 final TestLineSegment segment = (TestLineSegment) node.getCut();
132
133 PartitionTestUtils.assertPointsEqual(new TestPoint2D(0, 2), segment.getStartPoint());
134 PartitionTestUtils.assertPointsEqual(new TestPoint2D(2, 0), segment.getEndPoint());
135 }
136
137 @Test
138 void testInsertCut_doesNotPassThroughCell_intersects() {
139
140 final TestBSPTree tree = new TestBSPTree();
141
142 final TestNode node = tree.getRoot()
143 .cut(TestLine.X_AXIS)
144 .getMinus()
145 .cut(TestLine.Y_AXIS)
146 .getPlus();
147
148
149 final boolean result = node.insertCut(new TestLine(-2, 0, 0, -2));
150
151
152 Assertions.assertFalse(result);
153 PartitionTestUtils.assertIsLeafNode(node);
154 }
155
156 @Test
157 void testInsertCut_doesNotPassThroughCell_parallel() {
158
159 final TestBSPTree tree = new TestBSPTree();
160
161 final TestNode node = tree.getRoot()
162 .cut(TestLine.X_AXIS)
163 .getMinus();
164
165
166 final boolean result = node.insertCut(new TestLine(0, -1, 1, -1));
167
168
169 Assertions.assertFalse(result);
170 PartitionTestUtils.assertIsLeafNode(node);
171 }
172
173 @Test
174 void testInsertCut_doesNotPassThroughCell_removesExistingChildren() {
175
176 final TestBSPTree tree = new TestBSPTree();
177
178 final TestNode node = tree.getRoot()
179 .cut(TestLine.X_AXIS)
180 .getMinus()
181 .cut(TestLine.Y_AXIS)
182 .getPlus()
183 .cut(new TestLine(0, 2, 2, 0));
184
185
186 final boolean result = node.insertCut(new TestLine(-2, 0, 0, -2));
187
188
189 Assertions.assertFalse(result);
190 PartitionTestUtils.assertIsLeafNode(node);
191 }
192
193 @Test
194 void testInsertCut_cutExistsInTree_sameOrientation() {
195
196 final TestBSPTree tree = new TestBSPTree();
197
198 final TestNode node = tree.getRoot()
199 .cut(TestLine.X_AXIS)
200 .getMinus()
201 .cut(TestLine.Y_AXIS)
202 .getPlus()
203 .cut(new TestLine(0, 2, 2, 0));
204
205
206 final boolean result = node.insertCut(new TestLine(0, 2, 0, 3));
207
208
209 Assertions.assertFalse(result);
210 PartitionTestUtils.assertIsLeafNode(node);
211 }
212
213 @Test
214 void testInsertCut_cutExistsInTree_oppositeOrientation() {
215
216 final TestBSPTree tree = new TestBSPTree();
217
218 final TestNode node = tree.getRoot()
219 .cut(TestLine.X_AXIS)
220 .getMinus()
221 .cut(TestLine.Y_AXIS)
222 .getPlus()
223 .cut(new TestLine(0, 2, 2, 0));
224
225
226 final boolean result = node.insertCut(new TestLine(0, 3, 0, 2));
227
228
229 Assertions.assertTrue(result);
230 PartitionTestUtils.assertIsInternalNode(node);
231 }
232
233 @Test
234 void testInsertCut_createRegionWithThicknessOfHyperplane() {
235
236 final TestBSPTree tree = new TestBSPTree();
237
238 final TestNode node = tree.getRoot()
239 .cut(TestLine.X_AXIS)
240 .getMinus();
241
242
243 final boolean result = node.insertCut(new TestLine(0, 0, -1, 0));
244
245
246 Assertions.assertTrue(result);
247
248 Assertions.assertSame(tree.getRoot().getPlus(), tree.findNode(new TestPoint2D(0, -1e-2)));
249 Assertions.assertSame(node.getMinus(), tree.findNode(new TestPoint2D(0, 0)));
250 Assertions.assertSame(node.getPlus(), tree.findNode(new TestPoint2D(0, 1e-2)));
251 }
252
253 @Test
254 void testClearCut_cutExists() {
255
256 final TestBSPTree tree = new TestBSPTree();
257
258 final TestNode node = tree.getRoot()
259 .cut(TestLine.X_AXIS)
260 .getMinus()
261 .cut(TestLine.Y_AXIS);
262
263
264 final boolean result = node.clearCut();
265
266
267 Assertions.assertTrue(result);
268 Assertions.assertTrue(node.isLeaf());
269 Assertions.assertNull(node.getPlus());
270 Assertions.assertNull(node.getMinus());
271 }
272
273 @Test
274 void testClearCut_cutDoesNotExist() {
275
276 final TestBSPTree tree = new TestBSPTree();
277
278 final TestNode node = tree.getRoot()
279 .cut(TestLine.X_AXIS)
280 .getMinus()
281 .cut(TestLine.Y_AXIS)
282 .getMinus();
283
284
285 final boolean result = node.clearCut();
286
287
288 Assertions.assertFalse(result);
289 Assertions.assertTrue(node.isLeaf());
290 Assertions.assertNull(node.getPlus());
291 Assertions.assertNull(node.getMinus());
292 }
293
294 @Test
295 void testClearCut_root_fullTree() {
296
297 final TestBSPTree tree = new TestBSPTree();
298
299 final TestNode node = tree.getRoot()
300 .cut(TestLine.X_AXIS)
301 .getMinus()
302 .cut(TestLine.Y_AXIS)
303 .getMinus();
304
305
306 final boolean result = tree.getRoot().clearCut();
307
308
309 Assertions.assertTrue(result);
310 Assertions.assertTrue(node.isLeaf());
311 Assertions.assertNull(node.getPlus());
312 Assertions.assertNull(node.getMinus());
313
314 Assertions.assertEquals(1, tree.count());
315 }
316
317 @Test
318 void testClearCut_root_emptyTree() {
319
320 final TestBSPTree tree = new TestBSPTree();
321 final TestNode node = tree.getRoot();
322
323
324 final boolean result = node.clearCut();
325
326
327 Assertions.assertFalse(result);
328 Assertions.assertTrue(node.isLeaf());
329 Assertions.assertNull(node.getPlus());
330 Assertions.assertNull(node.getMinus());
331
332 Assertions.assertEquals(1, tree.count());
333 }
334
335 @Test
336 void testFindNode_emptyTree() {
337
338 final TestBSPTree tree = new TestBSPTree();
339 final TestNode root = tree.getRoot();
340
341 final List<TestPoint2D> testPoints = Arrays.asList(
342 new TestPoint2D(0, 0),
343 new TestPoint2D(1, 0),
344 new TestPoint2D(1, 1),
345 new TestPoint2D(0, 1),
346 new TestPoint2D(-1, 1),
347 new TestPoint2D(-1, 0),
348 new TestPoint2D(-1, -1),
349 new TestPoint2D(0, -1),
350 new TestPoint2D(1, -1)
351 );
352
353
354 for (final TestPoint2D pt : testPoints) {
355 Assertions.assertSame(root, tree.findNode(pt));
356 }
357
358 for (final TestPoint2D pt : testPoints) {
359 Assertions.assertSame(root, tree.findNode(pt, FindNodeCutRule.NODE));
360 }
361
362 for (final TestPoint2D pt : testPoints) {
363 Assertions.assertSame(root, tree.findNode(pt, FindNodeCutRule.MINUS));
364 }
365
366 for (final TestPoint2D pt : testPoints) {
367 Assertions.assertSame(root, tree.findNode(pt, FindNodeCutRule.PLUS));
368 }
369 }
370
371 @Test
372 void testFindNode_singleArg() {
373
374 final TestBSPTree tree = new TestBSPTree();
375
376 tree.getRoot()
377 .cut(TestLine.X_AXIS)
378 .getMinus()
379 .cut(TestLine.Y_AXIS)
380 .getPlus()
381 .cut(new TestLine(0, 2, 2, 0));
382
383 final TestNode root = tree.getRoot();
384 final TestNode minusY = root.getPlus();
385
386 final TestNode yCut = root.getMinus();
387 final TestNode minusXPlusY = yCut.getMinus();
388
389 final TestNode diagonalCut = yCut.getPlus();
390 final TestNode underDiagonal = diagonalCut.getPlus();
391 final TestNode aboveDiagonal = diagonalCut.getMinus();
392
393
394 Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(0, 0)));
395
396 Assertions.assertSame(underDiagonal, tree.findNode(new TestPoint2D(1, 0)));
397 Assertions.assertSame(aboveDiagonal, tree.findNode(new TestPoint2D(1, 1)));
398 Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(0, 1)));
399 Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(-1, 1)));
400 Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(-1, 0)));
401 Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(-1, -1)));
402 Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(0, -1)));
403 Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(1, -1)));
404
405 Assertions.assertSame(underDiagonal, tree.findNode(new TestPoint2D(0.5, 0.5)));
406 Assertions.assertSame(aboveDiagonal, tree.findNode(new TestPoint2D(3, 3)));
407 }
408
409 @Test
410 void testFindNode_nodeCutBehavior() {
411
412 final TestBSPTree tree = new TestBSPTree();
413
414 tree.getRoot()
415 .cut(TestLine.X_AXIS)
416 .getMinus()
417 .cut(TestLine.Y_AXIS)
418 .getPlus()
419 .cut(new TestLine(0, 2, 2, 0));
420
421 final TestNode root = tree.getRoot();
422 final TestNode minusY = root.getPlus();
423
424 final TestNode yCut = root.getMinus();
425 final TestNode minusXPlusY = yCut.getMinus();
426
427 final TestNode diagonalCut = yCut.getPlus();
428 final TestNode underDiagonal = diagonalCut.getPlus();
429 final TestNode aboveDiagonal = diagonalCut.getMinus();
430
431 final FindNodeCutRule cutBehavior = FindNodeCutRule.NODE;
432
433
434 Assertions.assertSame(root, tree.findNode(new TestPoint2D(0, 0), cutBehavior));
435
436 Assertions.assertSame(root, tree.findNode(new TestPoint2D(1, 0), cutBehavior));
437 Assertions.assertSame(diagonalCut, tree.findNode(new TestPoint2D(1, 1), cutBehavior));
438 Assertions.assertSame(yCut, tree.findNode(new TestPoint2D(0, 1), cutBehavior));
439 Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(-1, 1), cutBehavior));
440 Assertions.assertSame(root, tree.findNode(new TestPoint2D(-1, 0), cutBehavior));
441 Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(-1, -1), cutBehavior));
442 Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(0, -1), cutBehavior));
443 Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(1, -1), cutBehavior));
444
445 Assertions.assertSame(underDiagonal, tree.findNode(new TestPoint2D(0.5, 0.5), cutBehavior));
446 Assertions.assertSame(aboveDiagonal, tree.findNode(new TestPoint2D(3, 3), cutBehavior));
447 }
448
449 @Test
450 void testFindNode_minusCutBehavior() {
451
452 final TestBSPTree tree = new TestBSPTree();
453
454 tree.getRoot()
455 .cut(TestLine.X_AXIS)
456 .getMinus()
457 .cut(TestLine.Y_AXIS)
458 .getPlus()
459 .cut(new TestLine(0, 2, 2, 0));
460
461 final TestNode root = tree.getRoot();
462 final TestNode minusY = root.getPlus();
463
464 final TestNode yCut = root.getMinus();
465 final TestNode minusXPlusY = yCut.getMinus();
466
467 final TestNode diagonalCut = yCut.getPlus();
468 final TestNode underDiagonal = diagonalCut.getPlus();
469 final TestNode aboveDiagonal = diagonalCut.getMinus();
470
471 final FindNodeCutRule cutBehavior = FindNodeCutRule.MINUS;
472
473
474 Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(0, 0), cutBehavior));
475
476 Assertions.assertSame(underDiagonal, tree.findNode(new TestPoint2D(1, 0), cutBehavior));
477 Assertions.assertSame(aboveDiagonal, tree.findNode(new TestPoint2D(1, 1), cutBehavior));
478 Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(0, 1), cutBehavior));
479 Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(-1, 1), cutBehavior));
480 Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(-1, 0), cutBehavior));
481 Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(-1, -1), cutBehavior));
482 Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(0, -1), cutBehavior));
483 Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(1, -1), cutBehavior));
484
485 Assertions.assertSame(underDiagonal, tree.findNode(new TestPoint2D(0.5, 0.5), cutBehavior));
486 Assertions.assertSame(aboveDiagonal, tree.findNode(new TestPoint2D(3, 3), cutBehavior));
487 }
488
489 @Test
490 void testFindNode_plusCutBehavior() {
491
492 final TestBSPTree tree = new TestBSPTree();
493
494 tree.getRoot()
495 .cut(TestLine.X_AXIS)
496 .getMinus()
497 .cut(TestLine.Y_AXIS)
498 .getPlus()
499 .cut(new TestLine(0, 2, 2, 0));
500
501 final TestNode root = tree.getRoot();
502 final TestNode minusY = root.getPlus();
503
504 final TestNode yCut = root.getMinus();
505 final TestNode minusXPlusY = yCut.getMinus();
506
507 final TestNode diagonalCut = yCut.getPlus();
508 final TestNode underDiagonal = diagonalCut.getPlus();
509 final TestNode aboveDiagonal = diagonalCut.getMinus();
510
511 final FindNodeCutRule cutBehavior = FindNodeCutRule.PLUS;
512
513
514 Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(0, 0), cutBehavior));
515
516 Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(1, 0), cutBehavior));
517 Assertions.assertSame(underDiagonal, tree.findNode(new TestPoint2D(1, 1), cutBehavior));
518 Assertions.assertSame(underDiagonal, tree.findNode(new TestPoint2D(0, 1), cutBehavior));
519 Assertions.assertSame(minusXPlusY, tree.findNode(new TestPoint2D(-1, 1), cutBehavior));
520 Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(-1, 0), cutBehavior));
521 Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(-1, -1), cutBehavior));
522 Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(0, -1), cutBehavior));
523 Assertions.assertSame(minusY, tree.findNode(new TestPoint2D(1, -1), cutBehavior));
524
525 Assertions.assertSame(underDiagonal, tree.findNode(new TestPoint2D(0.5, 0.5), cutBehavior));
526 Assertions.assertSame(aboveDiagonal, tree.findNode(new TestPoint2D(3, 3), cutBehavior));
527 }
528
529 @Test
530 void testInsert_convex_emptyTree() {
531
532 final TestBSPTree tree = new TestBSPTree();
533
534
535 tree.insert(new TestLineSegment(1, 0, 1, 1));
536
537
538 final TestNode root = tree.getRoot();
539 Assertions.assertFalse(root.isLeaf());
540 Assertions.assertTrue(root.getMinus().isLeaf());
541 Assertions.assertTrue(root.getPlus().isLeaf());
542
543 final TestLineSegment seg = (TestLineSegment) root.getCut();
544 PartitionTestUtils.assertPointsEqual(
545 new TestPoint2D(1, Double.NEGATIVE_INFINITY),
546 seg.getStartPoint());
547 PartitionTestUtils.assertPointsEqual(
548 new TestPoint2D(1, Double.POSITIVE_INFINITY),
549 seg.getEndPoint());
550 }
551
552 @Test
553 void testInsert_convex_noSplit() {
554
555 final TestBSPTree tree = new TestBSPTree();
556 tree.getRoot()
557 .cut(TestLine.X_AXIS)
558 .getMinus()
559 .cut(TestLine.Y_AXIS);
560
561
562 tree.insert(new TestLineSegment(0.5, 1.5, 1.5, 0.5));
563
564
565 final TestNode root = tree.getRoot();
566 Assertions.assertFalse(root.isLeaf());
567
568 final TestNode node = tree.findNode(new TestPoint2D(0.5, 0.5));
569 final TestLineSegment seg = (TestLineSegment) node.getParent().getCut();
570
571 PartitionTestUtils.assertPointsEqual(new TestPoint2D(0, 2), seg.getStartPoint());
572 PartitionTestUtils.assertPointsEqual(new TestPoint2D(2, 0), seg.getEndPoint());
573
574 Assertions.assertTrue(tree.getRoot().getPlus().isLeaf());
575 Assertions.assertTrue(tree.getRoot().getMinus().getMinus().isLeaf());
576 }
577
578 @Test
579 void testInsert_convex_split() {
580
581 final TestBSPTree tree = new TestBSPTree();
582 tree.getRoot()
583 .cut(TestLine.X_AXIS)
584 .getMinus()
585 .cut(TestLine.Y_AXIS);
586
587
588 tree.insert(new TestLineSegment(-0.5, 2.5, 2.5, -0.5));
589
590
591 final TestNode root = tree.getRoot();
592 Assertions.assertFalse(root.isLeaf());
593
594 final TestNode plusXPlusY = tree.getRoot().getMinus().getPlus();
595 final TestLineSegment plusXPlusYSeg = (TestLineSegment) plusXPlusY.getCut();
596
597 PartitionTestUtils.assertPointsEqual(new TestPoint2D(0, 2), plusXPlusYSeg.getStartPoint());
598 PartitionTestUtils.assertPointsEqual(new TestPoint2D(2, 0), plusXPlusYSeg.getEndPoint());
599
600 final TestNode minusY = tree.getRoot().getPlus();
601 final TestLineSegment minusYSeg = (TestLineSegment) minusY.getCut();
602
603 PartitionTestUtils.assertPointsEqual(new TestPoint2D(2, 0), minusYSeg.getStartPoint());
604 PartitionTestUtils.assertPointsEqual(
605 new TestPoint2D(Double.POSITIVE_INFINITY, Double.NEGATIVE_INFINITY), minusYSeg.getEndPoint());
606
607 final TestNode minusXPlusY = tree.getRoot().getMinus().getMinus();
608 final TestLineSegment minusXPlusYSeg = (TestLineSegment) minusXPlusY.getCut();
609
610 PartitionTestUtils.assertPointsEqual(
611 new TestPoint2D(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY), minusXPlusYSeg.getStartPoint());
612 PartitionTestUtils.assertPointsEqual(new TestPoint2D(0, 2), minusXPlusYSeg.getEndPoint());
613 }
614
615 @Test
616 void testInsert_convexList_convexRegion() {
617
618 final TestBSPTree tree = new TestBSPTree();
619
620 final TestLineSegment a = new TestLineSegment(0, 0, 1, 0);
621 final TestLineSegment b = new TestLineSegment(1, 0, 0, 1);
622 final TestLineSegment c = new TestLineSegment(0, 1, 0, 0);
623
624
625 tree.insert(Arrays.asList(a, b, c));
626
627
628 final List<TestLineSegment> segments = getLineSegments(tree);
629
630 Assertions.assertEquals(3, segments.size());
631
632 PartitionTestUtils.assertSegmentsEqual(
633 new TestLineSegment(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
634 segments.get(0));
635 PartitionTestUtils.assertSegmentsEqual(
636 new TestLineSegment(-Math.sqrt(0.5), Double.POSITIVE_INFINITY, new TestLine(1, 0, 0, 1)),
637 segments.get(1));
638 PartitionTestUtils.assertSegmentsEqual(c, segments.get(2));
639 }
640
641 @Test
642 void testInsert_convexList_concaveRegion() {
643
644 final TestBSPTree tree = new TestBSPTree();
645
646 final TestLineSegment a = new TestLineSegment(-1, -1, 1, -1);
647 final TestLineSegment b = new TestLineSegment(1, -1, 0, 0);
648 final TestLineSegment c = new TestLineSegment(0, 0, 1, 1);
649 final TestLineSegment d = new TestLineSegment(1, 1, -1, 1);
650 final TestLineSegment e = new TestLineSegment(-1, 1, -1, -1);
651
652
653 tree.insert(Arrays.asList(a, b, c, d, e));
654
655
656 final List<TestLineSegment> segments = getLineSegments(tree);
657
658 Assertions.assertEquals(5, segments.size());
659
660 PartitionTestUtils.assertSegmentsEqual(
661 new TestLineSegment(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, new TestLine(-1, -1, 1, -1)),
662 segments.get(0));
663 PartitionTestUtils.assertSegmentsEqual(
664 new TestLineSegment(-Math.sqrt(2), Double.POSITIVE_INFINITY, new TestLine(1, -1, 0, 0)),
665 segments.get(1));
666 PartitionTestUtils.assertSegmentsEqual(
667 new TestLineSegment(-1, 1, -1, -1),
668 segments.get(2));
669
670 PartitionTestUtils.assertSegmentsEqual(
671 new TestLineSegment(0, Double.POSITIVE_INFINITY, new TestLine(0, 0, 1, 1)),
672 segments.get(3));
673 PartitionTestUtils.assertSegmentsEqual(
674 new TestLineSegment(1, 1, -1, 1),
675 segments.get(4));
676 }
677
678 @Test
679 void testInsert_hyperplaneSubset_concaveRegion() {
680
681 final TestBSPTree tree = new TestBSPTree();
682
683 final TestLineSegment a = new TestLineSegment(-1, -1, 1, -1);
684 final TestLineSegment b = new TestLineSegment(1, -1, 0, 0);
685 final TestLineSegment c = new TestLineSegment(0, 0, 1, 1);
686 final TestLineSegment d = new TestLineSegment(1, 1, -1, 1);
687 final TestLineSegment e = new TestLineSegment(-1, 1, -1, -1);
688
689 final TestLineSegmentCollection coll = new TestLineSegmentCollection(
690 Arrays.asList(a, b, c, d, e));
691
692
693 tree.insert(coll);
694
695
696 final List<TestLineSegment> segments = getLineSegments(tree);
697
698 Assertions.assertEquals(5, segments.size());
699
700 PartitionTestUtils.assertSegmentsEqual(
701 new TestLineSegment(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, new TestLine(-1, -1, 1, -1)),
702 segments.get(0));
703 PartitionTestUtils.assertSegmentsEqual(
704 new TestLineSegment(-Math.sqrt(2), Double.POSITIVE_INFINITY, new TestLine(1, -1, 0, 0)),
705 segments.get(1));
706 PartitionTestUtils.assertSegmentsEqual(
707 new TestLineSegment(-1, 1, -1, -1),
708 segments.get(2));
709
710 PartitionTestUtils.assertSegmentsEqual(
711 new TestLineSegment(0, Double.POSITIVE_INFINITY, new TestLine(0, 0, 1, 1)),
712 segments.get(3));
713 PartitionTestUtils.assertSegmentsEqual(
714 new TestLineSegment(1, 1, -1, 1),
715 segments.get(4));
716 }
717
718 @Test
719 void testInsert_boundarySource() {
720
721 final TestBSPTree tree = new TestBSPTree();
722
723 final TestLineSegment a = new TestLineSegment(-1, -1, 1, -1);
724 final TestLineSegment b = new TestLineSegment(1, -1, 0, 0);
725 final TestLineSegment c = new TestLineSegment(0, 0, 1, 1);
726 final TestLineSegment d = new TestLineSegment(1, 1, -1, 1);
727 final TestLineSegment e = new TestLineSegment(-1, 1, -1, -1);
728
729 final BoundarySource<TestLineSegment> src = () -> Stream.of(a, b, c, d, e);
730
731
732 tree.insert(src);
733
734
735 final List<TestLineSegment> segments = getLineSegments(tree);
736
737 Assertions.assertEquals(5, segments.size());
738
739 PartitionTestUtils.assertSegmentsEqual(
740 new TestLineSegment(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, new TestLine(-1, -1, 1, -1)),
741 segments.get(0));
742 PartitionTestUtils.assertSegmentsEqual(
743 new TestLineSegment(-Math.sqrt(2), Double.POSITIVE_INFINITY, new TestLine(1, -1, 0, 0)),
744 segments.get(1));
745 PartitionTestUtils.assertSegmentsEqual(
746 new TestLineSegment(-1, 1, -1, -1),
747 segments.get(2));
748
749 PartitionTestUtils.assertSegmentsEqual(
750 new TestLineSegment(0, Double.POSITIVE_INFINITY, new TestLine(0, 0, 1, 1)),
751 segments.get(3));
752 PartitionTestUtils.assertSegmentsEqual(
753 new TestLineSegment(1, 1, -1, 1),
754 segments.get(4));
755 }
756
757 @Test
758 void testInsert_boundarySource_emptySource() {
759
760 final TestBSPTree tree = new TestBSPTree();
761
762 final BoundarySource<TestLineSegment> src = Stream::empty;
763
764
765 tree.insert(src);
766
767
768 Assertions.assertEquals(1, tree.count());
769 }
770
771 @Test
772 void testCount() {
773
774 final TestBSPTree tree = new TestBSPTree();
775
776
777 Assertions.assertEquals(1, tree.count());
778 Assertions.assertEquals(1, tree.getRoot().count());
779
780 tree.getRoot().insertCut(TestLine.X_AXIS);
781 Assertions.assertEquals(1, tree.getRoot().getMinus().count());
782 Assertions.assertEquals(1, tree.getRoot().getPlus().count());
783 Assertions.assertEquals(3, tree.count());
784
785 tree.getRoot().getPlus().insertCut(TestLine.Y_AXIS);
786 Assertions.assertEquals(1, tree.getRoot().getMinus().count());
787 Assertions.assertEquals(3, tree.getRoot().getPlus().count());
788 Assertions.assertEquals(5, tree.count());
789
790 tree.getRoot().getMinus().insertCut(TestLine.Y_AXIS);
791 Assertions.assertEquals(3, tree.getRoot().getMinus().count());
792 Assertions.assertEquals(3, tree.getRoot().getPlus().count());
793 Assertions.assertEquals(7, tree.count());
794
795 tree.getRoot().getMinus().insertCut(new TestLine(new TestPoint2D(-1, -1), new TestPoint2D(1, -1)));
796 Assertions.assertEquals(1, tree.getRoot().getMinus().count());
797 Assertions.assertEquals(3, tree.getRoot().getPlus().count());
798 Assertions.assertEquals(5, tree.count());
799 }
800
801 @Test
802 void testHeight() {
803
804 final TestBSPTree tree = new TestBSPTree();
805
806
807 Assertions.assertEquals(0, tree.height());
808 Assertions.assertEquals(0, tree.getRoot().height());
809
810 tree.getRoot().insertCut(TestLine.X_AXIS);
811 Assertions.assertEquals(0, tree.getRoot().getMinus().height());
812 Assertions.assertEquals(0, tree.getRoot().getPlus().height());
813 Assertions.assertEquals(1, tree.height());
814
815 tree.getRoot().getPlus().insertCut(TestLine.Y_AXIS);
816 Assertions.assertEquals(0, tree.getRoot().getMinus().height());
817 Assertions.assertEquals(1, tree.getRoot().getPlus().height());
818 Assertions.assertEquals(2, tree.height());
819
820 tree.getRoot().getMinus().insertCut(TestLine.Y_AXIS);
821 Assertions.assertEquals(1, tree.getRoot().getMinus().height());
822 Assertions.assertEquals(1, tree.getRoot().getPlus().height());
823 Assertions.assertEquals(2, tree.height());
824
825 tree.getRoot().getMinus().clearCut();
826 Assertions.assertEquals(0, tree.getRoot().getMinus().height());
827 Assertions.assertEquals(1, tree.getRoot().getPlus().height());
828 Assertions.assertEquals(2, tree.height());
829
830 tree.getRoot().getPlus().getPlus()
831 .insertCut(new TestLine(new TestPoint2D(0, -1), new TestPoint2D(1, -1)));
832
833 Assertions.assertEquals(0, tree.getRoot().getMinus().height());
834 Assertions.assertEquals(2, tree.getRoot().getPlus().height());
835 Assertions.assertEquals(3, tree.height());
836 }
837
838 @Test
839 void testDepth() {
840
841 final TestBSPTree tree = new TestBSPTree();
842
843 final TestNode root = tree.getRoot();
844 root.cut(TestLine.X_AXIS)
845 .getMinus()
846 .cut(TestLine.Y_AXIS);
847
848
849 Assertions.assertEquals(0, root.depth());
850
851 Assertions.assertEquals(1, root.getPlus().depth());
852
853 Assertions.assertEquals(1, root.getMinus().depth());
854 Assertions.assertEquals(2, root.getMinus().getPlus().depth());
855 Assertions.assertEquals(2, root.getMinus().getMinus().depth());
856 }
857
858 @Test
859 void testDepth_detachedNodes() {
860
861 final TestBSPTree tree = new TestBSPTree();
862
863 final TestNode detached = new TestNode(tree);
864 detached.cut(TestLine.X_AXIS)
865 .getMinus()
866 .cut(TestLine.Y_AXIS);
867
868
869 Assertions.assertEquals(-1, detached.depth());
870
871 Assertions.assertEquals(-1, detached.getPlus().depth());
872
873 Assertions.assertEquals(-1, detached.getMinus().depth());
874 Assertions.assertEquals(-1, detached.getMinus().getPlus().depth());
875 Assertions.assertEquals(-1, detached.getMinus().getMinus().depth());
876 }
877
878 @Test
879 void testVisit_defaultOrder() {
880
881 final TestBSPTree tree = new TestBSPTree();
882 tree.getRoot().cut(TestLine.X_AXIS)
883 .getMinus().cut(TestLine.Y_AXIS);
884
885 final TestNode root = tree.getRoot();
886 final TestNode minus = root.getMinus();
887 final TestNode plus = root.getPlus();
888 final TestNode minusMinus = minus.getMinus();
889 final TestNode minusPlus = minus.getPlus();
890
891 final List<TestNode> nodes = new ArrayList<>();
892
893
894 tree.accept(node -> {
895 nodes.add(node);
896 return BSPTreeVisitor.Result.CONTINUE;
897 });
898
899
900 Assertions.assertEquals(
901 Arrays.asList(root, minus, minusMinus, minusPlus, plus),
902 nodes);
903 }
904
905 @Test
906 void testVisit_specifiedOrder() {
907
908 final TestBSPTree tree = new TestBSPTree();
909 tree.getRoot().cut(TestLine.X_AXIS)
910 .getMinus().cut(TestLine.Y_AXIS);
911
912 final TestNode root = tree.getRoot();
913 final TestNode minus = root.getMinus();
914 final TestNode plus = root.getPlus();
915 final TestNode minusMinus = minus.getMinus();
916 final TestNode minusPlus = minus.getPlus();
917
918
919 final TestVisitor plusMinusNode = new TestVisitor(BSPTreeVisitor.Order.PLUS_MINUS_NODE);
920 tree.accept(plusMinusNode);
921 Assertions.assertEquals(
922 Arrays.asList(plus, minusPlus, minusMinus, minus, root),
923 plusMinusNode.getVisited());
924
925 final TestVisitor plusNodeMinus = new TestVisitor(BSPTreeVisitor.Order.PLUS_NODE_MINUS);
926 tree.accept(plusNodeMinus);
927 Assertions.assertEquals(
928 Arrays.asList(plus, root, minusPlus, minus, minusMinus),
929 plusNodeMinus.getVisited());
930
931 final TestVisitor minusPlusNode = new TestVisitor(BSPTreeVisitor.Order.MINUS_PLUS_NODE);
932 tree.accept(minusPlusNode);
933 Assertions.assertEquals(
934 Arrays.asList(minusMinus, minusPlus, minus, plus, root),
935 minusPlusNode.getVisited());
936
937 final TestVisitor minusNodePlus = new TestVisitor(BSPTreeVisitor.Order.MINUS_NODE_PLUS);
938 tree.accept(minusNodePlus);
939 Assertions.assertEquals(
940 Arrays.asList(minusMinus, minus, minusPlus, root, plus),
941 minusNodePlus.getVisited());
942
943 final TestVisitor nodeMinusPlus = new TestVisitor(BSPTreeVisitor.Order.NODE_MINUS_PLUS);
944 tree.accept(nodeMinusPlus);
945 Assertions.assertEquals(
946 Arrays.asList(root, minus, minusMinus, minusPlus, plus),
947 nodeMinusPlus.getVisited());
948
949 final TestVisitor nodePlusMinus = new TestVisitor(BSPTreeVisitor.Order.NODE_PLUS_MINUS);
950 tree.accept(nodePlusMinus);
951 Assertions.assertEquals(
952 Arrays.asList(root, plus, minus, minusPlus, minusMinus),
953 nodePlusMinus.getVisited());
954 }
955
956 @Test
957 void testVisit_nullVisitOrderSkipsSubtree() {
958
959 final TestBSPTree tree = new TestBSPTree();
960 tree.getRoot().cut(TestLine.X_AXIS)
961 .getMinus().cut(TestLine.Y_AXIS);
962
963 final TestNode root = tree.getRoot();
964 final TestNode plus = root.getPlus();
965 final TestNode minus = root.getMinus();
966
967 final TestVisitor visitor = new TestVisitor(BSPTreeVisitor.Order.NODE_MINUS_PLUS) {
968 @Override
969 public Order visitOrder(final TestNode node) {
970 if (node == minus) {
971 return null;
972 }
973 return super.visitOrder(node);
974 }
975 };
976
977
978 tree.accept(visitor);
979
980
981 Assertions.assertEquals(
982 Arrays.asList(root, plus),
983 visitor.getVisited());
984 }
985
986 @Test
987 void testVisit_noneVisitOrderSkipsSubtree() {
988
989 final TestBSPTree tree = new TestBSPTree();
990 tree.getRoot().cut(TestLine.X_AXIS)
991 .getMinus().cut(TestLine.Y_AXIS);
992
993 final TestNode root = tree.getRoot();
994 final TestNode plus = root.getPlus();
995 final TestNode minus = root.getMinus();
996
997 final TestVisitor visitor = new TestVisitor(BSPTreeVisitor.Order.NODE_MINUS_PLUS) {
998 @Override
999 public Order visitOrder(final TestNode node) {
1000 if (node == minus) {
1001 return Order.NONE;
1002 }
1003 return super.visitOrder(node);
1004 }
1005 };
1006
1007
1008 tree.accept(visitor);
1009
1010
1011 Assertions.assertEquals(
1012 Arrays.asList(root, plus),
1013 visitor.getVisited());
1014 }
1015
1016 @Test
1017 void testVisit_visitorReturnsNull_terminatesEarly() {
1018
1019 final TestBSPTree tree = new TestBSPTree();
1020 tree.getRoot().cut(TestLine.X_AXIS)
1021 .getMinus().cut(TestLine.Y_AXIS);
1022
1023 final TestNode root = tree.getRoot();
1024 final TestNode minus = root.getMinus();
1025 final TestNode minusMinus = minus.getMinus();
1026 final TestNode minusPlus = minus.getPlus();
1027
1028 final TestVisitor visitor = new TestVisitor(BSPTreeVisitor.Order.MINUS_PLUS_NODE) {
1029 @Override
1030 public Result visit(final TestNode node) {
1031 super.visit(node);
1032
1033 if (node == minus) {
1034 return null;
1035 }
1036 return Result.CONTINUE;
1037 }
1038 };
1039
1040
1041 tree.accept(visitor);
1042
1043
1044 Assertions.assertEquals(
1045 Arrays.asList(minusMinus, minusPlus, minus),
1046 visitor.getVisited());
1047 }
1048
1049 @Test
1050 void testVisit_visitorReturnsTerminate_terminatesEarly() {
1051
1052 final TestBSPTree tree = new TestBSPTree();
1053 tree.getRoot().cut(TestLine.X_AXIS)
1054 .getMinus().cut(TestLine.Y_AXIS);
1055
1056 final TestNode root = tree.getRoot();
1057 final TestNode minus = root.getMinus();
1058 final TestNode minusMinus = minus.getMinus();
1059 final TestNode minusPlus = minus.getPlus();
1060
1061 final TestVisitor visitor = new TestVisitor(BSPTreeVisitor.Order.MINUS_PLUS_NODE) {
1062 @Override
1063 public Result visit(final TestNode node) {
1064 super.visit(node);
1065
1066 if (node == minus) {
1067 return Result.TERMINATE;
1068 }
1069 return Result.CONTINUE;
1070 }
1071 };
1072
1073
1074 tree.accept(visitor);
1075
1076
1077 Assertions.assertEquals(
1078 Arrays.asList(minusMinus, minusPlus, minus),
1079 visitor.getVisited());
1080 }
1081
1082 @Test
1083 void testVisit_earlyTerminationPermutations() {
1084
1085 final TestBSPTree tree = new TestBSPTree();
1086 tree.getRoot().cut(TestLine.X_AXIS)
1087 .getMinus().cut(TestLine.Y_AXIS);
1088
1089 final TestNode root = tree.getRoot();
1090 final TestNode minus = root.getMinus();
1091 final TestNode plus = root.getPlus();
1092 final TestNode minusMinus = minus.getMinus();
1093 final TestNode minusPlus = minus.getPlus();
1094
1095
1096 final TestVisitor plusMinusNode = new TestVisitor(BSPTreeVisitor.Order.PLUS_MINUS_NODE).withTerminationNode(minus);
1097 tree.accept(plusMinusNode);
1098 Assertions.assertEquals(
1099 Arrays.asList(plus, minusPlus, minusMinus, minus),
1100 plusMinusNode.getVisited());
1101
1102 final TestVisitor plusNodeMinus = new TestVisitor(BSPTreeVisitor.Order.PLUS_NODE_MINUS).withTerminationNode(minus);
1103 tree.accept(plusNodeMinus);
1104 Assertions.assertEquals(
1105 Arrays.asList(plus, root, minusPlus, minus),
1106 plusNodeMinus.getVisited());
1107
1108 final TestVisitor minusPlusNode = new TestVisitor(BSPTreeVisitor.Order.MINUS_PLUS_NODE).withTerminationNode(minus);
1109 tree.accept(minusPlusNode);
1110 Assertions.assertEquals(
1111 Arrays.asList(minusMinus, minusPlus, minus),
1112 minusPlusNode.getVisited());
1113
1114 final TestVisitor minusNodePlus = new TestVisitor(BSPTreeVisitor.Order.MINUS_NODE_PLUS).withTerminationNode(minus);
1115 tree.accept(minusNodePlus);
1116 Assertions.assertEquals(
1117 Arrays.asList(minusMinus, minus),
1118 minusNodePlus.getVisited());
1119
1120 final TestVisitor nodeMinusPlus = new TestVisitor(BSPTreeVisitor.Order.NODE_MINUS_PLUS).withTerminationNode(minus);
1121 tree.accept(nodeMinusPlus);
1122 Assertions.assertEquals(
1123 Arrays.asList(root, minus),
1124 nodeMinusPlus.getVisited());
1125
1126 final TestVisitor nodePlusMinus = new TestVisitor(BSPTreeVisitor.Order.NODE_PLUS_MINUS).withTerminationNode(minus);
1127 tree.accept(nodePlusMinus);
1128 Assertions.assertEquals(
1129 Arrays.asList(root, plus, minus),
1130 nodePlusMinus.getVisited());
1131 }
1132
1133 @Test
1134 void testVisit_visitNode() {
1135
1136 final TestBSPTree tree = new TestBSPTree();
1137 tree.getRoot().cut(TestLine.X_AXIS)
1138 .getMinus().cut(TestLine.Y_AXIS);
1139
1140 final TestNode root = tree.getRoot();
1141 final TestNode minus = root.getMinus();
1142 final TestNode minusMinus = minus.getMinus();
1143 final TestNode minusPlus = minus.getPlus();
1144
1145 final List<TestNode> nodes = new ArrayList<>();
1146
1147
1148 minus.accept(node -> {
1149 nodes.add(node);
1150 return BSPTreeVisitor.Result.CONTINUE;
1151 });
1152
1153
1154 Assertions.assertEquals(
1155 Arrays.asList(minus, minusMinus, minusPlus),
1156 nodes);
1157 }
1158
1159 @Test
1160 void testNodesIterable_emptyTree() {
1161
1162 final TestBSPTree tree = new TestBSPTree();
1163 final List<TestNode> nodes = new ArrayList<>();
1164
1165
1166 for (final TestNode node : tree.nodes()) {
1167 nodes.add(node);
1168 }
1169
1170
1171 Assertions.assertEquals(1, nodes.size());
1172 Assertions.assertSame(tree.getRoot(), nodes.get(0));
1173 }
1174
1175 @Test
1176 void testNodesIterable_multipleNodes() {
1177
1178 final TestBSPTree tree = new TestBSPTree();
1179
1180 final TestNode root = tree.getRoot();
1181 root.cut(TestLine.X_AXIS)
1182 .getMinus()
1183 .cut(TestLine.Y_AXIS)
1184 .getParent()
1185 .getPlus()
1186 .cut(TestLine.Y_AXIS);
1187
1188 final List<TestNode> nodes = new ArrayList<>();
1189
1190
1191 for (final TestNode node : tree.nodes()) {
1192 nodes.add(node);
1193 }
1194
1195
1196 Assertions.assertEquals(7, nodes.size());
1197 Assertions.assertSame(root, nodes.get(0));
1198
1199 Assertions.assertSame(root.getMinus(), nodes.get(1));
1200 Assertions.assertSame(root.getMinus().getMinus(), nodes.get(2));
1201 Assertions.assertSame(root.getMinus().getPlus(), nodes.get(3));
1202
1203 Assertions.assertSame(root.getPlus(), nodes.get(4));
1204 Assertions.assertSame(root.getPlus().getMinus(), nodes.get(5));
1205 Assertions.assertSame(root.getPlus().getPlus(), nodes.get(6));
1206 }
1207
1208
1209 @Test
1210 void testNodesIterable_iteratorThrowsNoSuchElementExceptionAtEnd() {
1211
1212 final TestBSPTree tree = new TestBSPTree();
1213
1214 final Iterator<TestNode> it = tree.nodes().iterator();
1215 it.next();
1216
1217
1218 try {
1219 it.next();
1220 Assertions.fail("Operation should have thrown an exception");
1221 } catch (final NoSuchElementException exc) {
1222
1223 }
1224 }
1225
1226 @Test
1227 void testSubtreeNodesIterable_singleNodeSubtree() {
1228
1229 final TestBSPTree tree = new TestBSPTree();
1230 final TestNode node = tree.getRoot().cut(TestLine.X_AXIS)
1231 .getMinus()
1232 .cut(TestLine.Y_AXIS)
1233 .getMinus();
1234
1235 final List<TestNode> nodes = new ArrayList<>();
1236
1237 for (final TestNode n : node.nodes()) {
1238 nodes.add(n);
1239 }
1240
1241
1242 Assertions.assertEquals(1, nodes.size());
1243 Assertions.assertSame(node, nodes.get(0));
1244 }
1245
1246 @Test
1247 void testSubtreeNodesIterable_multipleNodeSubtree() {
1248
1249 final TestBSPTree tree = new TestBSPTree();
1250 final TestNode node = tree.getRoot().cut(TestLine.X_AXIS)
1251 .getMinus()
1252 .cut(TestLine.Y_AXIS);
1253
1254 final List<TestNode> nodes = new ArrayList<>();
1255
1256 for (final TestNode n : node.nodes()) {
1257 nodes.add(n);
1258 }
1259
1260
1261 Assertions.assertEquals(3, nodes.size());
1262 Assertions.assertSame(node, nodes.get(0));
1263 Assertions.assertSame(node.getMinus(), nodes.get(1));
1264 Assertions.assertSame(node.getPlus(), nodes.get(2));
1265 }
1266
1267 @Test
1268 void testNodeTrim() {
1269
1270 final TestBSPTree tree = new TestBSPTree();
1271 tree.getRoot().cut(TestLine.Y_AXIS)
1272 .getPlus()
1273 .cut(new TestLine(new TestPoint2D(0, 0), new TestPoint2D(1, 1)))
1274 .getPlus()
1275 .cut(new TestLine(new TestPoint2D(1.5, 1.5), new TestPoint2D(2, 1)));
1276
1277 final TestNode root = tree.getRoot();
1278 final TestNode plus = root.getPlus();
1279 final TestNode plusMinus = plus.getMinus();
1280 final TestNode plusPlusPlus = plus.getPlus().getPlus();
1281
1282 final TestLineSegment xAxisSeg = TestLine.X_AXIS.span();
1283 final TestLineSegment shortSeg = new TestLineSegment(new TestPoint2D(2, 0), new TestPoint2D(2, 2));
1284
1285
1286 Assertions.assertSame(xAxisSeg, root.trim(xAxisSeg));
1287 Assertions.assertSame(shortSeg, root.trim(shortSeg));
1288
1289 PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
1290 (TestLineSegment) plus.trim(xAxisSeg));
1291 Assertions.assertSame(shortSeg, plus.trim(shortSeg));
1292
1293 Assertions.assertNull(plusMinus.trim(xAxisSeg));
1294 Assertions.assertNull(plusMinus.trim(shortSeg));
1295
1296 PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, 3, TestLine.X_AXIS),
1297 (TestLineSegment) plusPlusPlus.trim(xAxisSeg));
1298 PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(new TestPoint2D(2, 0), new TestPoint2D(2, 1)),
1299 (TestLineSegment) plusPlusPlus.trim(shortSeg));
1300 }
1301
1302 @Test
1303 void testCopy_rootOnly() {
1304
1305 final TestBSPTree tree = new TestBSPTree();
1306
1307
1308 final TestBSPTree copy = new TestBSPTree();
1309 copy.copy(tree);
1310
1311
1312 Assertions.assertNotSame(tree, copy);
1313 Assertions.assertNotSame(tree.getRoot(), copy.getRoot());
1314
1315 Assertions.assertEquals(tree.count(), copy.count());
1316 }
1317
1318 @Test
1319 void testCopy_withCuts() {
1320
1321 final TestBSPTree tree = new TestBSPTree();
1322 tree.getRoot()
1323 .cut(TestLine.X_AXIS)
1324 .getMinus()
1325 .cut(TestLine.Y_AXIS);
1326
1327
1328 final TestBSPTree copy = new TestBSPTree();
1329 copy.copy(tree);
1330
1331
1332 Assertions.assertNotSame(tree, copy);
1333 assertNodesCopiedRecursive(tree.getRoot(), copy.getRoot());
1334 Assertions.assertEquals(tree.count(), copy.count());
1335 }
1336
1337 @Test
1338 void testCopy_changesToOneTreeDoNotAffectCopy() {
1339
1340 final TestBSPTree tree = new TestBSPTree();
1341 tree.getRoot()
1342 .cut(TestLine.X_AXIS)
1343 .getMinus()
1344 .cut(TestLine.Y_AXIS);
1345
1346
1347 final TestBSPTree copy = new TestBSPTree();
1348 copy.copy(tree);
1349 tree.getRoot().clearCut();
1350
1351
1352 Assertions.assertEquals(1, tree.count());
1353 Assertions.assertEquals(5, copy.count());
1354 }
1355
1356 @Test
1357 void testCopy_instancePassedAsArgument() {
1358
1359 final TestBSPTree tree = new TestBSPTree();
1360 tree.getRoot()
1361 .cut(TestLine.X_AXIS)
1362 .getMinus()
1363 .cut(TestLine.Y_AXIS);
1364
1365
1366 tree.copy(tree);
1367
1368
1369 Assertions.assertEquals(5, tree.count());
1370 }
1371
1372 @Test
1373 void testExtract_singleNodeTree() {
1374
1375 final TestBSPTree tree = new TestBSPTree();
1376
1377 final TestBSPTree result = new TestBSPTree();
1378 result.getRoot().insertCut(TestLine.X_AXIS);
1379
1380
1381 result.extract(tree.getRoot());
1382
1383
1384 Assertions.assertNotSame(tree.getRoot(), result.getRoot());
1385 Assertions.assertEquals(1, tree.count());
1386 Assertions.assertEquals(1, result.count());
1387
1388 PartitionTestUtils.assertTreeStructure(tree);
1389 PartitionTestUtils.assertTreeStructure(result);
1390 }
1391
1392 @Test
1393 void testExtract_clearsExistingNodesInCallingTree() {
1394
1395 final TestBSPTree tree = new TestBSPTree();
1396
1397 final TestBSPTree result = new TestBSPTree();
1398 result.getRoot().cut(TestLine.X_AXIS)
1399 .getMinus().cut(TestLine.Y_AXIS);
1400
1401
1402 result.extract(tree.getRoot());
1403
1404
1405 Assertions.assertNotSame(tree.getRoot(), result.getRoot());
1406 Assertions.assertEquals(1, tree.count());
1407 Assertions.assertEquals(1, result.count());
1408
1409 PartitionTestUtils.assertTreeStructure(tree);
1410 PartitionTestUtils.assertTreeStructure(result);
1411 }
1412
1413 @Test
1414 void testExtract_internalNode() {
1415
1416 final TestBSPTree tree = new TestBSPTree();
1417 tree.insert(Arrays.asList(
1418 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
1419 new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)),
1420 new TestLineSegment(new TestPoint2D(1, 2), new TestPoint2D(2, 1)),
1421 new TestLineSegment(new TestPoint2D(-1, 2), new TestPoint2D(-2, 1)),
1422 new TestLineSegment(new TestPoint2D(0, -2), new TestPoint2D(1, -2))
1423 ));
1424
1425 final TestBSPTree result = new TestBSPTree();
1426
1427
1428 result.extract(tree.getRoot().getPlus());
1429
1430
1431 Assertions.assertEquals(7, result.count());
1432
1433 final List<TestLineSegment> resultSegments = getLineSegments(result);
1434 Assertions.assertEquals(3, resultSegments.size());
1435
1436 PartitionTestUtils.assertSegmentsEqual(
1437 new TestLineSegment(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
1438 resultSegments.get(0));
1439 PartitionTestUtils.assertSegmentsEqual(
1440 new TestLineSegment(Double.NEGATIVE_INFINITY, 0, TestLine.Y_AXIS),
1441 resultSegments.get(1));
1442 PartitionTestUtils.assertSegmentsEqual(
1443 new TestLineSegment(0, Double.POSITIVE_INFINITY, new TestLine(new TestPoint2D(0, -2), new TestPoint2D(1, -2))),
1444 resultSegments.get(2));
1445
1446 Assertions.assertEquals(13, tree.count());
1447
1448 final List<TestLineSegment> inputSegment = getLineSegments(tree);
1449 Assertions.assertEquals(6, inputSegment.size());
1450
1451 PartitionTestUtils.assertTreeStructure(tree);
1452 PartitionTestUtils.assertTreeStructure(result);
1453 }
1454
1455 @Test
1456 void testExtract_leafNode() {
1457
1458 final TestBSPTree tree = new TestBSPTree();
1459 tree.insert(Arrays.asList(
1460 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
1461 new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)),
1462 new TestLineSegment(new TestPoint2D(1, 2), new TestPoint2D(2, 1)),
1463 new TestLineSegment(new TestPoint2D(-1, 2), new TestPoint2D(-2, 1)),
1464 new TestLineSegment(new TestPoint2D(0, -2), new TestPoint2D(1, -2))
1465 ));
1466
1467 final TestPoint2D pt = new TestPoint2D(1, 1);
1468
1469 final TestNode node = tree.findNode(pt);
1470 final TestBSPTree result = new TestBSPTree();
1471
1472
1473 result.extract(node);
1474
1475
1476 final TestNode resultNode = result.findNode(pt);
1477 Assertions.assertNotNull(resultNode);
1478 Assertions.assertNotSame(node, resultNode);
1479
1480 Assertions.assertEquals(7, result.count());
1481
1482 final List<TestLineSegment> resultSegments = getLineSegments(result);
1483 Assertions.assertEquals(3, resultSegments.size());
1484
1485 PartitionTestUtils.assertSegmentsEqual(
1486 new TestLineSegment(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
1487 resultSegments.get(0));
1488 PartitionTestUtils.assertSegmentsEqual(
1489 new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.Y_AXIS),
1490 resultSegments.get(1));
1491 PartitionTestUtils.assertSegmentsEqual(
1492 new TestLineSegment(new TestPoint2D(0, 3), new TestPoint2D(3, 0)),
1493 resultSegments.get(2));
1494
1495 Assertions.assertEquals(13, tree.count());
1496
1497 final List<TestLineSegment> inputSegment = getLineSegments(tree);
1498 Assertions.assertEquals(6, inputSegment.size());
1499
1500 PartitionTestUtils.assertTreeStructure(tree);
1501 PartitionTestUtils.assertTreeStructure(result);
1502 }
1503
1504 @Test
1505 void testExtract_extractFromSameTree() {
1506
1507 final TestBSPTree tree = new TestBSPTree();
1508 tree.insert(Arrays.asList(
1509 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
1510 new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)),
1511 new TestLineSegment(new TestPoint2D(1, 2), new TestPoint2D(2, 1)),
1512 new TestLineSegment(new TestPoint2D(-1, 2), new TestPoint2D(-2, 1)),
1513 new TestLineSegment(new TestPoint2D(0, -2), new TestPoint2D(1, -2))
1514 ));
1515
1516 final TestPoint2D pt = new TestPoint2D(1, 1);
1517
1518 final TestNode node = tree.findNode(pt);
1519
1520
1521 tree.extract(node);
1522
1523
1524 final TestNode resultNode = tree.findNode(pt);
1525 Assertions.assertNotNull(resultNode);
1526 Assertions.assertSame(node, resultNode);
1527
1528 Assertions.assertEquals(7, tree.count());
1529
1530 final List<TestLineSegment> resultSegments = getLineSegments(tree);
1531 Assertions.assertEquals(3, resultSegments.size());
1532
1533 PartitionTestUtils.assertSegmentsEqual(
1534 new TestLineSegment(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
1535 resultSegments.get(0));
1536 PartitionTestUtils.assertSegmentsEqual(
1537 new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.Y_AXIS),
1538 resultSegments.get(1));
1539 PartitionTestUtils.assertSegmentsEqual(
1540 new TestLineSegment(new TestPoint2D(0, 3), new TestPoint2D(3, 0)),
1541 resultSegments.get(2));
1542
1543 PartitionTestUtils.assertTreeStructure(tree);
1544 }
1545
1546 @Test
1547 void testTransform_singleNodeTree() {
1548
1549 final TestBSPTree tree = new TestBSPTree();
1550
1551 final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(p.getX(), p.getY() + 2));
1552
1553
1554 tree.transform(t);
1555
1556
1557 Assertions.assertEquals(1, tree.count());
1558 Assertions.assertTrue(tree.getRoot().isLeaf());
1559 }
1560
1561 @Test
1562 void testTransform_singleCut() {
1563
1564 final TestBSPTree tree = new TestBSPTree();
1565 tree.getRoot().insertCut(TestLine.X_AXIS);
1566
1567 final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(p.getX(), p.getY() + 2));
1568
1569
1570 tree.transform(t);
1571
1572
1573 Assertions.assertEquals(3, tree.count());
1574
1575 final List<TestLineSegment> segments = getLineSegments(tree);
1576 Assertions.assertEquals(1, segments.size());
1577
1578 final TestLineSegment seg = segments.get(0);
1579 PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.NEGATIVE_INFINITY, 2), seg.getStartPoint());
1580 PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.POSITIVE_INFINITY, 2), seg.getEndPoint());
1581 }
1582
1583 @Test
1584 void testTransform_multipleCuts() {
1585
1586 final TestBSPTree tree = new TestBSPTree();
1587 tree.insert(Arrays.asList(
1588 new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)),
1589 new TestLineSegment(new TestPoint2D(-1, -1), new TestPoint2D(1, 1)),
1590 new TestLineSegment(new TestPoint2D(3, 1), new TestPoint2D(3, 2))
1591 ));
1592
1593 final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(0.5 * p.getX(), p.getY() + 2));
1594
1595
1596 tree.transform(t);
1597
1598
1599 Assertions.assertEquals(9, tree.count());
1600
1601 final List<TestLineSegment> segments = getLineSegments(tree);
1602 Assertions.assertEquals(4, segments.size());
1603
1604 final TestLineSegment segment1 = segments.get(0);
1605 PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.NEGATIVE_INFINITY, 2), segment1.getStartPoint());
1606 PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.POSITIVE_INFINITY, 2), segment1.getEndPoint());
1607
1608 final TestLineSegment segment2 = segments.get(1);
1609 PartitionTestUtils.assertPointsEqual(new TestPoint2D(0, 2), segment2.getStartPoint());
1610 PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY), segment2.getEndPoint());
1611
1612 final TestLineSegment segment3 = segments.get(2);
1613 PartitionTestUtils.assertPointsEqual(new TestPoint2D(1.5, 2), segment3.getStartPoint());
1614 PartitionTestUtils.assertPointsEqual(new TestPoint2D(1.5, 5), segment3.getEndPoint());
1615
1616 final TestLineSegment segment4 = segments.get(3);
1617 PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.NEGATIVE_INFINITY, Double.NEGATIVE_INFINITY), segment4.getStartPoint());
1618 PartitionTestUtils.assertPointsEqual(new TestPoint2D(0, 2), segment4.getEndPoint());
1619 }
1620
1621 @Test
1622 void testTransform_xAxisReflection() {
1623
1624 final TestBSPTree tree = new TestBSPTree();
1625 tree.insert(Arrays.asList(
1626 new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)),
1627 new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)),
1628 new TestLineSegment(new TestPoint2D(0, 3), new TestPoint2D(3, 0))
1629 ));
1630
1631 final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(-p.getX(), p.getY()));
1632
1633 final Map<TestPoint2D, TestNode> pointNodeMap = createPointNodeMap(tree, -5, 5);
1634
1635
1636 tree.transform(t);
1637
1638
1639 checkTransformedPointNodeMap(tree, t, pointNodeMap);
1640
1641 final List<TestLineSegment> segments = getLineSegments(tree);
1642 Assertions.assertEquals(4, segments.size());
1643 }
1644
1645 @Test
1646 void testTransform_yAxisReflection() {
1647
1648 final TestBSPTree tree = new TestBSPTree();
1649 tree.insert(Arrays.asList(
1650 new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)),
1651 new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)),
1652 new TestLineSegment(new TestPoint2D(0, 3), new TestPoint2D(3, 0))
1653 ));
1654
1655 final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(p.getX(), -p.getY()));
1656
1657 final Map<TestPoint2D, TestNode> pointNodeMap = createPointNodeMap(tree, -5, 5);
1658
1659
1660 tree.transform(t);
1661
1662
1663 checkTransformedPointNodeMap(tree, t, pointNodeMap);
1664
1665 final List<TestLineSegment> segments = getLineSegments(tree);
1666 Assertions.assertEquals(4, segments.size());
1667 }
1668
1669 @Test
1670 void testTransform_xAndYAxisReflection() {
1671
1672 final TestBSPTree tree = new TestBSPTree();
1673 tree.insert(Arrays.asList(
1674 new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)),
1675 new TestLineSegment(new TestPoint2D(0, -1), new TestPoint2D(0, 1)),
1676 new TestLineSegment(new TestPoint2D(0, 3), new TestPoint2D(3, 0))
1677 ));
1678
1679 final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(-p.getX(), -p.getY()));
1680
1681 final Map<TestPoint2D, TestNode> pointNodeMap = createPointNodeMap(tree, -5, 5);
1682
1683
1684 tree.transform(t);
1685
1686
1687 checkTransformedPointNodeMap(tree, t, pointNodeMap);
1688
1689 final List<TestLineSegment> segments = getLineSegments(tree);
1690 Assertions.assertEquals(4, segments.size());
1691 }
1692
1693 @Test
1694 void testTreeString() {
1695
1696 final TestBSPTree tree = new TestBSPTree();
1697 tree.getRoot().cut(TestLine.X_AXIS)
1698 .getMinus().cut(TestLine.Y_AXIS);
1699
1700
1701 final String str = tree.treeString();
1702
1703
1704 final String[] lines = str.split("\n");
1705 Assertions.assertEquals(5, lines.length);
1706 Assertions.assertTrue(lines[0].startsWith("TestNode[cut= TestLineSegment"));
1707 Assertions.assertTrue(lines[1].startsWith(" [-] TestNode[cut= TestLineSegment"));
1708 Assertions.assertEquals(" [-] TestNode[cut= null]", lines[2]);
1709 Assertions.assertEquals(" [+] TestNode[cut= null]", lines[3]);
1710 Assertions.assertEquals(" [+] TestNode[cut= null]", lines[4]);
1711 }
1712
1713 @Test
1714 void testTreeString_emptyTree() {
1715
1716 final TestBSPTree tree = new TestBSPTree();
1717
1718
1719 final String str = tree.treeString();
1720
1721
1722 Assertions.assertEquals("TestNode[cut= null]", str);
1723 }
1724
1725 @Test
1726 void testTreeString_reachesMaxDepth() {
1727
1728 final TestBSPTree tree = new TestBSPTree();
1729 tree.getRoot().cut(TestLine.X_AXIS)
1730 .getMinus().cut(TestLine.Y_AXIS)
1731 .getMinus().cut(new TestLine(new TestPoint2D(-2, 1), new TestPoint2D(0, 1)));
1732
1733
1734 final String str = tree.treeString(1);
1735
1736
1737 final String[] lines = str.split("\n");
1738 Assertions.assertEquals(4, lines.length);
1739 Assertions.assertTrue(lines[0].startsWith("TestNode[cut= TestLineSegment"));
1740 Assertions.assertTrue(lines[1].startsWith(" [-] TestNode[cut= TestLineSegment"));
1741 Assertions.assertEquals(" ...", lines[2]);
1742 Assertions.assertEquals(" [+] TestNode[cut= null]", lines[3]);
1743 }
1744
1745 @Test
1746 void testTreeString_zeroMaxDepth() {
1747
1748 final TestBSPTree tree = new TestBSPTree();
1749 tree.getRoot().cut(TestLine.X_AXIS)
1750 .getMinus().cut(TestLine.Y_AXIS)
1751 .getMinus().cut(new TestLine(new TestPoint2D(-2, 1), new TestPoint2D(0, 1)));
1752
1753
1754 final String str = tree.treeString(0);
1755
1756
1757 final String[] lines = str.split("\n");
1758 Assertions.assertEquals(2, lines.length);
1759 Assertions.assertTrue(lines[0].startsWith("TestNode[cut= TestLineSegment"));
1760 Assertions.assertTrue(lines[1].startsWith(" ..."));
1761 }
1762
1763 @Test
1764 void testTreeString_negativeMaxDepth() {
1765
1766 final TestBSPTree tree = new TestBSPTree();
1767 tree.getRoot().cut(TestLine.X_AXIS)
1768 .getMinus().cut(TestLine.Y_AXIS)
1769 .getMinus().cut(new TestLine(new TestPoint2D(-2, 1), new TestPoint2D(0, 1)));
1770
1771
1772 final String str = tree.treeString(-1);
1773
1774
1775 Assertions.assertEquals("", str);
1776 }
1777
1778 @Test
1779 void testToString() {
1780
1781 final TestBSPTree tree = new TestBSPTree();
1782 tree.getRoot().insertCut(TestLine.Y_AXIS);
1783
1784
1785 final String str = tree.toString();
1786
1787
1788 final String msg = "Unexpected toString() representation: " + str;
1789
1790 Assertions.assertTrue(str.contains("TestBSPTree"), msg);
1791 Assertions.assertTrue(str.contains("count= 3"), msg);
1792 Assertions.assertTrue(str.contains("height= 1"), msg);
1793 }
1794
1795 @Test
1796 void testNodeToString() {
1797
1798 final TestBSPTree tree = new TestBSPTree();
1799 tree.getRoot().cut(TestLine.X_AXIS);
1800
1801
1802 final String str = tree.getRoot().toString();
1803
1804
1805 Assertions.assertTrue(str.contains("TestNode"));
1806 Assertions.assertTrue(str.contains("cut= TestLineSegment"));
1807 }
1808
1809 @Test
1810 void testSplitIntoTree() {
1811
1812 final TestBSPTree tree = new TestBSPTree();
1813 tree.getRoot()
1814 .cut(TestLine.X_AXIS)
1815 .getMinus()
1816 .cut(TestLine.Y_AXIS);
1817
1818 final TestBSPTree minus = new TestBSPTree();
1819 final TestBSPTree plus = new TestBSPTree();
1820
1821 final TestLine splitter = new TestLine(new TestPoint2D(0, 0), new TestPoint2D(-1, 1));
1822
1823
1824 tree.splitIntoTrees(splitter, minus, plus);
1825
1826
1827 final TestLineSegment splitSegment = new TestLineSegment(Double.NEGATIVE_INFINITY,
1828 Double.POSITIVE_INFINITY, splitter);
1829
1830 Assertions.assertEquals(5, tree.count());
1831 Assertions.assertEquals(2, tree.height());
1832
1833 Assertions.assertEquals(5, minus.count());
1834 Assertions.assertEquals(2, minus.height());
1835
1836 final List<TestLineSegment> minusSegments = getLineSegments(minus);
1837 Assertions.assertEquals(2, minusSegments.size());
1838 PartitionTestUtils.assertSegmentsEqual(splitSegment, minusSegments.get(0));
1839 PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(Double.NEGATIVE_INFINITY, 0, TestLine.X_AXIS),
1840 minusSegments.get(1));
1841
1842 Assertions.assertEquals(7, plus.count());
1843 Assertions.assertEquals(3, plus.height());
1844
1845 final List<TestLineSegment> plusSegments = getLineSegments(plus);
1846 Assertions.assertEquals(3, plusSegments.size());
1847 PartitionTestUtils.assertSegmentsEqual(splitSegment, plusSegments.get(0));
1848 PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
1849 plusSegments.get(1));
1850 PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.Y_AXIS),
1851 plusSegments.get(2));
1852 }
1853
1854 @Test
1855 void testSplitIntoTree_minusOnly() {
1856
1857 final TestBSPTree tree = new TestBSPTree();
1858 tree.getRoot()
1859 .cut(TestLine.X_AXIS)
1860 .getMinus()
1861 .cut(TestLine.Y_AXIS);
1862
1863 final TestBSPTree minus = new TestBSPTree();
1864
1865 final TestLine splitter = new TestLine(new TestPoint2D(0, 0), new TestPoint2D(-1, 1));
1866
1867
1868 tree.splitIntoTrees(splitter, minus, null);
1869
1870
1871 final TestLineSegment splitSegment = new TestLineSegment(Double.NEGATIVE_INFINITY,
1872 Double.POSITIVE_INFINITY, splitter);
1873
1874 Assertions.assertEquals(5, tree.count());
1875 Assertions.assertEquals(2, tree.height());
1876
1877 Assertions.assertEquals(5, minus.count());
1878 Assertions.assertEquals(2, minus.height());
1879
1880 final List<TestLineSegment> minusSegments = getLineSegments(minus);
1881 Assertions.assertEquals(2, minusSegments.size());
1882 PartitionTestUtils.assertSegmentsEqual(splitSegment, minusSegments.get(0));
1883 PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(Double.NEGATIVE_INFINITY, 0, TestLine.X_AXIS),
1884 minusSegments.get(1));
1885 }
1886
1887 @Test
1888 void testSplitIntoTree_plusOnly() {
1889
1890 final TestBSPTree tree = new TestBSPTree();
1891 tree.getRoot()
1892 .cut(TestLine.X_AXIS)
1893 .getMinus()
1894 .cut(TestLine.Y_AXIS);
1895
1896 final TestBSPTree plus = new TestBSPTree();
1897
1898 final TestLine splitter = new TestLine(new TestPoint2D(0, 0), new TestPoint2D(-1, 1));
1899
1900
1901 tree.splitIntoTrees(splitter, null, plus);
1902
1903
1904 final TestLineSegment splitSegment = new TestLineSegment(Double.NEGATIVE_INFINITY,
1905 Double.POSITIVE_INFINITY, splitter);
1906
1907 Assertions.assertEquals(5, tree.count());
1908 Assertions.assertEquals(2, tree.height());
1909
1910 Assertions.assertEquals(7, plus.count());
1911 Assertions.assertEquals(3, plus.height());
1912
1913 final List<TestLineSegment> plusSegments = getLineSegments(plus);
1914 Assertions.assertEquals(3, plusSegments.size());
1915 PartitionTestUtils.assertSegmentsEqual(splitSegment, plusSegments.get(0));
1916 PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.X_AXIS),
1917 plusSegments.get(1));
1918 PartitionTestUtils.assertSegmentsEqual(new TestLineSegment(0, Double.POSITIVE_INFINITY, TestLine.Y_AXIS),
1919 plusSegments.get(2));
1920 }
1921
1922 private void assertNodesCopiedRecursive(final TestNode orig, final TestNode copy) {
1923 Assertions.assertNotSame(orig, copy);
1924
1925 Assertions.assertEquals(orig.getCut(), copy.getCut());
1926
1927 if (orig.isLeaf()) {
1928 Assertions.assertNull(copy.getMinus());
1929 Assertions.assertNull(copy.getPlus());
1930 } else {
1931 Assertions.assertNotSame(orig.getMinus(), copy.getMinus());
1932 Assertions.assertNotSame(orig.getPlus(), copy.getPlus());
1933
1934 assertNodesCopiedRecursive(orig.getMinus(), copy.getMinus());
1935 assertNodesCopiedRecursive(orig.getPlus(), copy.getPlus());
1936 }
1937
1938 Assertions.assertEquals(orig.depth(), copy.depth());
1939 Assertions.assertEquals(orig.count(), copy.count());
1940 }
1941
1942 private static List<TestLineSegment> getLineSegments(final TestBSPTree tree) {
1943 return StreamSupport.stream(tree.nodes().spliterator(), false)
1944 .filter(BSPTree.Node::isInternal)
1945 .map(n -> (TestLineSegment) n.getCut())
1946 .collect(Collectors.toList());
1947 }
1948
1949
1950
1951
1952 private static Map<TestPoint2D, TestNode> createPointNodeMap(final TestBSPTree tree, final int min, final int max) {
1953 final Map<TestPoint2D, TestNode> map = new HashMap<>();
1954
1955 for (int x = min; x <= max; ++x) {
1956 for (int y = min; y <= max; ++y) {
1957 final TestPoint2D pt = new TestPoint2D(x, y);
1958 final TestNode node = tree.findNode(pt, FindNodeCutRule.NODE);
1959
1960 map.put(pt, node);
1961 }
1962 }
1963
1964 return map;
1965 }
1966
1967
1968
1969
1970
1971
1972
1973 private static void checkTransformedPointNodeMap(final TestBSPTree transformedTree, final Transform<TestPoint2D> transform,
1974 final Map<TestPoint2D, TestNode> pointNodeMap) {
1975
1976 for (final Map.Entry<TestPoint2D, TestNode> entry : pointNodeMap.entrySet()) {
1977 final TestNode expectedNode = entry.getValue();
1978 final TestPoint2D transformedPt = transform.apply(entry.getKey());
1979
1980 final String msg = "Expected transformed point " + transformedPt + " to resolve to node " + expectedNode;
1981 Assertions.assertSame(expectedNode, transformedTree.findNode(transformedPt, FindNodeCutRule.NODE), msg);
1982 }
1983 }
1984
1985 private static class TestVisitor implements BSPTreeVisitor<TestPoint2D, TestNode> {
1986
1987 private final Order order;
1988
1989 private TestNode terminationNode;
1990
1991 private final List<TestNode> visited = new ArrayList<>();
1992
1993 TestVisitor(final Order order) {
1994 this.order = order;
1995 }
1996
1997 public TestVisitor withTerminationNode(final TestNode newTerminationNode) {
1998 this.terminationNode = newTerminationNode;
1999 return this;
2000 }
2001
2002 @Override
2003 public Result visit(final TestNode node) {
2004 visited.add(node);
2005 return (terminationNode == node) ?
2006 Result.TERMINATE :
2007 Result.CONTINUE;
2008 }
2009
2010 @Override
2011 public Order visitOrder(final TestNode node) {
2012 return order;
2013 }
2014
2015 public List<TestNode> getVisited() {
2016 return visited;
2017 }
2018 }
2019 }