View Javadoc

    1   /*
    2    * Licensed to the Apache Software Foundation (ASF) under one or more
    3    * contributor license agreements.  See the NOTICE file distributed with
    4    * this work for additional information regarding copyright ownership.
    5    * The ASF licenses this file to You under the Apache License, Version 2.0
    6    * (the "License"); you may not use this file except in compliance with
    7    * the License.  You may obtain a copy of the License at
    8    *
    9    *      http://www.apache.org/licenses/LICENSE-2.0
    10   *
    11   * Unless required by applicable law or agreed to in writing, software
    12   * distributed under the License is distributed on an "AS IS" BASIS,
    13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    14   * See the License for the specific language governing permissions and
    15   * limitations under the License.
    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          // arrange
    43          final RegionBSPTree1D tree = new RegionBSPTree1D(true);
    44          tree.getRoot().cut(OrientedPoints.createPositiveFacing(1.0, TEST_PRECISION));
    45
    46          // act
    47          final RegionBSPTree1D copy = tree.copy();
    48
    49          // assert
    50          Assertions.assertNotSame(tree, copy);
    51          Assertions.assertEquals(3, copy.count());
    52      }
    53
    54      @Test
    55      void testClassify_fullRegion() {
    56          // arrange
    57          final RegionBSPTree1D tree = new RegionBSPTree1D(true);
    58
    59          // act/assert
    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          // arrange
    69          final RegionBSPTree1D tree = new RegionBSPTree1D(false);
    70
    71          // act/assert
    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          // arrange
    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          // act/assert
    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          // arrange
    100         final RegionBSPTree1D tree = new RegionBSPTree1D(true);
    101
    102         // act/assert
    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         // arrange
    112         final RegionBSPTree1D tree = new RegionBSPTree1D(false);
    113
    114         // act/assert
    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         // arrange
    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         // act/assert
    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         // act/assert
    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         // arrange
    154         final RegionBSPTree1D full = RegionBSPTree1D.full();
    155
    156         // act/assert
    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         // arrange
    165         final RegionBSPTree1D empty = RegionBSPTree1D.empty();
    166
    167         // act/assert
    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         // arrange
    176         final RegionBSPTree1D tree = RegionBSPTree1D.from(Interval.point(1, TEST_PRECISION));
    177
    178         // act/assert
    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         // arrange
    194         final RegionBSPTree1D tree = RegionBSPTree1D.from(Interval.of(Double.NEGATIVE_INFINITY, 1, TEST_PRECISION));
    195
    196         // act/assert
    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         // arrange
    210         final RegionBSPTree1D tree = RegionBSPTree1D.from(Interval.of(1, Double.POSITIVE_INFINITY, TEST_PRECISION));
    211
    212         // act/assert
    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         // arrange
    226         final RegionBSPTree1D tree = RegionBSPTree1D.from(Interval.of(1, 3, TEST_PRECISION));
    227
    228         // act/assert
    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         // arrange
    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         // act/assert
    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         // arrange
    300         final RegionBSPTree1D tree = RegionBSPTree1D.empty();
    301
    302         // act
    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         // assert
    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         // arrange
    319         final RegionBSPTree1D tree = RegionBSPTree1D.empty();
    320
    321         // act
    322         tree.add(Interval.of(1, 2, TEST_PRECISION));
    323         tree.add(Interval.of(2, 3, TEST_PRECISION));
    324
    325         // assert
    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         // arrange
    337         final RegionBSPTree1D tree = RegionBSPTree1D.empty();
    338
    339         // act
    340         tree.add(Interval.of(-1, 1, TEST_PRECISION));
    341         tree.add(Interval.of(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, TEST_PRECISION));
    342
    343         // assert
    344         Assertions.assertTrue(tree.isFull());
    345         Assertions.assertEquals(1, tree.count());
    346     }
    347
    348     @Test
    349     void testAdd_interval_duplicateBoundaryPoint() {
    350         // arrange
    351         final RegionBSPTree1D tree = new RegionBSPTree1D(false);
    352
    353         // act
    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         // assert
    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         // arrange
    370         final RegionBSPTree1D tree = new RegionBSPTree1D(true);
    371
    372         // act
    373         final List<Interval> intervals = tree.toIntervals();
    374
    375         // assert
    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         // arrange
    383         final RegionBSPTree1D tree = new RegionBSPTree1D(false);
    384
    385         // act
    386         final List<Interval> intervals = tree.toIntervals();
    387
    388         // assert
    389         Assertions.assertEquals(0, intervals.size());
    390     }
    391
    392     @Test
    393     void testToIntervals_halfOpen_negative() {
    394         // arrange
    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         // act
    401         final List<Interval> intervals = tree.toIntervals();
    402
    403         // assert
    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         // arrange
    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         // act
    417         final List<Interval> intervals = tree.toIntervals();
    418
    419         // assert
    420         Assertions.assertEquals(1, intervals.size());
    421         checkInterval(intervals.get(0), -1, Double.POSITIVE_INFINITY);
    422     }
    423
    424     @Test
    425     void testToIntervals_singleClosedInterval() {
    426         // arrange
    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         // act
    433         final List<Interval> intervals = tree.toIntervals();
    434
    435         // assert
    436         Assertions.assertEquals(1, intervals.size());
    437         checkInterval(intervals.get(0), -1, 1);
    438     }
    439
    440     @Test
    441     void testToIntervals_singleClosedInterval_complement() {
    442         // arrange
    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         // act
    450         final List<Interval> intervals = tree.toIntervals();
    451
    452         // assert
    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         // arrange
    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         // act
    469         final List<Interval> intervals = tree.toIntervals();
    470
    471         // assert
    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         // arrange
    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         // act
    487         final List<Interval> intervals = tree.toIntervals();
    488
    489         // assert
    490         Assertions.assertEquals(1, intervals.size());
    491         checkInterval(intervals.get(0), 1, 1);
    492     }
    493
    494     @Test
    495     void testToIntervals_singlePoint_complement() {
    496         // arrange
    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         // act
    504         final List<Interval> intervals = tree.toIntervals();
    505
    506         // assert
    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         // arrange
    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         // act
    522         final List<Interval> intervals = tree.toIntervals();
    523
    524         // assert
    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         // arrange
    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         // act
    541         final List<Interval> intervals = tree.toIntervals();
    542
    543         // assert
    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         // arrange
    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         // act
    559         final List<Interval> intervals = tree.toIntervals();
    560
    561         // assert
    562         Assertions.assertEquals(1, intervals.size());
    563         checkInterval(intervals.get(0), 1, 3);
    564     }
    565
    566     @Test
    567     void testToIntervals_multipleAdjacentIntervals() {
    568         // arrange
    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         // act
    579         final List<Interval> intervals = tree.toIntervals();
    580
    581         // assert
    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         // arrange
    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         // act
    597         final List<Interval> intervals = tree.toIntervals();
    598
    599         // assert
    600         Assertions.assertEquals(1, intervals.size());
    601         checkInterval(intervals.get(0), -1, 6);
    602     }
    603
    604     @Test
    605     void testGetNodeRegion() {
    606         // arrange
    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         // act/assert
    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         // arrange
    628         final RegionBSPTree1D tree = RegionBSPTree1D.full();
    629
    630         final AffineTransformMatrix1D transform = AffineTransformMatrix1D.createScale(2);
    631
    632         // act
    633         tree.transform(transform);
    634
    635         // assert
    636         Assertions.assertTrue(tree.isFull());
    637     }
    638
    639     @Test
    640     void testTransform_noReflection() {
    641         // arrange
    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         // act
    651         tree.transform(transform);
    652
    653         // assert
    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         // arrange
    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         // act
    673         tree.transform(transform);
    674
    675         // assert
    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         // arrange
    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         // act
    694         tree.transform(transform);
    695
    696         // assert
    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         // arrange
    707         final RegionBSPTree1D tree = RegionBSPTree1D.full();
    708         final OrientedPoint splitter = OrientedPoints.fromLocationAndDirection(2, true, TEST_PRECISION);
    709
    710         // act
    711         final Split<RegionBSPTree1D> split = tree.split(splitter);
    712
    713         // assert
    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         // arrange
    728         final RegionBSPTree1D tree = RegionBSPTree1D.empty();
    729         final OrientedPoint splitter = OrientedPoints.fromLocationAndDirection(2, true, TEST_PRECISION);
    730
    731         // act
    732         final Split<RegionBSPTree1D> split = tree.split(splitter);
    733
    734         // assert
    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         // arrange
    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         // act
    751         final Split<RegionBSPTree1D> split = tree.split(splitter);
    752
    753         // assert
    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         // arrange
    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         // act
    775         final Split<RegionBSPTree1D> split = tree.split(splitter);
    776
    777         // assert
    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         // arrange
    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         // act
    796         final Split<RegionBSPTree1D> split = tree.split(splitter);
    797
    798         // assert
    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         // arrange
    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         // act
    816         final Split<RegionBSPTree1D> split = tree.split(splitter);
    817
    818         // assert
    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         // arrange
    831         final RegionBSPTree1D tree = RegionBSPTree1D.from(Interval.point(1, TEST_PRECISION));
    832
    833         final OrientedPoint splitter = OrientedPoints.fromLocationAndDirection(1, true, TEST_PRECISION);
    834
    835         // act
    836         final Split<RegionBSPTree1D> split = tree.split(splitter);
    837
    838         // assert
    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         // arrange
    851         final RegionBSPTree1D tree = RegionBSPTree1D.from(Interval.point(1, TEST_PRECISION));
    852
    853         final OrientedPoint splitter = OrientedPoints.fromLocationAndDirection(1, false, TEST_PRECISION);
    854
    855         // act
    856         final Split<RegionBSPTree1D> split = tree.split(splitter);
    857
    858         // assert
    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         // arrange
    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         // act/assert
    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         // arrange
    888         final RegionBSPTree1D tree = RegionBSPTree1D.empty();
    889
    890         // act/assert
    891         Assertions.assertEquals(0, tree.getSize(), TEST_EPS);
    892     }
    893
    894     @Test
    895     void testGetSize_exactPoints() {
    896         // arrange
    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         // act/assert
    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         // arrange
    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         // act/assert
    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         // arrange
    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         // act/assert
    936         Assertions.assertEquals(3, tree.getSize(), TEST_EPS);
    937     }
    938
    939     @Test
    940     void testGetSize_intervalWithPoints() {
    941         // arrange
    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         // act/assert
    948         Assertions.assertEquals(1, tree.getSize(), TEST_EPS);
    949     }
    950
    951     @Test
    952     void testGetSize_complementedRegion() {
    953         // arrange
    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         // act/assert
    961         Assertions.assertEquals(2, tree.getSize(), TEST_EPS);
    962     }
    963
    964     @Test
    965     void testGetCentroid_infinite() {
    966         // arrange
    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         // act/assert
    976         Assertions.assertNull(full.getCentroid());
    977         Assertions.assertNull(posHalfSpace.getCentroid());
    978         Assertions.assertNull(negHalfSpace.getCentroid());
    979     }
    980
    981     @Test
    982     void testGetCentroid_empty() {
    983         // arrange
    984         final RegionBSPTree1D tree = RegionBSPTree1D.empty();
    985
    986         // act/assert
    987         Assertions.assertNull(tree.getCentroid());
    988     }
    989
    990     @Test
    991     void testGetCentroid_exactPoints() {
    992         // arrange
    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         // act/assert
    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      // arrange
    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         // act/assert
    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         // arrange
    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         // act/assert
    1032         EuclideanTestUtils.assertCoordinatesEqual(Vector1D.of(9.5 / 3), tree.getCentroid(), TEST_EPS);
    1033     }
    1034
    1035     @Test
    1036     void testGetCentroid_complementedRegion() {
    1037         // arrange
    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         // act/assert
    1045         EuclideanTestUtils.assertCoordinatesEqual(Vector1D.of(3), tree.getCentroid(), TEST_EPS);
    1046     }
    1047
    1048     @Test
    1049     void testGetCentroid_intervalWithPoints() {
    1050         // arrange
    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         // act/assert
    1057         EuclideanTestUtils.assertCoordinatesEqual(Vector1D.of(1.5), tree.getCentroid(), TEST_EPS);
    1058     }
    1059
    1060     @Test
    1061     void testGetMinMax_full() {
    1062         // arrange
    1063         final RegionBSPTree1D tree = RegionBSPTree1D.empty();
    1064
    1065         // act/assert
    1066         GeometryTestUtils.assertPositiveInfinity(tree.getMin());
    1067         GeometryTestUtils.assertNegativeInfinity(tree.getMax());
    1068     }
    1069
    1070     @Test
    1071     void testGetMinMax_empty() {
    1072         // arrange
    1073         final RegionBSPTree1D tree = RegionBSPTree1D.empty();
    1074
    1075         // act/assert
    1076         GeometryTestUtils.assertPositiveInfinity(tree.getMin());
    1077         GeometryTestUtils.assertNegativeInfinity(tree.getMax());
    1078     }
    1079
    1080     @Test
    1081     void testGetMinMax_halfSpaces() {
    1082         // arrange
    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         // act/assert
    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         // arrange
    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         // act/assert
    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         // arrange
    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         // act/assert
    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         // act
    1128         final RegionBSPTree1D tree = RegionBSPTree1D.full();
    1129
    1130         // assert
    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         // act
    1139         final RegionBSPTree1D tree = RegionBSPTree1D.empty();
    1140
    1141         // assert
    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         // act
    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         // assert
    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         // act
    1169         final RegionBSPTree1D tree = RegionBSPTree1D.from(Collections.emptyList());
    1170
    1171         // assert
    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         // act
    1181         final RegionBSPTree1D tree = RegionBSPTree1D.from(
    1182                     Interval.of(1, 2, TEST_PRECISION),
    1183                     Interval.of(3, 4, TEST_PRECISION)
    1184                 );
    1185
    1186         // assert
    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 }