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