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.Collections;
22 import java.util.List;
23 import java.util.function.Consumer;
24 import java.util.function.Function;
25 import java.util.stream.Stream;
26
27 import org.apache.commons.geometry.core.GeometryTestUtils;
28 import org.apache.commons.geometry.core.RegionLocation;
29 import org.apache.commons.geometry.core.Transform;
30 import org.apache.commons.geometry.core.partitioning.BoundarySource;
31 import org.apache.commons.geometry.core.partitioning.HyperplaneConvexSubset;
32 import org.apache.commons.geometry.core.partitioning.Split;
33 import org.apache.commons.geometry.core.partitioning.SplitLocation;
34 import org.apache.commons.geometry.core.partitioning.bsp.AbstractRegionBSPTree.RegionSizeProperties;
35 import org.apache.commons.geometry.core.partitioning.test.PartitionTestUtils;
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.TestRegionBSPTree;
41 import org.apache.commons.geometry.core.partitioning.test.TestRegionBSPTree.TestRegionNode;
42 import org.apache.commons.geometry.core.partitioning.test.TestTransform2D;
43 import org.junit.jupiter.api.Assertions;
44 import org.junit.jupiter.api.BeforeEach;
45 import org.junit.jupiter.api.Test;
46
47 class AbstractRegionBSPTreeTest {
48
49 private TestRegionBSPTree tree;
50
51 private TestRegionNode root;
52
53 @BeforeEach
54 public void setup() {
55 tree = new TestRegionBSPTree();
56 root = tree.getRoot();
57 }
58
59 @Test
60 void testDefaultConstructor() {
61
62 Assertions.assertNotNull(root);
63 Assertions.assertNull(root.getParent());
64
65 PartitionTestUtils.assertIsLeafNode(root);
66 Assertions.assertFalse(root.isPlus());
67 Assertions.assertFalse(root.isMinus());
68
69 Assertions.assertSame(tree, root.getTree());
70
71 Assertions.assertEquals(RegionLocation.INSIDE, root.getLocation());
72 }
73
74 @Test
75 void testParameterizedConstructor_true() {
76
77 tree = new TestRegionBSPTree(true);
78 root = tree.getRoot();
79
80
81 Assertions.assertNotNull(root);
82 Assertions.assertNull(root.getParent());
83
84 PartitionTestUtils.assertIsLeafNode(root);
85 Assertions.assertFalse(root.isPlus());
86 Assertions.assertFalse(root.isMinus());
87
88 Assertions.assertSame(tree, root.getTree());
89
90 Assertions.assertEquals(RegionLocation.INSIDE, root.getLocation());
91 }
92
93 @Test
94 void testParameterizedConstructor_false() {
95
96 tree = new TestRegionBSPTree(false);
97 root = tree.getRoot();
98
99
100 Assertions.assertNotNull(root);
101 Assertions.assertNull(root.getParent());
102
103 PartitionTestUtils.assertIsLeafNode(root);
104 Assertions.assertFalse(root.isPlus());
105 Assertions.assertFalse(root.isMinus());
106
107 Assertions.assertSame(tree, root.getTree());
108
109 Assertions.assertEquals(RegionLocation.OUTSIDE, root.getLocation());
110 }
111
112 @Test
113 void testInsert_hyperplaneSubsets_mixedCutRules() {
114
115 checkMixedCutRuleInsertion(segs -> {
116 tree.insert(new TestLineSegmentCollection(Collections.singletonList(segs[0])), RegionCutRule.PLUS_INSIDE);
117 tree.insert(new TestLineSegmentCollection(Collections.singletonList(segs[1])));
118 tree.insert(new TestLineSegmentCollection(Collections.singletonList(segs[2])), RegionCutRule.PLUS_INSIDE);
119 tree.insert(new TestLineSegmentCollection(Collections.singletonList(segs[3])), RegionCutRule.MINUS_INSIDE);
120 tree.insert(new TestLineSegmentCollection(Collections.singletonList(segs[4])), RegionCutRule.INHERIT);
121 });
122
123 }
124
125 @Test
126 void testInsert_hyperplaneConvexSubsets_mixedCutRules() {
127
128 checkMixedCutRuleInsertion(segs -> {
129 tree.insert(segs[0], RegionCutRule.PLUS_INSIDE);
130 tree.insert(segs[1]);
131 tree.insert(segs[2], RegionCutRule.PLUS_INSIDE);
132 tree.insert(segs[3], RegionCutRule.MINUS_INSIDE);
133 tree.insert(segs[4], RegionCutRule.INHERIT);
134 });
135 }
136
137 @Test
138 void testInsert_hyperplaneConvexSubsetList_mixedCutRules() {
139
140 checkMixedCutRuleInsertion(segs -> {
141 tree.insert(Collections.singletonList(segs[0]), RegionCutRule.PLUS_INSIDE);
142 tree.insert(Collections.singletonList(segs[1]));
143 tree.insert(Collections.singletonList(segs[2]), RegionCutRule.PLUS_INSIDE);
144 tree.insert(Collections.singletonList(segs[3]), RegionCutRule.MINUS_INSIDE);
145 tree.insert(Collections.singletonList(segs[4]), RegionCutRule.INHERIT);
146 });
147 }
148
149 @Test
150 void testInsert_boundarySource_mixedCutRules() {
151
152 final Function<TestLineSegment, BoundarySource<TestLineSegment>> factory = seg -> () -> Stream.of(seg);
153
154
155 checkMixedCutRuleInsertion(segs -> {
156 tree.insert(factory.apply(segs[0]), RegionCutRule.PLUS_INSIDE);
157 tree.insert(factory.apply(segs[1]));
158 tree.insert(factory.apply(segs[2]), RegionCutRule.PLUS_INSIDE);
159 tree.insert(factory.apply(segs[3]), RegionCutRule.MINUS_INSIDE);
160 tree.insert(factory.apply(segs[4]), RegionCutRule.INHERIT);
161 });
162 }
163
164
165
166
167 private void checkMixedCutRuleInsertion(final Consumer<TestLineSegment[]> fn) {
168
169 final TestLineSegment bottom = new TestLineSegment(new TestPoint2D(1, 0), new TestPoint2D(0, 0));
170 final TestLineSegment right = new TestLineSegment(new TestPoint2D(1, 0), new TestPoint2D(1, 1));
171 final TestLineSegment top = new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(1, 1));
172 final TestLineSegment left = new TestLineSegment(new TestPoint2D(0, 1), new TestPoint2D(0, 0));
173 final TestLineSegment diag = new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 1));
174
175 tree = emptyTree();
176
177
178 fn.accept(new TestLineSegment[] {
179 bottom,
180 right,
181 top,
182 left,
183 diag
184 });
185
186
187 TestRegionNode node = tree.getRoot();
188 Assertions.assertEquals(RegionLocation.OUTSIDE, node.getLocation());
189
190 Assertions.assertEquals(RegionLocation.OUTSIDE, node.getMinus().getLocation());
191 Assertions.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
192
193 node = node.getPlus();
194 Assertions.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
195 Assertions.assertEquals(RegionLocation.OUTSIDE, node.getPlus().getLocation());
196
197 node = node.getMinus();
198 Assertions.assertEquals(RegionLocation.OUTSIDE, node.getMinus().getLocation());
199 Assertions.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
200
201 node = node.getPlus();
202 Assertions.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
203 Assertions.assertEquals(RegionLocation.OUTSIDE, node.getPlus().getLocation());
204
205 node = node.getMinus();
206 Assertions.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
207 Assertions.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
208 }
209
210 @Test
211 void testGetLocation_emptyRoot() {
212
213 Assertions.assertEquals(RegionLocation.INSIDE, root.getLocation());
214 }
215
216 @Test
217 void testGetLocation_singleCut() {
218
219 root.insertCut(TestLine.X_AXIS);
220
221
222 Assertions.assertEquals(RegionLocation.INSIDE, root.getLocation());
223 Assertions.assertFalse(root.isInside());
224 Assertions.assertFalse(root.isOutside());
225
226 final TestRegionNode minus = root.getMinus();
227 Assertions.assertEquals(RegionLocation.INSIDE, minus.getLocation());
228 Assertions.assertTrue(minus.isInside());
229 Assertions.assertFalse(minus.isOutside());
230
231 final TestRegionNode plus = root.getPlus();
232 Assertions.assertEquals(RegionLocation.OUTSIDE, plus.getLocation());
233 Assertions.assertFalse(plus.isInside());
234 Assertions.assertTrue(plus.isOutside());
235 }
236
237 @Test
238 void testGetLocation_multipleCuts() {
239
240 tree.insert(Arrays.asList(
241 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
242 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1)),
243 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, -1))));
244
245
246 Assertions.assertEquals(RegionLocation.INSIDE, root.getLocation());
247
248 final TestRegionNode plus = root.getPlus();
249 Assertions.assertEquals(RegionLocation.OUTSIDE, plus.getLocation());
250
251 final TestRegionNode plusPlus = plus.getPlus();
252 Assertions.assertEquals(RegionLocation.OUTSIDE, plusPlus.getLocation());
253
254 final TestRegionNode plusMinus = plus.getMinus();
255 Assertions.assertEquals(RegionLocation.INSIDE, plusMinus.getLocation());
256
257 final TestRegionNode minus = root.getMinus();
258 Assertions.assertEquals(RegionLocation.INSIDE, minus.getLocation());
259
260 final TestRegionNode minusPlus = minus.getPlus();
261 Assertions.assertEquals(RegionLocation.OUTSIDE, minusPlus.getLocation());
262
263 final TestRegionNode minusMinus = minus.getMinus();
264 Assertions.assertEquals(RegionLocation.INSIDE, minusMinus.getLocation());
265 }
266
267 @Test
268 void testSetLocation() {
269
270 tree = emptyTree();
271 tree.insert(TestLine.Y_AXIS.span());
272
273 final TestRegionNode node = tree.getRoot().getMinus();
274
275
276 node.setLocation(RegionLocation.OUTSIDE);
277
278
279 Assertions.assertEquals(RegionLocation.OUTSIDE, node.getLocation());
280 Assertions.assertTrue(tree.isEmpty());
281 }
282
283 @Test
284 void testSetLocation_invalidatesRegionProperties() {
285
286 tree = emptyTree();
287 tree.insert(TestLine.Y_AXIS.span());
288
289 final TestRegionNode node = tree.getRoot().getMinus();
290
291 final RegionSizeProperties<TestPoint2D> prevProps = tree.getRegionSizeProperties();
292
293
294 node.setLocation(RegionLocation.OUTSIDE);
295
296
297 Assertions.assertNotSame(prevProps, tree.getRegionSizeProperties());
298 }
299
300 @Test
301 void testSetLocation_noChange_doesNotInvalidateTree() {
302
303 tree = emptyTree();
304 tree.insert(TestLine.Y_AXIS.span());
305
306 final TestRegionNode node = tree.getRoot().getMinus();
307
308 final RegionSizeProperties<TestPoint2D> prevProps = tree.getRegionSizeProperties();
309
310
311 node.setLocation(RegionLocation.INSIDE);
312
313
314 Assertions.assertSame(prevProps, tree.getRegionSizeProperties());
315 }
316
317 @Test
318 void testSetLocation_invalidArgs() {
319
320 GeometryTestUtils.assertThrowsWithMessage(() -> root.setLocation(null),
321 IllegalArgumentException.class, "Invalid node location: null");
322 GeometryTestUtils.assertThrowsWithMessage(() -> root.setLocation(RegionLocation.BOUNDARY),
323 IllegalArgumentException.class, "Invalid node location: BOUNDARY");
324 }
325
326 @Test
327 void testCondense() {
328
329 tree = emptyTree();
330 tree.insert(TestLine.Y_AXIS.span(), RegionCutRule.MINUS_INSIDE);
331 tree.insert(TestLine.X_AXIS.span(), RegionCutRule.INHERIT);
332
333
334 final boolean result = tree.condense();
335
336
337 Assertions.assertTrue(result);
338
339 Assertions.assertEquals(3, tree.count());
340 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getLocation());
341 Assertions.assertEquals(RegionLocation.INSIDE, tree.getRoot().getMinus().getLocation());
342 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getPlus().getLocation());
343 }
344
345 @Test
346 void testCondense_alreadyCondensed() {
347
348 tree = emptyTree();
349 tree.insert(TestLine.Y_AXIS.span(), RegionCutRule.MINUS_INSIDE);
350
351
352 final boolean result = tree.condense();
353
354
355 Assertions.assertFalse(result);
356
357 Assertions.assertEquals(3, tree.count());
358 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getLocation());
359 Assertions.assertEquals(RegionLocation.INSIDE, tree.getRoot().getMinus().getLocation());
360 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getPlus().getLocation());
361 }
362
363 @Test
364 void testCondense_invalidatesTreeWhenChanged() {
365
366 tree = emptyTree();
367 tree.insert(TestLine.Y_AXIS.span(), RegionCutRule.MINUS_INSIDE);
368 tree.insert(TestLine.X_AXIS.span(), RegionCutRule.INHERIT);
369
370 final RegionSizeProperties<TestPoint2D> prevProps = tree.getRegionSizeProperties();
371
372
373 final boolean result = tree.condense();
374
375
376 Assertions.assertTrue(result);
377
378 Assertions.assertNotSame(prevProps, tree.getRegionSizeProperties());
379 }
380
381 @Test
382 void testCondense_doesNotInvalidateTreeWhenNotChanged() {
383
384 tree = emptyTree();
385
386 final RegionSizeProperties<TestPoint2D> prevProps = tree.getRegionSizeProperties();
387
388
389 final boolean result = tree.condense();
390
391
392 Assertions.assertFalse(result);
393
394 Assertions.assertSame(prevProps, tree.getRegionSizeProperties());
395 }
396
397 @Test
398 void testCut_nodeMethod() {
399
400 tree = emptyTree();
401
402
403 tree.getRoot().cut(TestLine.X_AXIS, RegionCutRule.PLUS_INSIDE)
404 .getPlus()
405 .cut(TestLine.Y_AXIS, RegionCutRule.MINUS_INSIDE)
406 .getMinus()
407 .cut(new TestLine(TestPoint2D.ZERO, new TestPoint2D(-1, -1)), RegionCutRule.INHERIT);
408
409
410 TestRegionNode node = tree.getRoot();
411 Assertions.assertEquals(RegionLocation.OUTSIDE, node.getLocation());
412
413 Assertions.assertEquals(RegionLocation.OUTSIDE, node.getMinus().getLocation());
414 Assertions.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
415
416 node = node.getPlus();
417 Assertions.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
418 Assertions.assertEquals(RegionLocation.OUTSIDE, node.getPlus().getLocation());
419
420 node = node.getMinus();
421 Assertions.assertEquals(RegionLocation.INSIDE, node.getMinus().getLocation());
422 Assertions.assertEquals(RegionLocation.INSIDE, node.getPlus().getLocation());
423 }
424
425 @Test
426 void testBoundaries_fullAndEmpty() {
427
428 tree.setFull();
429 Assertions.assertFalse(tree.boundaries().iterator().hasNext());
430
431 tree.setEmpty();
432 Assertions.assertFalse(tree.boundaries().iterator().hasNext());
433 }
434
435 @Test
436 void testBoundaries_finite() {
437
438 insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
439
440
441 final List<TestLineSegment> segments = new ArrayList<>();
442 for (final HyperplaneConvexSubset<TestPoint2D> sub : tree.boundaries()) {
443 segments.add((TestLineSegment) sub);
444 }
445
446
447 Assertions.assertEquals(4, segments.size());
448
449 assertContainsSegment(segments, new TestPoint2D(0, 0), new TestPoint2D(1, 0));
450 assertContainsSegment(segments, new TestPoint2D(1, 0), new TestPoint2D(1, 1));
451 assertContainsSegment(segments, new TestPoint2D(1, 1), new TestPoint2D(0, 1));
452 assertContainsSegment(segments, new TestPoint2D(0, 1), new TestPoint2D(0, 0));
453 }
454
455 @Test
456 void testBoundaries_finite_inverted() {
457
458 insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
459 tree.complement();
460
461
462 final List<TestLineSegment> segments = new ArrayList<>();
463 for (final HyperplaneConvexSubset<TestPoint2D> sub : tree.boundaries()) {
464 segments.add((TestLineSegment) sub);
465 }
466
467
468 Assertions.assertEquals(4, segments.size());
469
470 assertContainsSegment(segments, new TestPoint2D(0, 0), new TestPoint2D(0, 1));
471 assertContainsSegment(segments, new TestPoint2D(0, 1), new TestPoint2D(1, 1));
472 assertContainsSegment(segments, new TestPoint2D(1, 1), new TestPoint2D(1, 0));
473 assertContainsSegment(segments, new TestPoint2D(1, 0), new TestPoint2D(0, 0));
474 }
475
476 @Test
477 void testGetBoundaries_fullAndEmpty() {
478
479 tree.setFull();
480 Assertions.assertEquals(0, tree.getBoundaries().size());
481
482 tree.setEmpty();
483 Assertions.assertEquals(0, tree.getBoundaries().size());
484 }
485
486 @Test
487 void testGetBoundaries_finite() {
488
489 insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
490
491
492 final List<TestLineSegment> segments = new ArrayList<>();
493 for (final HyperplaneConvexSubset<TestPoint2D> sub : tree.getBoundaries()) {
494 segments.add((TestLineSegment) sub);
495 }
496
497
498 Assertions.assertEquals(4, segments.size());
499
500 assertContainsSegment(segments, new TestPoint2D(0, 0), new TestPoint2D(1, 0));
501 assertContainsSegment(segments, new TestPoint2D(1, 0), new TestPoint2D(1, 1));
502 assertContainsSegment(segments, new TestPoint2D(1, 1), new TestPoint2D(0, 1));
503 assertContainsSegment(segments, new TestPoint2D(0, 1), new TestPoint2D(0, 0));
504 }
505
506 @Test
507 void testGetBoundaries_finite_inverted() {
508
509 insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
510 tree.complement();
511
512
513 final List<TestLineSegment> segments = new ArrayList<>();
514 for (final HyperplaneConvexSubset<TestPoint2D> sub : tree.getBoundaries()) {
515 segments.add((TestLineSegment) sub);
516 }
517
518
519 Assertions.assertEquals(4, segments.size());
520
521 assertContainsSegment(segments, new TestPoint2D(0, 0), new TestPoint2D(0, 1));
522 assertContainsSegment(segments, new TestPoint2D(0, 1), new TestPoint2D(1, 1));
523 assertContainsSegment(segments, new TestPoint2D(1, 1), new TestPoint2D(1, 0));
524 assertContainsSegment(segments, new TestPoint2D(1, 0), new TestPoint2D(0, 0));
525 }
526
527 @Test
528 void testClassify() {
529
530 insertSkewedBowtie(tree);
531
532
533 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(3, 1)));
534 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-3, -1)));
535
536 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(-3, 1)));
537 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(3, -1)));
538
539 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(4, 5)));
540 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-4, -5)));
541
542 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(5, 0)));
543 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(4, 0)));
544 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(3, 0)));
545 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(2, 0)));
546 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(1, 0)));
547 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(0, 0)));
548 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-1, 0)));
549 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-2, 0)));
550 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-3, 0)));
551 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-4, 0)));
552 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(-5, 0)));
553 }
554
555 @Test
556 void testClassify_emptyTree() {
557
558 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(TestPoint2D.ZERO));
559 }
560
561 @Test
562 void testClassify_NaN() {
563
564 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(0, Double.NaN)));
565 }
566
567 @Test
568 void testContains() {
569
570 insertSkewedBowtie(tree);
571
572
573 Assertions.assertTrue(tree.contains(new TestPoint2D(3, 1)));
574 Assertions.assertTrue(tree.contains(new TestPoint2D(-3, -1)));
575
576 Assertions.assertFalse(tree.contains(new TestPoint2D(-3, 1)));
577 Assertions.assertFalse(tree.contains(new TestPoint2D(3, -1)));
578
579 Assertions.assertTrue(tree.contains(new TestPoint2D(4, 5)));
580 Assertions.assertTrue(tree.contains(new TestPoint2D(-4, -5)));
581
582 Assertions.assertFalse(tree.contains(new TestPoint2D(5, 0)));
583
584 Assertions.assertTrue(tree.contains(new TestPoint2D(4, 0)));
585 Assertions.assertTrue(tree.contains(new TestPoint2D(3, 0)));
586 Assertions.assertTrue(tree.contains(new TestPoint2D(2, 0)));
587 Assertions.assertTrue(tree.contains(new TestPoint2D(1, 0)));
588 Assertions.assertTrue(tree.contains(new TestPoint2D(0, 0)));
589 Assertions.assertTrue(tree.contains(new TestPoint2D(-1, 0)));
590 Assertions.assertTrue(tree.contains(new TestPoint2D(-2, 0)));
591 Assertions.assertTrue(tree.contains(new TestPoint2D(-3, 0)));
592 Assertions.assertTrue(tree.contains(new TestPoint2D(-4, 0)));
593
594 Assertions.assertFalse(tree.contains(new TestPoint2D(-5, 0)));
595 }
596
597 @Test
598 void testSetFull() {
599
600 insertSkewedBowtie(tree);
601
602
603 tree.setFull();
604
605
606 Assertions.assertTrue(tree.isFull());
607 Assertions.assertFalse(tree.isEmpty());
608
609 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(TestPoint2D.ZERO));
610 Assertions.assertTrue(tree.contains(TestPoint2D.ZERO));
611 }
612
613 @Test
614 void testSetEmpty() {
615
616 insertSkewedBowtie(tree);
617
618
619 tree.setEmpty();
620
621
622 Assertions.assertFalse(tree.isFull());
623 Assertions.assertTrue(tree.isEmpty());
624
625 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(TestPoint2D.ZERO));
626 Assertions.assertFalse(tree.contains(TestPoint2D.ZERO));
627 }
628
629 @Test
630 void testGetRegionSizeProperties_cachesValueBasedOnVersion() {
631
632 final RegionSizeProperties<TestPoint2D> first = tree.getRegionSizeProperties();
633 final RegionSizeProperties<TestPoint2D> second = tree.getRegionSizeProperties();
634 tree.getRoot().cut(TestLine.X_AXIS);
635 final RegionSizeProperties<TestPoint2D> third = tree.getRegionSizeProperties();
636
637
638 Assertions.assertSame(first, second);
639 Assertions.assertNotSame(second, third);
640
641 Assertions.assertEquals(1234, first.getSize(), PartitionTestUtils.EPS);
642 PartitionTestUtils.assertPointsEqual(new TestPoint2D(12, 34), first.getCentroid());
643 }
644
645 @Test
646 void testGetSize() {
647
648
649 Assertions.assertEquals(1234, tree.getSize(), PartitionTestUtils.EPS);
650 }
651
652 @Test
653 void testGetCentroid() {
654
655
656 PartitionTestUtils.assertPointsEqual(new TestPoint2D(12, 34), tree.getCentroid());
657 }
658
659 @Test
660 void testGetBoundarySize_fullAndEmpty() {
661
662 Assertions.assertEquals(0.0, fullTree().getBoundarySize(), PartitionTestUtils.EPS);
663 Assertions.assertEquals(0.0, emptyTree().getBoundarySize(), PartitionTestUtils.EPS);
664 }
665
666 @Test
667 void testGetBoundarySize_infinite() {
668
669 final TestRegionBSPTree halfPos = new TestRegionBSPTree(true);
670 halfPos.getRoot().cut(TestLine.X_AXIS);
671
672 final TestRegionBSPTree halfPosComplement = new TestRegionBSPTree(true);
673 halfPosComplement.complement(halfPos);
674
675
676 Assertions.assertEquals(Double.POSITIVE_INFINITY, halfPos.getBoundarySize(), PartitionTestUtils.EPS);
677 Assertions.assertEquals(Double.POSITIVE_INFINITY, halfPosComplement.getBoundarySize(), PartitionTestUtils.EPS);
678 }
679
680 @Test
681 void testGetBoundarySize_alignedCuts() {
682
683 final TestPoint2D p0 = TestPoint2D.ZERO;
684 final TestPoint2D p1 = new TestPoint2D(0, 3);
685
686 TestRegionNode node = tree.getRoot();
687
688 tree.cutNode(node, new TestLineSegment(p0, p1));
689 node = node.getMinus();
690
691 tree.cutNode(node, new TestLineSegment(0, 0, new TestLine(p1, new TestPoint2D(-1, 3))));
692 node = node.getMinus();
693
694 tree.cutNode(node, new TestLineSegment(p1, p0));
695 node = node.getMinus();
696
697 tree.cutNode(node, new TestLineSegment(0, 0, new TestLine(p0, new TestPoint2D(1, 3))));
698
699
700 Assertions.assertEquals(6, tree.getBoundarySize(), PartitionTestUtils.EPS);
701 }
702
703 @Test
704 void testGetBoundarySize_box() {
705
706 insertBox(tree, new TestPoint2D(2, 2), new TestPoint2D(4, 1));
707
708
709 Assertions.assertEquals(6.0, tree.getBoundarySize(), PartitionTestUtils.EPS);
710 }
711
712 @Test
713 void testGetBoundarySize_boxComplement() {
714
715 insertBox(tree, new TestPoint2D(2, 2), new TestPoint2D(4, 1));
716 tree.complement();
717
718
719 Assertions.assertEquals(6.0, tree.getBoundarySize(), PartitionTestUtils.EPS);
720 }
721
722 @Test
723 void testGetBoundarySize_recomputesAfterChange() {
724
725 insertBox(tree, new TestPoint2D(2, 2), new TestPoint2D(4, 1));
726
727
728 final double first = tree.getBoundarySize();
729 tree.insert(new TestLineSegment(new TestPoint2D(3, 1), new TestPoint2D(3, 2)));
730
731 final double second = tree.getBoundarySize();
732 final double third = tree.getBoundarySize();
733
734
735 Assertions.assertEquals(6.0, first, PartitionTestUtils.EPS);
736 Assertions.assertEquals(4.0, second, PartitionTestUtils.EPS);
737 Assertions.assertEquals(4.0, third, PartitionTestUtils.EPS);
738 }
739
740 @Test
741 void testGetCutBoundary_emptyTree() {
742
743 final RegionCutBoundary<TestPoint2D> boundary = root.getCutBoundary();
744
745
746 Assertions.assertNull(boundary);
747 }
748
749 @Test
750 void testGetCutBoundary_singleCut() {
751
752 tree.insert(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
753
754
755 final RegionCutBoundary<TestPoint2D> boundary = root.getCutBoundary();
756
757
758 Assertions.assertTrue(boundary.getInsideFacing().isEmpty());
759
760 assertCutBoundarySegment(boundary.getOutsideFacing(),
761 new TestPoint2D(Double.NEGATIVE_INFINITY, 0.0), new TestPoint2D(Double.POSITIVE_INFINITY, 0.0));
762 }
763
764 @Test
765 void testGetCutBoundary_singleCut_leafNode() {
766
767 tree.insert(new TestLineSegment(new TestPoint2D(0, 0), new TestPoint2D(1, 0)));
768
769
770 final RegionCutBoundary<TestPoint2D> boundary = root.getMinus().getCutBoundary();
771
772
773 Assertions.assertNull(boundary);
774 }
775
776 @Test
777 void testGetCutBoundary_singleCorner() {
778
779 tree.insert(new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)));
780 tree.insert(new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1)));
781
782
783 final RegionCutBoundary<TestPoint2D> rootBoundary = root.getCutBoundary();
784
785 Assertions.assertTrue(rootBoundary.getInsideFacing().isEmpty());
786 assertCutBoundarySegment(rootBoundary.getOutsideFacing(),
787 new TestPoint2D(Double.NEGATIVE_INFINITY, 0.0), TestPoint2D.ZERO);
788
789 final RegionCutBoundary<TestPoint2D> childBoundary = tree.getRoot().getMinus().getCutBoundary();
790 Assertions.assertTrue(childBoundary.getInsideFacing().isEmpty());
791 assertCutBoundarySegment(childBoundary.getOutsideFacing(),
792 TestPoint2D.ZERO, new TestPoint2D(0.0, Double.POSITIVE_INFINITY));
793 }
794
795 @Test
796 void testGetCutBoundary_leafNode() {
797
798 tree.insert(new TestLineSegment(new TestPoint2D(-1, 0), new TestPoint2D(1, 0)));
799 tree.insert(new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1)));
800
801
802 Assertions.assertNull(root.getPlus().getCutBoundary());
803 Assertions.assertNull(root.getMinus().getMinus().getCutHyperplane());
804 Assertions.assertNull(root.getMinus().getPlus().getCutHyperplane());
805 }
806
807 @Test
808 void testFullEmpty_fullTree() {
809
810 Assertions.assertTrue(tree.isFull());
811 Assertions.assertFalse(tree.isEmpty());
812 Assertions.assertEquals(RegionLocation.INSIDE, tree.getRoot().getLocation());
813 }
814
815 @Test
816 void testFullEmpty_emptyTree() {
817
818 tree.complement();
819
820
821 Assertions.assertFalse(tree.isFull());
822 Assertions.assertTrue(tree.isEmpty());
823 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getLocation());
824 }
825
826 @Test
827 void testTransform_noCuts() {
828
829 final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(p.getX(), p.getY() + 2));
830
831
832 tree.transform(t);
833
834
835 Assertions.assertTrue(tree.isFull());
836 Assertions.assertFalse(tree.isEmpty());
837
838 PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE, TestPoint2D.ZERO);
839 }
840
841 @Test
842 void testTransform_singleCut() {
843
844 tree.getRoot().insertCut(TestLine.X_AXIS);
845
846 final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(p.getX(), p.getY() + 2));
847
848
849 tree.transform(t);
850
851
852 Assertions.assertFalse(tree.isFull());
853 Assertions.assertFalse(tree.isEmpty());
854
855 PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
856 new TestPoint2D(0, -1), TestPoint2D.ZERO, new TestPoint2D(0, 1));
857
858 PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY, new TestPoint2D(0, 2));
859
860 PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
861 new TestPoint2D(0, 3), new TestPoint2D(0, 4));
862 }
863
864 @Test
865 void testTransform_multipleCuts() {
866
867 insertSkewedBowtie(tree);
868
869 final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(0.5 * p.getX(), p.getY() + 5));
870
871
872 tree.transform(t);
873
874
875 Assertions.assertFalse(tree.isFull());
876 Assertions.assertFalse(tree.isEmpty());
877
878 PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
879 new TestPoint2D(0, 5), new TestPoint2D(-1, 4), new TestPoint2D(1, 6));
880
881 PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
882 new TestPoint2D(-2, 4), new TestPoint2D(2, 6));
883
884 PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
885 new TestPoint2D(-3, 5), new TestPoint2D(3, 5));
886 }
887
888 @Test
889 void testTransform_xAxisReflection() {
890
891 insertSkewedBowtie(tree);
892
893 final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(-p.getX(), p.getY()));
894
895
896 tree.transform(t);
897
898
899 Assertions.assertFalse(tree.isFull());
900 Assertions.assertFalse(tree.isEmpty());
901
902 PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
903 TestPoint2D.ZERO, new TestPoint2D(-1, 1), new TestPoint2D(1, -1));
904
905 PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
906 new TestPoint2D(0, 1), new TestPoint2D(0, -1),
907 new TestPoint2D(-4, 0), new TestPoint2D(4, 0));
908
909 PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
910 new TestPoint2D(1, 1), new TestPoint2D(-1, -1));
911 }
912
913 @Test
914 void testTransform_yAxisReflection() {
915
916 insertSkewedBowtie(tree);
917
918 final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(p.getX(), -p.getY()));
919
920
921 tree.transform(t);
922
923
924 Assertions.assertFalse(tree.isFull());
925 Assertions.assertFalse(tree.isEmpty());
926
927 PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
928 TestPoint2D.ZERO, new TestPoint2D(1, -1), new TestPoint2D(-1, 1));
929
930 PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
931 new TestPoint2D(0, 1), new TestPoint2D(0, -1),
932 new TestPoint2D(-4, 0), new TestPoint2D(4, 0));
933
934 PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
935 new TestPoint2D(-1, -1), new TestPoint2D(1, 1));
936 }
937
938 @Test
939 void testTransform_xAndYAxisReflection() {
940
941 insertSkewedBowtie(tree);
942
943 final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(-p.getX(), -p.getY()));
944
945
946 tree.transform(t);
947
948
949 Assertions.assertFalse(tree.isFull());
950 Assertions.assertFalse(tree.isEmpty());
951
952 PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
953 TestPoint2D.ZERO, new TestPoint2D(1, 1), new TestPoint2D(-1, -1));
954
955 PartitionTestUtils.assertPointLocations(tree, RegionLocation.BOUNDARY,
956 new TestPoint2D(0, 1), new TestPoint2D(0, -1),
957 new TestPoint2D(-4, 0), new TestPoint2D(4, 0));
958
959 PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
960 new TestPoint2D(-1, 1), new TestPoint2D(1, -1));
961 }
962
963 @Test
964 void testTransform_resetsCutBoundary() {
965
966 insertSkewedBowtie(tree);
967
968 final TestRegionNode node = tree.findNode(new TestPoint2D(1, 1)).getParent();
969
970
971 final Transform<TestPoint2D> t = new TestTransform2D(p -> new TestPoint2D(0.5 * p.getX(), p.getY() + 5));
972
973
974 final RegionCutBoundary<TestPoint2D> origBoundary = node.getCutBoundary();
975
976 tree.transform(t);
977
978 final RegionCutBoundary<TestPoint2D> resultBoundary = node.getCutBoundary();
979
980
981 Assertions.assertNotSame(origBoundary, resultBoundary);
982
983 assertCutBoundarySegment(origBoundary.getOutsideFacing(), new TestPoint2D(4, 5), new TestPoint2D(-1, 0));
984
985 assertCutBoundarySegment(resultBoundary.getOutsideFacing(), new TestPoint2D(2, 10), new TestPoint2D(-0.5, 5));
986 }
987
988 @Test
989 void testComplement_rootOnly() {
990
991 tree.complement();
992
993
994 Assertions.assertTrue(tree.isEmpty());
995 Assertions.assertFalse(tree.isFull());
996
997 Assertions.assertEquals(RegionLocation.OUTSIDE, root.getLocation());
998 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(TestPoint2D.ZERO));
999 }
1000
1001 @Test
1002 void testComplement_singleCut() {
1003
1004 root.insertCut(TestLine.X_AXIS);
1005
1006
1007 tree.complement();
1008
1009
1010 Assertions.assertFalse(tree.isEmpty());
1011 Assertions.assertFalse(tree.isFull());
1012
1013 Assertions.assertEquals(RegionLocation.OUTSIDE, root.getMinus().getLocation());
1014 Assertions.assertEquals(RegionLocation.INSIDE, root.getPlus().getLocation());
1015
1016 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(0, 1)));
1017 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(TestPoint2D.ZERO));
1018 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(0, -1)));
1019 }
1020
1021 @Test
1022 void testComplement_skewedBowtie() {
1023
1024 insertSkewedBowtie(tree);
1025
1026
1027 tree.complement();
1028
1029
1030 Assertions.assertFalse(tree.isEmpty());
1031 Assertions.assertFalse(tree.isFull());
1032
1033 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(3, 1)));
1034 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(-3, -1)));
1035
1036 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-3, 1)));
1037 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(3, -1)));
1038
1039 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(4, 5)));
1040 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-4, -5)));
1041
1042 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(5, 0)));
1043 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(4, 0)));
1044 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(3, 0)));
1045 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(2, 0)));
1046 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(1, 0)));
1047 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(0, 0)));
1048 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-1, 0)));
1049 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-2, 0)));
1050 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-3, 0)));
1051 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-4, 0)));
1052 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-5, 0)));
1053 }
1054
1055 @Test
1056 void testComplement_addCutAfterComplement() {
1057
1058 tree.insert(new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)));
1059 tree.complement();
1060
1061
1062 tree.insert(new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1)));
1063
1064
1065 Assertions.assertFalse(tree.isEmpty());
1066 Assertions.assertFalse(tree.isFull());
1067
1068 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(TestPoint2D.ZERO));
1069
1070 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(1, 1)));
1071 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-1, 1)));
1072 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(1, -1)));
1073 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-1, -1)));
1074 }
1075
1076 @Test
1077 void testComplement_clearCutAfterComplement() {
1078
1079 tree.insert(Arrays.asList(
1080 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
1081 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1))
1082 ));
1083 tree.complement();
1084
1085
1086 root.getMinus().clearCut();
1087
1088
1089 Assertions.assertFalse(tree.isEmpty());
1090 Assertions.assertFalse(tree.isFull());
1091
1092 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(TestPoint2D.ZERO));
1093
1094 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(1, 1)));
1095 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(-1, 1)));
1096 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(1, -1)));
1097 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-1, -1)));
1098 }
1099
1100 @Test
1101 void testComplement_clearRootAfterComplement() {
1102
1103 tree.insert(Arrays.asList(
1104 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
1105 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1))
1106 ));
1107 tree.complement();
1108
1109
1110 root.clearCut();
1111
1112
1113 Assertions.assertTrue(tree.isEmpty());
1114 Assertions.assertFalse(tree.isFull());
1115
1116 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(TestPoint2D.ZERO));
1117 }
1118
1119 @Test
1120 void testComplement_isReversible_root() {
1121
1122 tree.complement();
1123 tree.complement();
1124
1125
1126 Assertions.assertFalse(tree.isEmpty());
1127 Assertions.assertTrue(tree.isFull());
1128
1129 Assertions.assertEquals(RegionLocation.INSIDE, root.getLocation());
1130 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(TestPoint2D.ZERO));
1131 }
1132
1133 @Test
1134 void testComplement_isReversible_skewedBowtie() {
1135
1136 insertSkewedBowtie(tree);
1137
1138
1139 tree.complement();
1140 tree.complement();
1141
1142
1143 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(3, 1)));
1144 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-3, -1)));
1145
1146 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(-3, 1)));
1147 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(3, -1)));
1148
1149 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(4, 5)));
1150 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-4, -5)));
1151
1152 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(5, 0)));
1153 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(4, 0)));
1154 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(3, 0)));
1155 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(2, 0)));
1156 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(1, 0)));
1157 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(0, 0)));
1158 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-1, 0)));
1159 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-2, 0)));
1160 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-3, 0)));
1161 Assertions.assertEquals(RegionLocation.BOUNDARY, tree.classify(new TestPoint2D(-4, 0)));
1162 Assertions.assertEquals(RegionLocation.OUTSIDE, tree.classify(new TestPoint2D(-5, 0)));
1163 }
1164
1165 @Test
1166 void testComplement_getCutBoundary() {
1167
1168 tree.insert(Arrays.asList(
1169 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
1170 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(0, 1))));
1171 tree.complement();
1172
1173
1174 final RegionCutBoundary<TestPoint2D> xAxisBoundary = root.getCutBoundary();
1175 final RegionCutBoundary<TestPoint2D> yAxisBoundary = root.getMinus().getCutBoundary();
1176
1177
1178 Assertions.assertTrue(xAxisBoundary.getOutsideFacing().isEmpty());
1179 Assertions.assertFalse(xAxisBoundary.getInsideFacing().isEmpty());
1180
1181 final List<HyperplaneConvexSubset<TestPoint2D>> xAxisInsideFacing = xAxisBoundary.getInsideFacing();
1182 Assertions.assertEquals(1, xAxisInsideFacing.size());
1183
1184 final TestLineSegment xAxisSeg = (TestLineSegment) xAxisInsideFacing.get(0);
1185 PartitionTestUtils.assertPointsEqual(new TestPoint2D(Double.NEGATIVE_INFINITY, 0), xAxisSeg.getStartPoint());
1186 PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, xAxisSeg.getEndPoint());
1187
1188 Assertions.assertTrue(yAxisBoundary.getOutsideFacing().isEmpty());
1189 Assertions.assertFalse(yAxisBoundary.getInsideFacing().isEmpty());
1190
1191 final List<HyperplaneConvexSubset<TestPoint2D>> yAxisInsideFacing = yAxisBoundary.getInsideFacing();
1192 Assertions.assertEquals(1, yAxisInsideFacing.size());
1193
1194 final TestLineSegment yAxisSeg = (TestLineSegment) yAxisInsideFacing.get(0);
1195 PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, yAxisSeg.getStartPoint());
1196 PartitionTestUtils.assertPointsEqual(new TestPoint2D(0, Double.POSITIVE_INFINITY), yAxisSeg.getEndPoint());
1197 }
1198
1199 @Test
1200 void testComplementOf_rootOnly() {
1201
1202 final TestRegionBSPTree other = fullTree();
1203 insertSkewedBowtie(other);
1204
1205
1206 other.complement(tree);
1207
1208
1209 Assertions.assertFalse(tree.isEmpty());
1210 Assertions.assertTrue(tree.isFull());
1211
1212 Assertions.assertEquals(RegionLocation.INSIDE, root.getLocation());
1213 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(TestPoint2D.ZERO));
1214
1215 Assertions.assertTrue(other.isEmpty());
1216 Assertions.assertFalse(other.isFull());
1217
1218 Assertions.assertEquals(RegionLocation.OUTSIDE, other.getRoot().getLocation());
1219 Assertions.assertEquals(RegionLocation.OUTSIDE, other.classify(TestPoint2D.ZERO));
1220 }
1221
1222 @Test
1223 void testComplementOf_skewedBowtie() {
1224
1225 insertSkewedBowtie(tree);
1226
1227 final TestRegionBSPTree other = fullTree();
1228
1229
1230 other.complement(tree);
1231
1232
1233 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(3, 1)));
1234 Assertions.assertEquals(RegionLocation.INSIDE, tree.classify(new TestPoint2D(-3, -1)));
1235
1236 Assertions.assertFalse(other.isEmpty());
1237 Assertions.assertFalse(other.isFull());
1238
1239 Assertions.assertEquals(RegionLocation.OUTSIDE, other.classify(new TestPoint2D(3, 1)));
1240 Assertions.assertEquals(RegionLocation.OUTSIDE, other.classify(new TestPoint2D(-3, -1)));
1241
1242 Assertions.assertEquals(RegionLocation.INSIDE, other.classify(new TestPoint2D(-3, 1)));
1243 Assertions.assertEquals(RegionLocation.INSIDE, other.classify(new TestPoint2D(3, -1)));
1244
1245 Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(4, 5)));
1246 Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(-4, -5)));
1247
1248 Assertions.assertEquals(RegionLocation.INSIDE, other.classify(new TestPoint2D(5, 0)));
1249 Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(4, 0)));
1250 Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(3, 0)));
1251 Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(2, 0)));
1252 Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(1, 0)));
1253 Assertions.assertEquals(RegionLocation.OUTSIDE, other.classify(new TestPoint2D(0, 0)));
1254 Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(-1, 0)));
1255 Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(-2, 0)));
1256 Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(-3, 0)));
1257 Assertions.assertEquals(RegionLocation.BOUNDARY, other.classify(new TestPoint2D(-4, 0)));
1258 Assertions.assertEquals(RegionLocation.INSIDE, other.classify(new TestPoint2D(-5, 0)));
1259 }
1260
1261 @Test
1262 void testCopy() {
1263
1264 insertSkewedBowtie(tree);
1265
1266
1267 final TestRegionBSPTree copy = fullTree();
1268 copy.copy(tree);
1269
1270
1271 Assertions.assertNotSame(tree, copy);
1272 Assertions.assertEquals(tree.count(), copy.count());
1273
1274 final List<RegionLocation> origLocations = new ArrayList<>();
1275 tree.nodes().forEach(n -> origLocations.add(n.getLocation()));
1276
1277 final List<RegionLocation> copyLocations = new ArrayList<>();
1278 copy.nodes().forEach(n -> copyLocations.add(n.getLocation()));
1279
1280 Assertions.assertEquals(origLocations, copyLocations);
1281 }
1282
1283 @Test
1284 void testExtract() {
1285
1286 insertSkewedBowtie(tree);
1287
1288 final TestRegionBSPTree result = fullTree();
1289
1290 final TestPoint2D pt = new TestPoint2D(2, 2);
1291
1292
1293 result.extract(tree.findNode(pt));
1294
1295
1296 PartitionTestUtils.assertPointLocations(result, RegionLocation.INSIDE,
1297 new TestPoint2D(0, 0.5), new TestPoint2D(2, 2));
1298 PartitionTestUtils.assertPointLocations(result, RegionLocation.OUTSIDE,
1299 new TestPoint2D(-2, 2),
1300 new TestPoint2D(-2, -2), new TestPoint2D(0, -0.5), new TestPoint2D(-2, 2));
1301
1302 PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
1303 new TestPoint2D(0, 0.5), new TestPoint2D(2, 2),
1304 new TestPoint2D(-2, -2), new TestPoint2D(0, -0.5));
1305 PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
1306 new TestPoint2D(2, -2), new TestPoint2D(-2, 2));
1307 }
1308
1309 @Test
1310 void testExtract_complementedTree() {
1311
1312 insertSkewedBowtie(tree);
1313 tree.complement();
1314
1315 final TestRegionBSPTree result = fullTree();
1316
1317 final TestPoint2D pt = new TestPoint2D(2, 2);
1318
1319
1320 result.extract(tree.findNode(pt));
1321
1322
1323 PartitionTestUtils.assertPointLocations(result, RegionLocation.OUTSIDE,
1324 new TestPoint2D(0, 0.5), new TestPoint2D(2, 2));
1325 PartitionTestUtils.assertPointLocations(result, RegionLocation.INSIDE,
1326 new TestPoint2D(-2, 2),
1327 new TestPoint2D(-2, -2), new TestPoint2D(0, -0.5), new TestPoint2D(-2, 2));
1328
1329 PartitionTestUtils.assertPointLocations(tree, RegionLocation.OUTSIDE,
1330 new TestPoint2D(0, 0.5), new TestPoint2D(2, 2),
1331 new TestPoint2D(-2, -2), new TestPoint2D(0, -0.5));
1332 PartitionTestUtils.assertPointLocations(tree, RegionLocation.INSIDE,
1333 new TestPoint2D(2, -2), new TestPoint2D(-2, 2));
1334 }
1335
1336
1337
1338 @Test
1339 void testProject_emptyAndFull() {
1340
1341 final TestRegionBSPTree full = fullTree();
1342 final TestRegionBSPTree empty = emptyTree();
1343
1344
1345 Assertions.assertNull(full.project(new TestPoint2D(0, 0)));
1346 Assertions.assertNull(empty.project(new TestPoint2D(-1, 1)));
1347 }
1348
1349 @Test
1350 void testProject_halfSpace() {
1351
1352 tree.getRoot().cut(TestLine.X_AXIS);
1353
1354
1355 PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, tree.project(TestPoint2D.ZERO));
1356
1357 PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, tree.project(new TestPoint2D(0, 7)));
1358 PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, tree.project(new TestPoint2D(0, -7)));
1359
1360 PartitionTestUtils.assertPointsEqual(new TestPoint2D(4, 0), tree.project(new TestPoint2D(4, 10)));
1361 PartitionTestUtils.assertPointsEqual(new TestPoint2D(-5, 0), tree.project(new TestPoint2D(-5, -2)));
1362 }
1363
1364 @Test
1365 void testProject_box() {
1366
1367 insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
1368
1369
1370 PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, tree.project(TestPoint2D.ZERO));
1371 PartitionTestUtils.assertPointsEqual(TestPoint2D.ZERO, tree.project(new TestPoint2D(-1, -4)));
1372
1373 PartitionTestUtils.assertPointsEqual(new TestPoint2D(1, 1), tree.project(new TestPoint2D(2, 9)));
1374
1375 PartitionTestUtils.assertPointsEqual(new TestPoint2D(0.5, 1), tree.project(new TestPoint2D(0.5, 3)));
1376 }
1377
1378 @Test
1379 void testSplit_empty() {
1380
1381 tree = emptyTree();
1382
1383
1384 final Split<TestRegionBSPTree> split = tree.split(TestLine.X_AXIS);
1385
1386
1387 Assertions.assertEquals(SplitLocation.NEITHER, split.getLocation());
1388
1389 Assertions.assertNull(split.getMinus());
1390 Assertions.assertNull(split.getPlus());
1391 }
1392
1393 @Test
1394 void testSplit_full() {
1395
1396 tree = fullTree();
1397
1398
1399 final Split<TestRegionBSPTree> split = tree.split(TestLine.X_AXIS);
1400
1401
1402 Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
1403
1404 final TestRegionBSPTree minus = split.getMinus();
1405 PartitionTestUtils.assertPointLocations(minus, RegionLocation.INSIDE,
1406 new TestPoint2D(-1, 1), new TestPoint2D(0, 1), new TestPoint2D(1, 1));
1407 PartitionTestUtils.assertPointLocations(minus, RegionLocation.BOUNDARY,
1408 new TestPoint2D(-1, 0), new TestPoint2D(0, 0), new TestPoint2D(1, 0));
1409 PartitionTestUtils.assertPointLocations(minus, RegionLocation.OUTSIDE,
1410 new TestPoint2D(-1, -1), new TestPoint2D(0, -1), new TestPoint2D(1, -1));
1411
1412 final TestRegionBSPTree plus = split.getPlus();
1413 PartitionTestUtils.assertPointLocations(plus, RegionLocation.OUTSIDE,
1414 new TestPoint2D(-1, 1), new TestPoint2D(0, 1), new TestPoint2D(1, 1));
1415 PartitionTestUtils.assertPointLocations(plus, RegionLocation.BOUNDARY,
1416 new TestPoint2D(-1, 0), new TestPoint2D(0, 0), new TestPoint2D(1, 0));
1417 PartitionTestUtils.assertPointLocations(plus, RegionLocation.INSIDE,
1418 new TestPoint2D(-1, -1), new TestPoint2D(0, -1), new TestPoint2D(1, -1));
1419 }
1420
1421 @Test
1422 void testSplit_halfSpace() {
1423
1424 tree.getRoot().insertCut(TestLine.X_AXIS);
1425
1426 final TestLine splitter = TestLine.Y_AXIS;
1427
1428
1429 final Split<TestRegionBSPTree> split = tree.split(splitter);
1430
1431
1432 Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
1433
1434 final TestRegionBSPTree minus = split.getMinus();
1435 PartitionTestUtils.assertPointLocations(minus, RegionLocation.INSIDE, new TestPoint2D(-1, 1));
1436 PartitionTestUtils.assertPointLocations(minus, RegionLocation.OUTSIDE,
1437 new TestPoint2D(1, 1), new TestPoint2D(-1, -1), new TestPoint2D(1, -1));
1438
1439 final TestRegionBSPTree plus = split.getPlus();
1440 PartitionTestUtils.assertPointLocations(plus, RegionLocation.INSIDE, new TestPoint2D(1, 1));
1441 PartitionTestUtils.assertPointLocations(plus, RegionLocation.OUTSIDE,
1442 new TestPoint2D(-1, 1), new TestPoint2D(-1, -1), new TestPoint2D(1, -1));
1443 }
1444
1445 @Test
1446 void testSplit_box() {
1447
1448 insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
1449
1450 final TestLine splitter = new TestLine(new TestPoint2D(1, 0), new TestPoint2D(0, 1));
1451
1452
1453 final Split<TestRegionBSPTree> split = tree.split(splitter);
1454
1455
1456 Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
1457
1458 final TestRegionBSPTree minus = split.getMinus();
1459 PartitionTestUtils.assertPointLocations(minus, RegionLocation.INSIDE, new TestPoint2D(0.25, 0.25));
1460 PartitionTestUtils.assertPointLocations(minus, RegionLocation.BOUNDARY,
1461 new TestPoint2D(0.5, 0), new TestPoint2D(0, 0.5));
1462 PartitionTestUtils.assertPointLocations(minus, RegionLocation.OUTSIDE,
1463 new TestPoint2D(1, 0.5), new TestPoint2D(0.5, 1), new TestPoint2D(0.75, 0.75));
1464
1465 final TestRegionBSPTree plus = split.getPlus();
1466 PartitionTestUtils.assertPointLocations(plus, RegionLocation.INSIDE, new TestPoint2D(0.75, 0.75));
1467 PartitionTestUtils.assertPointLocations(plus, RegionLocation.OUTSIDE,
1468 new TestPoint2D(0.5, 0), new TestPoint2D(0, 0.5), new TestPoint2D(0.25, 0.25));
1469 PartitionTestUtils.assertPointLocations(plus, RegionLocation.BOUNDARY,
1470 new TestPoint2D(1, 0.5), new TestPoint2D(0.5, 1));
1471 }
1472
1473 @Test
1474 void testSplit_box_onMinusOnly() {
1475
1476 insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
1477
1478 final TestLine splitter = new TestLine(new TestPoint2D(2, 0), new TestPoint2D(1, 1));
1479
1480
1481 final Split<TestRegionBSPTree> split = tree.split(splitter);
1482
1483
1484 Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
1485
1486 final TestRegionBSPTree minus = split.getMinus();
1487 PartitionTestUtils.assertPointLocations(minus, RegionLocation.INSIDE, new TestPoint2D(0.5, 0.5));
1488 PartitionTestUtils.assertPointLocations(minus, RegionLocation.BOUNDARY,
1489 new TestPoint2D(0.5, 0), new TestPoint2D(0, 0.5),
1490 new TestPoint2D(1, 0.5), new TestPoint2D(0.5, 1));
1491
1492 Assertions.assertNull(split.getPlus());
1493 }
1494
1495 @Test
1496 void testSplit_box_onPlusOnly() {
1497
1498 insertBox(tree, new TestPoint2D(0, 1), new TestPoint2D(1, 0));
1499
1500 final TestLine splitter = new TestLine(new TestPoint2D(0, 0), new TestPoint2D(-1, 1));
1501
1502
1503 final Split<TestRegionBSPTree> split = tree.split(splitter);
1504
1505
1506 Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
1507
1508 Assertions.assertNull(split.getMinus());
1509
1510 final TestRegionBSPTree plus = split.getPlus();
1511 PartitionTestUtils.assertPointLocations(plus, RegionLocation.INSIDE, new TestPoint2D(0.5, 0.5));
1512 PartitionTestUtils.assertPointLocations(plus, RegionLocation.BOUNDARY,
1513 new TestPoint2D(0.5, 0), new TestPoint2D(0, 0.5),
1514 new TestPoint2D(1, 0.5), new TestPoint2D(0.5, 1));
1515 }
1516
1517 @Test
1518 void testToString() {
1519
1520 tree.getRoot().cut(TestLine.X_AXIS);
1521
1522
1523 final String str = tree.toString();
1524
1525
1526 Assertions.assertEquals("TestRegionBSPTree[count= 3, height= 1]", str);
1527 Assertions.assertTrue(tree.getRoot().toString().contains("TestRegionNode"));
1528 }
1529
1530 private static void insertBox(final TestRegionBSPTree tree, final TestPoint2D upperLeft,
1531 final TestPoint2D lowerRight) {
1532 final TestPoint2D upperRight = new TestPoint2D(lowerRight.getX(), upperLeft.getY());
1533 final TestPoint2D lowerLeft = new TestPoint2D(upperLeft.getX(), lowerRight.getY());
1534
1535 tree.insert(Arrays.asList(
1536 new TestLineSegment(lowerRight, upperRight),
1537 new TestLineSegment(upperRight, upperLeft),
1538 new TestLineSegment(upperLeft, lowerLeft),
1539 new TestLineSegment(lowerLeft, lowerRight)
1540 ));
1541 }
1542
1543 private static void insertSkewedBowtie(final TestRegionBSPTree tree) {
1544 tree.insert(Arrays.asList(
1545 new TestLineSegment(TestPoint2D.ZERO, new TestPoint2D(1, 0)),
1546
1547 new TestLineSegment(new TestPoint2D(4, 0), new TestPoint2D(4, 1)),
1548 new TestLineSegment(new TestPoint2D(-4, 0), new TestPoint2D(-4, -1)),
1549
1550 new TestLineSegment(new TestPoint2D(4, 5), new TestPoint2D(-1, 0)),
1551 new TestLineSegment(new TestPoint2D(-4, -5), new TestPoint2D(1, 0))));
1552 }
1553
1554 private static void assertCutBoundarySegment(final List<HyperplaneConvexSubset<TestPoint2D>> boundaries,
1555 final TestPoint2D start, final TestPoint2D end) {
1556 Assertions.assertFalse(boundaries.isEmpty(), "Expected boundary to not be empty");
1557
1558 Assertions.assertEquals(1, boundaries.size());
1559
1560 final TestLineSegment segment = (TestLineSegment) boundaries.get(0);
1561 PartitionTestUtils.assertPointsEqual(start, segment.getStartPoint());
1562 PartitionTestUtils.assertPointsEqual(end, segment.getEndPoint());
1563 }
1564
1565 private static void assertContainsSegment(final List<TestLineSegment> boundaries, final TestPoint2D start,
1566 final TestPoint2D end) {
1567 boolean found = false;
1568 for (final TestLineSegment seg : boundaries) {
1569 final TestPoint2D startPt = seg.getStartPoint();
1570 final TestPoint2D endPt = seg.getEndPoint();
1571
1572 if (PartitionTestUtils.PRECISION.eq(start.getX(), startPt.getX()) &&
1573 PartitionTestUtils.PRECISION.eq(start.getY(), startPt.getY()) &&
1574 PartitionTestUtils.PRECISION.eq(end.getX(), endPt.getX()) &&
1575 PartitionTestUtils.PRECISION.eq(end.getY(), endPt.getY())) {
1576 found = true;
1577 break;
1578 }
1579 }
1580
1581 Assertions.assertTrue(found, "Expected to find segment start= " + start + ", end= " + end);
1582 }
1583
1584 private static TestRegionBSPTree emptyTree() {
1585 return new TestRegionBSPTree(false);
1586 }
1587
1588 private static TestRegionBSPTree fullTree() {
1589 return new TestRegionBSPTree(true);
1590 }
1591 }