1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.geometry.euclidean.oned;
18
19 import java.util.Arrays;
20 import java.util.Collections;
21 import java.util.List;
22
23 import org.apache.commons.geometry.core.GeometryTestUtils;
24 import org.apache.commons.geometry.core.RegionLocation;
25 import org.apache.commons.geometry.core.partitioning.Split;
26 import org.apache.commons.geometry.core.partitioning.SplitLocation;
27 import org.apache.commons.geometry.euclidean.EuclideanTestUtils;
28 import org.apache.commons.geometry.euclidean.oned.RegionBSPTree1D.RegionNode1D;
29 import org.apache.commons.numbers.core.Precision;
30 import org.junit.jupiter.api.Assertions;
31 import org.junit.jupiter.api.Test;
32
33 class RegionBSPTree1DTest {
34
35 private static final double TEST_EPS = 1e-10;
36
37 private static final Precision.DoubleEquivalence TEST_PRECISION =
38 Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
39
40 @Test
41 void testCopy() {
42
43 final RegionBSPTree1D tree = new RegionBSPTree1D(true);
44 tree.getRoot().cut(OrientedPoints.createPositiveFacing(1.0, TEST_PRECISION));
45
46
47 final RegionBSPTree1D copy = tree.copy();
48
49
50 Assertions.assertNotSame(tree, copy);
51 Assertions.assertEquals(3, copy.count());
52 }
53
54 @Test
55 void testClassify_fullRegion() {
56
57 final RegionBSPTree1D tree = new RegionBSPTree1D(true);
58
59
60 checkClassify(tree, RegionLocation.INSIDE,
61 Double.NEGATIVE_INFINITY, -1, 0, 1, Double.POSITIVE_INFINITY);
62
63 checkClassify(tree, RegionLocation.OUTSIDE, Double.NaN);
64 }
65
66 @Test
67 void testClassify_emptyRegion() {
68
69 final RegionBSPTree1D tree = new RegionBSPTree1D(false);
70
71
72 checkClassify(tree, RegionLocation.OUTSIDE,
73 Double.NEGATIVE_INFINITY, -1, 0, 1, Double.POSITIVE_INFINITY);
74
75 checkClassify(tree, RegionLocation.OUTSIDE, Double.NaN);
76 }
77
78 @Test
79 void testClassify_singleClosedInterval() {
80
81 final RegionBSPTree1D tree = new RegionBSPTree1D();
82 tree.insert(Arrays.asList(
83 OrientedPoints.createNegativeFacing(Vector1D.of(-1), TEST_PRECISION).span(),
84 OrientedPoints.createPositiveFacing(Vector1D.of(9), TEST_PRECISION).span()
85 ));
86
87
88 checkClassify(tree, RegionLocation.OUTSIDE, Double.NEGATIVE_INFINITY);
89 checkClassify(tree, RegionLocation.OUTSIDE, -2.0);
90 checkClassify(tree, RegionLocation.INSIDE, 0.0);
91 checkClassify(tree, RegionLocation.BOUNDARY, 9.0 - 1e-16);
92 checkClassify(tree, RegionLocation.BOUNDARY, 9.0 + 1e-16);
93 checkClassify(tree, RegionLocation.OUTSIDE, 10.0);
94 checkClassify(tree, RegionLocation.OUTSIDE, Double.POSITIVE_INFINITY);
95 }
96
97 @Test
98 void testContains_fullRegion() {
99
100 final RegionBSPTree1D tree = new RegionBSPTree1D(true);
101
102
103 checkContains(tree, true,
104 Double.NEGATIVE_INFINITY, -1, 0, 1, Double.POSITIVE_INFINITY);
105
106 checkContains(tree, false, Double.NaN);
107 }
108
109 @Test
110 void testContains_emptyRegion() {
111
112 final RegionBSPTree1D tree = new RegionBSPTree1D(false);
113
114
115 checkContains(tree, false,
116 Double.NEGATIVE_INFINITY, -1, 0, 1, Double.POSITIVE_INFINITY);
117
118 checkContains(tree, false, Double.NaN);
119 }
120
121 @Test
122 void testContains_singleClosedInterval() {
123
124 final RegionBSPTree1D tree = new RegionBSPTree1D();
125 tree.insert(Arrays.asList(
126 OrientedPoints.createNegativeFacing(Vector1D.of(-1), TEST_PRECISION).span(),
127 OrientedPoints.createPositiveFacing(Vector1D.of(9), TEST_PRECISION).span()
128 ));
129
130
131 checkContains(tree, false, Double.NEGATIVE_INFINITY);
132 checkContains(tree, false, -2.0);
133 checkContains(tree, true, 0.0);
134 checkContains(tree, true, 9.0 - 1e-16);
135 checkContains(tree, true, 9.0 + 1e-16);
136 checkContains(tree, false, 10.0);
137 checkContains(tree, false, Double.POSITIVE_INFINITY);
138 }
139
140 @Test
141 void testGetBoundarySize_alwaysReturnsZero() {
142
143 Assertions.assertEquals(0.0, RegionBSPTree1D.full().getBoundarySize(), TEST_EPS);
144 Assertions.assertEquals(0.0, RegionBSPTree1D.empty().getBoundarySize(), TEST_EPS);
145 Assertions.assertEquals(0.0, RegionBSPTree1D.from(
146 Interval.of(1, 2, TEST_PRECISION),
147 Interval.of(4, 5, TEST_PRECISION)
148 ).getBoundarySize(), TEST_EPS);
149 }
150
151 @Test
152 void testProject_full() {
153
154 final RegionBSPTree1D full = RegionBSPTree1D.full();
155
156
157 Assertions.assertNull(full.project(Vector1D.of(Double.NEGATIVE_INFINITY)));
158 Assertions.assertNull(full.project(Vector1D.of(0)));
159 Assertions.assertNull(full.project(Vector1D.of(Double.POSITIVE_INFINITY)));
160 }
161
162 @Test
163 void testProject_empty() {
164
165 final RegionBSPTree1D empty = RegionBSPTree1D.empty();
166
167
168 Assertions.assertNull(empty.project(Vector1D.of(Double.NEGATIVE_INFINITY)));
169 Assertions.assertNull(empty.project(Vector1D.of(0)));
170 Assertions.assertNull(empty.project(Vector1D.of(Double.POSITIVE_INFINITY)));
171 }
172
173 @Test
174 void testProject_singlePoint() {
175
176 final RegionBSPTree1D tree = RegionBSPTree1D.from(Interval.point(1, TEST_PRECISION));
177
178
179 checkBoundaryProjection(tree, -1, 1);
180 checkBoundaryProjection(tree, 0, 1);
181
182 checkBoundaryProjection(tree, 1, 1);
183
184 checkBoundaryProjection(tree, 2, 1);
185 checkBoundaryProjection(tree, 3, 1);
186
187 checkBoundaryProjection(tree, Double.NEGATIVE_INFINITY, 1);
188 checkBoundaryProjection(tree, Double.POSITIVE_INFINITY, 1);
189 }
190
191 @Test
192 void testProject_noMinBoundary() {
193
194 final RegionBSPTree1D tree = RegionBSPTree1D.from(Interval.of(Double.NEGATIVE_INFINITY, 1, TEST_PRECISION));
195
196
197 checkBoundaryProjection(tree, -1, 1);
198 checkBoundaryProjection(tree, 0, 1);
199 checkBoundaryProjection(tree, 1, 1);
200 checkBoundaryProjection(tree, 2, 1);
201 checkBoundaryProjection(tree, 3, 1);
202
203 checkBoundaryProjection(tree, Double.NEGATIVE_INFINITY, 1);
204 checkBoundaryProjection(tree, Double.POSITIVE_INFINITY, 1);
205 }
206
207 @Test
208 void testProject_noMaxBoundary() {
209
210 final RegionBSPTree1D tree = RegionBSPTree1D.from(Interval.of(1, Double.POSITIVE_INFINITY, TEST_PRECISION));
211
212
213 checkBoundaryProjection(tree, -1, 1);
214 checkBoundaryProjection(tree, 0, 1);
215 checkBoundaryProjection(tree, 1, 1);
216 checkBoundaryProjection(tree, 2, 1);
217 checkBoundaryProjection(tree, 3, 1);
218
219 checkBoundaryProjection(tree, Double.NEGATIVE_INFINITY, 1);
220 checkBoundaryProjection(tree, Double.POSITIVE_INFINITY, 1);
221 }
222
223 @Test
224 void testProject_closedInterval() {
225
226 final RegionBSPTree1D tree = RegionBSPTree1D.from(Interval.of(1, 3, TEST_PRECISION));
227
228
229 checkBoundaryProjection(tree, -1, 1);
230 checkBoundaryProjection(tree, 0, 1);
231 checkBoundaryProjection(tree, 1, 1);
232
233 checkBoundaryProjection(tree, 1.9, 1);
234 checkBoundaryProjection(tree, 2, 1);
235 checkBoundaryProjection(tree, 2.1, 3);
236
237 checkBoundaryProjection(tree, 3, 3);
238 checkBoundaryProjection(tree, 4, 3);
239 checkBoundaryProjection(tree, 5, 3);
240
241 checkBoundaryProjection(tree, Double.NEGATIVE_INFINITY, 1);
242 checkBoundaryProjection(tree, Double.POSITIVE_INFINITY, 3);
243 }
244
245 @Test
246 void testProject_multipleIntervals() {
247
248 final RegionBSPTree1D tree = RegionBSPTree1D.from(
249 Interval.max(-1, TEST_PRECISION),
250 Interval.point(1, TEST_PRECISION),
251 Interval.of(2, 3, TEST_PRECISION),
252 Interval.of(5, 6, TEST_PRECISION)
253 );
254
255
256 checkBoundaryProjection(tree, Double.NEGATIVE_INFINITY, -1);
257 checkBoundaryProjection(tree, -2, -1);
258 checkBoundaryProjection(tree, -1, -1);
259
260 checkBoundaryProjection(tree, -0.5, -1);
261 checkBoundaryProjection(tree, 0, -1);
262 checkBoundaryProjection(tree, 0.5, 1);
263
264 checkBoundaryProjection(tree, 0.9, 1);
265 checkBoundaryProjection(tree, 1, 1);
266 checkBoundaryProjection(tree, 1.1, 1);
267
268 checkBoundaryProjection(tree, 0.5, 1);
269
270 checkBoundaryProjection(tree, 1.9, 2);
271 checkBoundaryProjection(tree, 2, 2);
272 checkBoundaryProjection(tree, 2.1, 2);
273 checkBoundaryProjection(tree, 2.5, 2);
274 checkBoundaryProjection(tree, 2.9, 3);
275 checkBoundaryProjection(tree, 3, 3);
276 checkBoundaryProjection(tree, 3.1, 3);
277
278 checkBoundaryProjection(tree, 3.9, 3);
279 checkBoundaryProjection(tree, 4, 3);
280 checkBoundaryProjection(tree, 4.1, 5);
281
282 checkBoundaryProjection(tree, 4.9, 5);
283 checkBoundaryProjection(tree, 5, 5);
284 checkBoundaryProjection(tree, 5.1, 5);
285 checkBoundaryProjection(tree, 5.49, 5);
286 checkBoundaryProjection(tree, 5.5, 5);
287 checkBoundaryProjection(tree, 5.51, 6);
288 checkBoundaryProjection(tree, 5.9, 6);
289 checkBoundaryProjection(tree, 6, 6);
290 checkBoundaryProjection(tree, 6.1, 6);
291
292 checkBoundaryProjection(tree, 7, 6);
293
294 checkBoundaryProjection(tree, Double.POSITIVE_INFINITY, 6);
295 }
296
297 @Test
298 void testAdd_interval() {
299
300 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
301
302
303 tree.add(Interval.of(Double.NEGATIVE_INFINITY, -10, TEST_PRECISION));
304 tree.add(Interval.of(-1, 1, TEST_PRECISION));
305 tree.add(Interval.of(10, Double.POSITIVE_INFINITY, TEST_PRECISION));
306
307
308 checkClassify(tree, RegionLocation.INSIDE,
309 Double.NEGATIVE_INFINITY, -11, 0, 11, Double.POSITIVE_INFINITY);
310
311 checkClassify(tree, RegionLocation.BOUNDARY, -10, -1, 1, 10);
312
313 checkClassify(tree, RegionLocation.OUTSIDE, -9, -2, 2, 9);
314 }
315
316 @Test
317 void testAdd_adjacentIntervals() {
318
319 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
320
321
322 tree.add(Interval.of(1, 2, TEST_PRECISION));
323 tree.add(Interval.of(2, 3, TEST_PRECISION));
324
325
326 checkClassify(tree, RegionLocation.INSIDE, 1.1, 2, 2.9);
327
328 checkClassify(tree, RegionLocation.BOUNDARY, 1, 3);
329
330 checkClassify(tree, RegionLocation.OUTSIDE,
331 Double.NEGATIVE_INFINITY, 0, 0.9, 3.1, 4, Double.POSITIVE_INFINITY);
332 }
333
334 @Test
335 void testAdd_addFullInterval() {
336
337 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
338
339
340 tree.add(Interval.of(-1, 1, TEST_PRECISION));
341 tree.add(Interval.of(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, TEST_PRECISION));
342
343
344 Assertions.assertTrue(tree.isFull());
345 Assertions.assertEquals(1, tree.count());
346 }
347
348 @Test
349 void testAdd_interval_duplicateBoundaryPoint() {
350
351 final RegionBSPTree1D tree = new RegionBSPTree1D(false);
352
353
354 tree.add(Interval.of(1, 2, TEST_PRECISION));
355 tree.add(Interval.of(2, 3, TEST_PRECISION));
356 tree.add(Interval.of(1, 2, TEST_PRECISION));
357 tree.add(Interval.of(0, 1, TEST_PRECISION));
358
359
360 checkClassify(tree, RegionLocation.INSIDE, 0.1, 1, 2, 2.9);
361
362 checkClassify(tree, RegionLocation.BOUNDARY, 0, 3);
363
364 checkClassify(tree, RegionLocation.OUTSIDE, -1, -0.1, 3.1, 4);
365 }
366
367 @Test
368 void testToIntervals_fullRegion() {
369
370 final RegionBSPTree1D tree = new RegionBSPTree1D(true);
371
372
373 final List<Interval> intervals = tree.toIntervals();
374
375
376 Assertions.assertEquals(1, intervals.size());
377 checkInterval(intervals.get(0), Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);
378 }
379
380 @Test
381 void testToIntervals_emptyRegion() {
382
383 final RegionBSPTree1D tree = new RegionBSPTree1D(false);
384
385
386 final List<Interval> intervals = tree.toIntervals();
387
388
389 Assertions.assertEquals(0, intervals.size());
390 }
391
392 @Test
393 void testToIntervals_halfOpen_negative() {
394
395 final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-2);
396
397 final RegionBSPTree1D tree = new RegionBSPTree1D();
398 tree.getRoot().cut(OrientedPoints.fromLocationAndDirection(1.0, true, precision));
399
400
401 final List<Interval> intervals = tree.toIntervals();
402
403
404 Assertions.assertEquals(1, intervals.size());
405 checkInterval(intervals.get(0), Double.NEGATIVE_INFINITY, 1);
406 }
407
408 @Test
409 void testToIntervals_halfOpen_positive() {
410
411 final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-2);
412
413 final RegionBSPTree1D tree = new RegionBSPTree1D();
414 tree.getRoot().cut(OrientedPoints.fromLocationAndDirection(-1.0, false, precision));
415
416
417 final List<Interval> intervals = tree.toIntervals();
418
419
420 Assertions.assertEquals(1, intervals.size());
421 checkInterval(intervals.get(0), -1, Double.POSITIVE_INFINITY);
422 }
423
424 @Test
425 void testToIntervals_singleClosedInterval() {
426
427 final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-2);
428
429 final RegionBSPTree1D tree = new RegionBSPTree1D(false);
430 tree.add(Interval.of(-1, 1, precision));
431
432
433 final List<Interval> intervals = tree.toIntervals();
434
435
436 Assertions.assertEquals(1, intervals.size());
437 checkInterval(intervals.get(0), -1, 1);
438 }
439
440 @Test
441 void testToIntervals_singleClosedInterval_complement() {
442
443 final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-2);
444
445 final RegionBSPTree1D tree = new RegionBSPTree1D(false);
446 tree.add(Interval.of(-1, 1, precision));
447 tree.complement();
448
449
450 final List<Interval> intervals = tree.toIntervals();
451
452
453 Assertions.assertEquals(2, intervals.size());
454 checkInterval(intervals.get(0), Double.NEGATIVE_INFINITY, -1);
455 checkInterval(intervals.get(1), 1, Double.POSITIVE_INFINITY);
456 }
457
458 @Test
459 void testToIntervals_openAndClosedIntervals() {
460
461 final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-2);
462
463 final RegionBSPTree1D tree = new RegionBSPTree1D(false);
464 tree.add(Interval.of(Double.NEGATIVE_INFINITY, -10, precision));
465 tree.add(Interval.of(-1, 1, precision));
466 tree.add(Interval.of(10, Double.POSITIVE_INFINITY, precision));
467
468
469 final List<Interval> intervals = tree.toIntervals();
470
471
472 Assertions.assertEquals(3, intervals.size());
473 checkInterval(intervals.get(0), Double.NEGATIVE_INFINITY, -10);
474 checkInterval(intervals.get(1), -1, 1);
475 checkInterval(intervals.get(2), 10, Double.POSITIVE_INFINITY);
476 }
477
478 @Test
479 void testToIntervals_singlePoint() {
480
481 final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-2);
482
483 final RegionBSPTree1D tree = new RegionBSPTree1D(false);
484 tree.add(Interval.of(1, 1, precision));
485
486
487 final List<Interval> intervals = tree.toIntervals();
488
489
490 Assertions.assertEquals(1, intervals.size());
491 checkInterval(intervals.get(0), 1, 1);
492 }
493
494 @Test
495 void testToIntervals_singlePoint_complement() {
496
497 final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-2);
498
499 final RegionBSPTree1D tree = new RegionBSPTree1D(false);
500 tree.add(Interval.of(1, 1, precision));
501 tree.complement();
502
503
504 final List<Interval> intervals = tree.toIntervals();
505
506
507 Assertions.assertEquals(2, intervals.size());
508 checkInterval(intervals.get(0), Double.NEGATIVE_INFINITY, 1);
509 checkInterval(intervals.get(1), 1, Double.POSITIVE_INFINITY);
510 }
511
512 @Test
513 void testToIntervals_multiplePoints() {
514
515 final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-2);
516
517 final RegionBSPTree1D tree = new RegionBSPTree1D(false);
518 tree.add(Interval.of(1, 1, precision));
519 tree.add(Interval.of(2, 2, precision));
520
521
522 final List<Interval> intervals = tree.toIntervals();
523
524
525 Assertions.assertEquals(2, intervals.size());
526 checkInterval(intervals.get(0), 1, 1);
527 checkInterval(intervals.get(1), 2, 2);
528 }
529
530 @Test
531 void testToIntervals_multiplePoints_complement() {
532
533 final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-2);
534
535 final RegionBSPTree1D tree = new RegionBSPTree1D(false);
536 tree.add(Interval.of(1, 1, precision));
537 tree.add(Interval.of(2, 2, precision));
538 tree.complement();
539
540
541 final List<Interval> intervals = tree.toIntervals();
542
543
544 Assertions.assertEquals(3, intervals.size());
545 checkInterval(intervals.get(0), Double.NEGATIVE_INFINITY, 1);
546 checkInterval(intervals.get(1), 1, 2);
547 checkInterval(intervals.get(2), 2, Double.POSITIVE_INFINITY);
548 }
549
550 @Test
551 void testToIntervals_adjacentIntervals() {
552
553 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
554
555 tree.add(Interval.of(1, 2, TEST_PRECISION));
556 tree.add(Interval.of(2, 3, TEST_PRECISION));
557
558
559 final List<Interval> intervals = tree.toIntervals();
560
561
562 Assertions.assertEquals(1, intervals.size());
563 checkInterval(intervals.get(0), 1, 3);
564 }
565
566 @Test
567 void testToIntervals_multipleAdjacentIntervals() {
568
569 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
570
571 tree.add(Interval.of(1, 2, TEST_PRECISION));
572 tree.add(Interval.of(2, 3, TEST_PRECISION));
573 tree.add(Interval.of(3, 4, TEST_PRECISION));
574
575 tree.add(Interval.of(-2, -1, TEST_PRECISION));
576 tree.add(Interval.of(5, 6, TEST_PRECISION));
577
578
579 final List<Interval> intervals = tree.toIntervals();
580
581
582 Assertions.assertEquals(3, intervals.size());
583 checkInterval(intervals.get(0), -2, -1);
584 checkInterval(intervals.get(1), 1, 4);
585 checkInterval(intervals.get(2), 5, 6);
586 }
587
588 @Test
589 void testToIntervals() {
590
591 final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-2);
592
593 final RegionBSPTree1D tree = new RegionBSPTree1D(false);
594 tree.add(Interval.of(-1, 6, precision));
595
596
597 final List<Interval> intervals = tree.toIntervals();
598
599
600 Assertions.assertEquals(1, intervals.size());
601 checkInterval(intervals.get(0), -1, 6);
602 }
603
604 @Test
605 void testGetNodeRegion() {
606
607 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
608
609 final RegionNode1D root = tree.getRoot();
610 root.cut(OrientedPoints.createPositiveFacing(1.0, TEST_PRECISION));
611
612 final RegionNode1D minus = root.getMinus();
613 minus.cut(OrientedPoints.createNegativeFacing(0.0, TEST_PRECISION));
614
615
616 checkInterval(root.getNodeRegion(), Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);
617
618 checkInterval(minus.getNodeRegion(), Double.NEGATIVE_INFINITY, 1.0);
619 checkInterval(root.getPlus().getNodeRegion(), 1.0, Double.POSITIVE_INFINITY);
620
621 checkInterval(minus.getPlus().getNodeRegion(), Double.NEGATIVE_INFINITY, 0.0);
622 checkInterval(minus.getMinus().getNodeRegion(), 0.0, 1.0);
623 }
624
625 @Test
626 void testTransform_full() {
627
628 final RegionBSPTree1D tree = RegionBSPTree1D.full();
629
630 final AffineTransformMatrix1D transform = AffineTransformMatrix1D.createScale(2);
631
632
633 tree.transform(transform);
634
635
636 Assertions.assertTrue(tree.isFull());
637 }
638
639 @Test
640 void testTransform_noReflection() {
641
642 final RegionBSPTree1D tree = RegionBSPTree1D.from(
643 Interval.of(1, 2, TEST_PRECISION),
644 Interval.min(3, TEST_PRECISION)
645 );
646
647 final AffineTransformMatrix1D transform = AffineTransformMatrix1D.createScale(2)
648 .translate(3);
649
650
651 tree.transform(transform);
652
653
654 final List<Interval> intervals = tree.toIntervals();
655
656 Assertions.assertEquals(2, intervals.size());
657 checkInterval(intervals.get(0), 5, 7);
658 checkInterval(intervals.get(1), 9, Double.POSITIVE_INFINITY);
659 }
660
661 @Test
662 void testTransform_withReflection() {
663
664 final RegionBSPTree1D tree = RegionBSPTree1D.from(
665 Interval.of(1, 2, TEST_PRECISION),
666 Interval.min(3, TEST_PRECISION)
667 );
668
669 final AffineTransformMatrix1D transform = AffineTransformMatrix1D.createScale(-2)
670 .translate(3);
671
672
673 tree.transform(transform);
674
675
676 final List<Interval> intervals = tree.toIntervals();
677
678 Assertions.assertEquals(2, intervals.size());
679 checkInterval(intervals.get(0), Double.NEGATIVE_INFINITY, -3);
680 checkInterval(intervals.get(1), -1, 1);
681 }
682
683 @Test
684 void testTransform_withReflection_functionBasedTransform() {
685
686 final RegionBSPTree1D tree = RegionBSPTree1D.from(
687 Interval.of(1, 2, TEST_PRECISION),
688 Interval.min(3, TEST_PRECISION)
689 );
690
691 final AffineTransformMatrix1D transform = AffineTransformMatrix1D.from(Vector1D::negate);
692
693
694 tree.transform(transform);
695
696
697 final List<Interval> intervals = tree.toIntervals();
698
699 Assertions.assertEquals(2, intervals.size());
700 checkInterval(intervals.get(0), Double.NEGATIVE_INFINITY, -3);
701 checkInterval(intervals.get(1), -2, -1);
702 }
703
704 @Test
705 void testSplit_full() {
706
707 final RegionBSPTree1D tree = RegionBSPTree1D.full();
708 final OrientedPoint splitter = OrientedPoints.fromLocationAndDirection(2, true, TEST_PRECISION);
709
710
711 final Split<RegionBSPTree1D> split = tree.split(splitter);
712
713
714 Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
715
716 final List<Interval> minusIntervals = split.getMinus().toIntervals();
717 Assertions.assertEquals(1, minusIntervals.size());
718 checkInterval(minusIntervals.get(0), Double.NEGATIVE_INFINITY, 2);
719
720 final List<Interval> plusIntervals = split.getPlus().toIntervals();
721 Assertions.assertEquals(1, plusIntervals.size());
722 checkInterval(plusIntervals.get(0), 2, Double.POSITIVE_INFINITY);
723 }
724
725 @Test
726 void testSplit_empty() {
727
728 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
729 final OrientedPoint splitter = OrientedPoints.fromLocationAndDirection(2, true, TEST_PRECISION);
730
731
732 final Split<RegionBSPTree1D> split = tree.split(splitter);
733
734
735 Assertions.assertEquals(SplitLocation.NEITHER, split.getLocation());
736
737 Assertions.assertNull(split.getMinus());
738 Assertions.assertNull(split.getPlus());
739 }
740
741 @Test
742 void testSplit_bothSides() {
743
744 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
745 tree.add(Interval.max(-2, TEST_PRECISION));
746 tree.add(Interval.of(1, 4, TEST_PRECISION));
747
748 final OrientedPoint splitter = OrientedPoints.fromLocationAndDirection(2, false, TEST_PRECISION);
749
750
751 final Split<RegionBSPTree1D> split = tree.split(splitter);
752
753
754 Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
755
756 final List<Interval> minusIntervals = split.getMinus().toIntervals();
757 Assertions.assertEquals(1, minusIntervals.size());
758 checkInterval(minusIntervals.get(0), 2, 4);
759
760 final List<Interval> plusIntervals = split.getPlus().toIntervals();
761 Assertions.assertEquals(2, plusIntervals.size());
762 checkInterval(plusIntervals.get(0), Double.NEGATIVE_INFINITY, -2);
763 checkInterval(plusIntervals.get(1), 1, 2);
764 }
765
766 @Test
767 void testSplit_splitterOnBoundary_minus() {
768
769 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
770 tree.add(Interval.of(1, 4, TEST_PRECISION));
771
772 final OrientedPoint splitter = OrientedPoints.fromLocationAndDirection(1, false, TEST_PRECISION);
773
774
775 final Split<RegionBSPTree1D> split = tree.split(splitter);
776
777
778 Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
779
780 final List<Interval> minusIntervals = split.getMinus().toIntervals();
781 Assertions.assertEquals(1, minusIntervals.size());
782 checkInterval(minusIntervals.get(0), 1, 4);
783
784 Assertions.assertNull(split.getPlus());
785 }
786
787 @Test
788 void testSplit_splitterOnBoundary_plus() {
789
790 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
791 tree.add(Interval.of(1, 4, TEST_PRECISION));
792
793 final OrientedPoint splitter = OrientedPoints.fromLocationAndDirection(4, false, TEST_PRECISION);
794
795
796 final Split<RegionBSPTree1D> split = tree.split(splitter);
797
798
799 Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
800
801 Assertions.assertNull(split.getMinus());
802
803 final List<Interval> plusIntervals = split.getPlus().toIntervals();
804 Assertions.assertEquals(1, plusIntervals.size());
805 checkInterval(plusIntervals.get(0), 1, 4);
806 }
807
808 @Test
809 void testSplit_point() {
810
811 final RegionBSPTree1D tree = RegionBSPTree1D.from(Interval.point(1.0, TEST_PRECISION));
812
813 final OrientedPoint splitter = OrientedPoints.fromLocationAndDirection(2, false, TEST_PRECISION);
814
815
816 final Split<RegionBSPTree1D> split = tree.split(splitter);
817
818
819 Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
820
821 Assertions.assertNull(split.getMinus());
822
823 final List<Interval> plusIntervals = split.getPlus().toIntervals();
824 Assertions.assertEquals(1, plusIntervals.size());
825 checkInterval(plusIntervals.get(0), 1, 1);
826 }
827
828 @Test
829 void testSplit_point_splitOnPoint_positiveFacingSplitter() {
830
831 final RegionBSPTree1D tree = RegionBSPTree1D.from(Interval.point(1, TEST_PRECISION));
832
833 final OrientedPoint splitter = OrientedPoints.fromLocationAndDirection(1, true, TEST_PRECISION);
834
835
836 final Split<RegionBSPTree1D> split = tree.split(splitter);
837
838
839 Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
840
841 Assertions.assertNull(split.getMinus());
842
843 final List<Interval> plusIntervals = split.getPlus().toIntervals();
844 Assertions.assertEquals(1, plusIntervals.size());
845 checkInterval(plusIntervals.get(0), 1, 1);
846 }
847
848 @Test
849 void testSplit_point_splitOnPoint_negativeFacingSplitter() {
850
851 final RegionBSPTree1D tree = RegionBSPTree1D.from(Interval.point(1, TEST_PRECISION));
852
853 final OrientedPoint splitter = OrientedPoints.fromLocationAndDirection(1, false, TEST_PRECISION);
854
855
856 final Split<RegionBSPTree1D> split = tree.split(splitter);
857
858
859 Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
860
861 final List<Interval> minusIntervals = split.getMinus().toIntervals();
862 Assertions.assertEquals(1, minusIntervals.size());
863 checkInterval(minusIntervals.get(0), 1, 1);
864
865 Assertions.assertNull(split.getPlus());
866 }
867
868 @Test
869 void testGetSize_infinite() {
870
871 final RegionBSPTree1D full = RegionBSPTree1D.full();
872
873 final RegionBSPTree1D posHalfSpace = RegionBSPTree1D.empty();
874 posHalfSpace.getRoot().cut(OrientedPoints.createNegativeFacing(-2.0, TEST_PRECISION));
875
876 final RegionBSPTree1D negHalfSpace = RegionBSPTree1D.empty();
877 negHalfSpace.getRoot().cut(OrientedPoints.createPositiveFacing(3.0, TEST_PRECISION));
878
879
880 Assertions.assertEquals(Double.POSITIVE_INFINITY, full.getSize(), TEST_EPS);
881 Assertions.assertEquals(Double.POSITIVE_INFINITY, posHalfSpace.getSize(), TEST_EPS);
882 Assertions.assertEquals(Double.POSITIVE_INFINITY, negHalfSpace.getSize(), TEST_EPS);
883 }
884
885 @Test
886 void testGetSize_empty() {
887
888 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
889
890
891 Assertions.assertEquals(0, tree.getSize(), TEST_EPS);
892 }
893
894 @Test
895 void testGetSize_exactPoints() {
896
897 final RegionBSPTree1D singlePoint = RegionBSPTree1D.empty();
898 singlePoint.add(Interval.of(1, 1, TEST_PRECISION));
899
900 final RegionBSPTree1D multiplePoints = RegionBSPTree1D.empty();
901 multiplePoints.add(Interval.of(1, 1, TEST_PRECISION));
902 multiplePoints.add(Interval.of(-1, -1, TEST_PRECISION));
903 multiplePoints.add(Interval.of(2, 2, TEST_PRECISION));
904
905
906 Assertions.assertEquals(0, singlePoint.getSize(), TEST_EPS);
907 Assertions.assertEquals(0, multiplePoints.getSize(), TEST_EPS);
908 }
909
910 @Test
911 void testGetSize_pointsWithinPrecision() {
912
913 final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-1);
914
915 final RegionBSPTree1D singlePoint = RegionBSPTree1D.empty();
916 singlePoint.add(Interval.of(1, 1.02, precision));
917
918 final RegionBSPTree1D multiplePoints = RegionBSPTree1D.empty();
919 multiplePoints.add(Interval.of(1, 1.02, precision));
920 multiplePoints.add(Interval.of(-1.02, -1, precision));
921 multiplePoints.add(Interval.of(2, 2.02, precision));
922
923
924 Assertions.assertEquals(0.02, singlePoint.getSize(), TEST_EPS);
925 Assertions.assertEquals(0.06, multiplePoints.getSize(), TEST_EPS);
926 }
927
928 @Test
929 void testGetSize_nonEmptyIntervals() {
930
931 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
932 tree.add(Interval.of(1, 2, TEST_PRECISION));
933 tree.add(Interval.of(3, 5, TEST_PRECISION));
934
935
936 Assertions.assertEquals(3, tree.getSize(), TEST_EPS);
937 }
938
939 @Test
940 void testGetSize_intervalWithPoints() {
941
942 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
943 tree.add(Interval.of(1, 2, TEST_PRECISION));
944 tree.add(Interval.of(3, 3, TEST_PRECISION));
945 tree.add(Interval.of(5, 5, TEST_PRECISION));
946
947
948 Assertions.assertEquals(1, tree.getSize(), TEST_EPS);
949 }
950
951 @Test
952 void testGetSize_complementedRegion() {
953
954 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
955 tree.add(Interval.of(Double.NEGATIVE_INFINITY, 2, TEST_PRECISION));
956 tree.add(Interval.of(4, Double.POSITIVE_INFINITY, TEST_PRECISION));
957
958 tree.complement();
959
960
961 Assertions.assertEquals(2, tree.getSize(), TEST_EPS);
962 }
963
964 @Test
965 void testGetCentroid_infinite() {
966
967 final RegionBSPTree1D full = RegionBSPTree1D.full();
968
969 final RegionBSPTree1D posHalfSpace = RegionBSPTree1D.empty();
970 posHalfSpace.getRoot().cut(OrientedPoints.createNegativeFacing(-2.0, TEST_PRECISION));
971
972 final RegionBSPTree1D negHalfSpace = RegionBSPTree1D.empty();
973 negHalfSpace.getRoot().cut(OrientedPoints.createPositiveFacing(3.0, TEST_PRECISION));
974
975
976 Assertions.assertNull(full.getCentroid());
977 Assertions.assertNull(posHalfSpace.getCentroid());
978 Assertions.assertNull(negHalfSpace.getCentroid());
979 }
980
981 @Test
982 void testGetCentroid_empty() {
983
984 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
985
986
987 Assertions.assertNull(tree.getCentroid());
988 }
989
990 @Test
991 void testGetCentroid_exactPoints() {
992
993 final RegionBSPTree1D singlePoint = RegionBSPTree1D.empty();
994 singlePoint.add(Interval.of(1, 1, TEST_PRECISION));
995
996 final RegionBSPTree1D multiplePoints = RegionBSPTree1D.empty();
997 multiplePoints.add(Interval.of(1, 1, TEST_PRECISION));
998 multiplePoints.add(Interval.of(-1, -1, TEST_PRECISION));
999 multiplePoints.add(Interval.of(6, 6, TEST_PRECISION));
1000
1001
1002 EuclideanTestUtils.assertCoordinatesEqual(Vector1D.of(1), singlePoint.getCentroid(), TEST_EPS);
1003 EuclideanTestUtils.assertCoordinatesEqual(Vector1D.of(2), multiplePoints.getCentroid(), TEST_EPS);
1004 }
1005
1006 @Test
1007 void testGetCentroid_pointsWithinPrecision() {
1008
1009 final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(1e-1);
1010
1011 final RegionBSPTree1D singlePoint = RegionBSPTree1D.empty();
1012 singlePoint.add(Interval.of(1, 1.02, precision));
1013
1014 final RegionBSPTree1D multiplePoints = RegionBSPTree1D.empty();
1015 multiplePoints.add(Interval.of(1, 1.02, precision));
1016 multiplePoints.add(Interval.of(-1.02, -1, precision));
1017 multiplePoints.add(Interval.of(6, 6.02, precision));
1018
1019
1020 EuclideanTestUtils.assertCoordinatesEqual(Vector1D.of(1.01), singlePoint.getCentroid(), TEST_EPS);
1021 EuclideanTestUtils.assertCoordinatesEqual(Vector1D.of(6.01 / 3), multiplePoints.getCentroid(), TEST_EPS);
1022 }
1023
1024 @Test
1025 void testGetCentroid_nonEmptyIntervals() {
1026
1027 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
1028 tree.add(Interval.of(1, 2, TEST_PRECISION));
1029 tree.add(Interval.of(3, 5, TEST_PRECISION));
1030
1031
1032 EuclideanTestUtils.assertCoordinatesEqual(Vector1D.of(9.5 / 3), tree.getCentroid(), TEST_EPS);
1033 }
1034
1035 @Test
1036 void testGetCentroid_complementedRegion() {
1037
1038 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
1039 tree.add(Interval.of(Double.NEGATIVE_INFINITY, 2, TEST_PRECISION));
1040 tree.add(Interval.of(4, Double.POSITIVE_INFINITY, TEST_PRECISION));
1041
1042 tree.complement();
1043
1044
1045 EuclideanTestUtils.assertCoordinatesEqual(Vector1D.of(3), tree.getCentroid(), TEST_EPS);
1046 }
1047
1048 @Test
1049 void testGetCentroid_intervalWithPoints() {
1050
1051 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
1052 tree.add(Interval.of(1, 2, TEST_PRECISION));
1053 tree.add(Interval.of(3, 3, TEST_PRECISION));
1054 tree.add(Interval.of(5, 5, TEST_PRECISION));
1055
1056
1057 EuclideanTestUtils.assertCoordinatesEqual(Vector1D.of(1.5), tree.getCentroid(), TEST_EPS);
1058 }
1059
1060 @Test
1061 void testGetMinMax_full() {
1062
1063 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
1064
1065
1066 GeometryTestUtils.assertPositiveInfinity(tree.getMin());
1067 GeometryTestUtils.assertNegativeInfinity(tree.getMax());
1068 }
1069
1070 @Test
1071 void testGetMinMax_empty() {
1072
1073 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
1074
1075
1076 GeometryTestUtils.assertPositiveInfinity(tree.getMin());
1077 GeometryTestUtils.assertNegativeInfinity(tree.getMax());
1078 }
1079
1080 @Test
1081 void testGetMinMax_halfSpaces() {
1082
1083 final RegionBSPTree1D posHalfSpace = RegionBSPTree1D.empty();
1084 posHalfSpace.getRoot().cut(OrientedPoints.createNegativeFacing(-2.0, TEST_PRECISION));
1085
1086 final RegionBSPTree1D negHalfSpace = RegionBSPTree1D.empty();
1087 negHalfSpace.getRoot().cut(OrientedPoints.createPositiveFacing(3.0, TEST_PRECISION));
1088
1089
1090 Assertions.assertEquals(-2, posHalfSpace.getMin(), TEST_EPS);
1091 GeometryTestUtils.assertPositiveInfinity(posHalfSpace.getMax());
1092
1093 GeometryTestUtils.assertNegativeInfinity(negHalfSpace.getMin());
1094 Assertions.assertEquals(3, negHalfSpace.getMax(), TEST_EPS);
1095 }
1096
1097 @Test
1098 void testGetMinMax_multipleIntervals() {
1099
1100 final RegionBSPTree1D tree = RegionBSPTree1D.from(Arrays.asList(
1101 Interval.of(3, 5, TEST_PRECISION),
1102 Interval.of(-4, -2, TEST_PRECISION),
1103 Interval.of(0, 0, TEST_PRECISION)
1104 ));
1105
1106
1107 Assertions.assertEquals(-4, tree.getMin(), TEST_EPS);
1108 Assertions.assertEquals(5, tree.getMax(), TEST_EPS);
1109 }
1110
1111 @Test
1112 void testGetMinMax_pointsAtMinAndMax() {
1113
1114 final RegionBSPTree1D tree = RegionBSPTree1D.from(Arrays.asList(
1115 Interval.of(5, 5, TEST_PRECISION),
1116 Interval.of(-4, -4, TEST_PRECISION),
1117 Interval.of(0, 0, TEST_PRECISION)
1118 ));
1119
1120
1121 Assertions.assertEquals(-4, tree.getMin(), TEST_EPS);
1122 Assertions.assertEquals(5, tree.getMax(), TEST_EPS);
1123 }
1124
1125 @Test
1126 void testFull_factoryMethod() {
1127
1128 final RegionBSPTree1D tree = RegionBSPTree1D.full();
1129
1130
1131 Assertions.assertTrue(tree.isFull());
1132 Assertions.assertFalse(tree.isEmpty());
1133 Assertions.assertNotSame(tree, RegionBSPTree1D.full());
1134 }
1135
1136 @Test
1137 void testEmpty_factoryMethod() {
1138
1139 final RegionBSPTree1D tree = RegionBSPTree1D.empty();
1140
1141
1142 Assertions.assertFalse(tree.isFull());
1143 Assertions.assertTrue(tree.isEmpty());
1144 Assertions.assertNotSame(tree, RegionBSPTree1D.full());
1145 }
1146
1147 @Test
1148 void testFromIntervals_iterable() {
1149
1150 final RegionBSPTree1D tree = RegionBSPTree1D.from(Arrays.asList(
1151 Interval.of(1, 2, TEST_PRECISION),
1152 Interval.of(3, 4, TEST_PRECISION)
1153 ));
1154
1155
1156 Assertions.assertFalse(tree.isFull());
1157 Assertions.assertFalse(tree.isEmpty());
1158
1159 checkClassify(tree, RegionLocation.INSIDE, 1.5, 3.5);
1160 checkClassify(tree, RegionLocation.BOUNDARY, 1, 2, 3, 4);
1161 checkClassify(tree, RegionLocation.OUTSIDE, 0, 2.5, 5);
1162
1163 Assertions.assertEquals(2, tree.toIntervals().size());
1164 }
1165
1166 @Test
1167 void testFromIntervals_iterable_noItervals() {
1168
1169 final RegionBSPTree1D tree = RegionBSPTree1D.from(Collections.emptyList());
1170
1171
1172 Assertions.assertFalse(tree.isFull());
1173 Assertions.assertTrue(tree.isEmpty());
1174
1175 Assertions.assertEquals(0, tree.toIntervals().size());
1176 }
1177
1178 @Test
1179 void testFromIntervals_varargs() {
1180
1181 final RegionBSPTree1D tree = RegionBSPTree1D.from(
1182 Interval.of(1, 2, TEST_PRECISION),
1183 Interval.of(3, 4, TEST_PRECISION)
1184 );
1185
1186
1187 Assertions.assertFalse(tree.isFull());
1188 Assertions.assertFalse(tree.isEmpty());
1189
1190 checkClassify(tree, RegionLocation.INSIDE, 1.5, 3.5);
1191 checkClassify(tree, RegionLocation.BOUNDARY, 1, 2, 3, 4);
1192 checkClassify(tree, RegionLocation.OUTSIDE, 0, 2.5, 5);
1193
1194 Assertions.assertEquals(2, tree.toIntervals().size());
1195 }
1196
1197 private static void checkClassify(final RegionBSPTree1D tree, final RegionLocation loc, final double... points) {
1198 for (final double x : points) {
1199 final String msg = "Unexpected location for point " + x;
1200
1201 Assertions.assertEquals(loc, tree.classify(x), msg);
1202 Assertions.assertEquals(loc, tree.classify(Vector1D.of(x)), msg);
1203 }
1204 }
1205
1206 private static void checkContains(final RegionBSPTree1D tree, final boolean contains, final double... points) {
1207 for (final double x : points) {
1208 final String msg = "Unexpected contains status for point " + x;
1209
1210 Assertions.assertEquals(contains, tree.contains(x), msg);
1211 Assertions.assertEquals(contains, tree.contains(Vector1D.of(x)), msg);
1212 }
1213 }
1214
1215 private static void checkBoundaryProjection(final RegionBSPTree1D tree, final double location, final double projectedLocation) {
1216 final Vector1D pt = Vector1D.of(location);
1217
1218 final Vector1D proj = tree.project(pt);
1219
1220 Assertions.assertEquals(projectedLocation, proj.getX(), TEST_EPS);
1221 }
1222
1223 private static void checkInterval(final Interval interval, final double min, final double max) {
1224 checkInterval(interval, min, max, TEST_PRECISION);
1225 }
1226
1227 private static void checkInterval(final Interval interval, final double min, final double max, final Precision.DoubleEquivalence precision) {
1228 Assertions.assertEquals(min, interval.getMin(), TEST_EPS);
1229 Assertions.assertEquals(max, interval.getMax(), TEST_EPS);
1230 }
1231 }