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.spherical.oned;
    18
    19  import java.util.List;
    20
    21  import org.apache.commons.geometry.core.Region;
    22  import org.apache.commons.geometry.core.RegionLocation;
    23  import org.apache.commons.geometry.core.partitioning.Split;
    24  import org.apache.commons.geometry.core.partitioning.SplitLocation;
    25  import org.apache.commons.geometry.euclidean.twod.Vector2D;
    26  import org.apache.commons.numbers.angle.Angle;
    27  import org.apache.commons.numbers.core.Precision;
    28  import org.junit.jupiter.api.Assertions;
    29  import org.junit.jupiter.api.Test;
    30
    31  class RegionBSPTree1STest {
    32
    33      private static final double TEST_EPS = 1e-10;
    34
    35      private static final Precision.DoubleEquivalence TEST_PRECISION =
    36              Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
    37
    38      private static final Transform1S HALF_PI_PLUS_AZ = Transform1S.createRotation(Angle.PI_OVER_TWO);
    39
    40      private static final Transform1S PI_MINUS_AZ = Transform1S.createNegation().rotate(Math.PI);
    41
    42      @Test
    43      void testConstructor_default() {
    44          // act
    45          final RegionBSPTree1S tree = new RegionBSPTree1S();
    46
    47          // assert
    48          Assertions.assertFalse(tree.isFull());
    49          Assertions.assertTrue(tree.isEmpty());
    50
    51          Assertions.assertEquals(0, tree.getSize(), TEST_EPS);
    52          Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
    53          Assertions.assertNull(tree.getCentroid());
    54      }
    55
    56      @Test
    57      void testConstructor_true() {
    58          // act
    59          final RegionBSPTree1S tree = new RegionBSPTree1S(true);
    60
    61          // assert
    62          Assertions.assertTrue(tree.isFull());
    63          Assertions.assertFalse(tree.isEmpty());
    64
    65          Assertions.assertEquals(Angle.TWO_PI, tree.getSize(), TEST_EPS);
    66          Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
    67          Assertions.assertNull(tree.getCentroid());
    68      }
    69
    70      @Test
    71      void testConstructor_false() {
    72          // act
    73          final RegionBSPTree1S tree = new RegionBSPTree1S(false);
    74
    75          // assert
    76          Assertions.assertFalse(tree.isFull());
    77          Assertions.assertTrue(tree.isEmpty());
    78
    79          Assertions.assertEquals(0, tree.getSize(), TEST_EPS);
    80          Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
    81          Assertions.assertNull(tree.getCentroid());
    82      }
    83
    84      @Test
    85      void testFull() {
    86          // act
    87          final RegionBSPTree1S tree = RegionBSPTree1S.full();
    88
    89          // assert
    90          Assertions.assertTrue(tree.isFull());
    91          Assertions.assertFalse(tree.isEmpty());
    92
    93          Assertions.assertEquals(Angle.TWO_PI, tree.getSize(), TEST_EPS);
    94          Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
    95          Assertions.assertNull(tree.getCentroid());
    96      }
    97
    98      @Test
    99      void testEmpty() {
    100         // act
    101         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    102
    103         // assert
    104         Assertions.assertFalse(tree.isFull());
    105         Assertions.assertTrue(tree.isEmpty());
    106
    107         Assertions.assertEquals(0, tree.getSize(), TEST_EPS);
    108         Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
    109         Assertions.assertNull(tree.getCentroid());
    110     }
    111
    112     @Test
    113     void testCopy() {
    114         // arrange
    115         final RegionBSPTree1S orig = RegionBSPTree1S.fromInterval(AngularInterval.of(0, Math.PI, TEST_PRECISION));
    116
    117         // act
    118         final RegionBSPTree1S copy = orig.copy();
    119
    120         // assert
    121         Assertions.assertNotSame(orig, copy);
    122
    123         orig.setEmpty();
    124
    125         checkSingleInterval(copy, 0, Math.PI);
    126     }
    127
    128     @Test
    129     void testFromInterval_full() {
    130         // act
    131         final RegionBSPTree1S tree = RegionBSPTree1S.fromInterval(AngularInterval.full());
    132
    133         // assert
    134         Assertions.assertTrue(tree.isFull());
    135     }
    136
    137     @Test
    138     void testFromInterval_nonFull() {
    139         for (double theta = 0.0; theta <= Angle.TWO_PI; theta += 0.2) {
    140             // arrange
    141             final double max = theta + Angle.PI_OVER_TWO;
    142
    143             // act
    144             final RegionBSPTree1S tree = RegionBSPTree1S.fromInterval(AngularInterval.of(theta, max, TEST_PRECISION));
    145
    146             checkSingleInterval(tree, theta, max);
    147
    148             Assertions.assertEquals(Angle.PI_OVER_TWO, tree.getSize(), TEST_EPS);
    149             Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
    150             Assertions.assertEquals(Angle.Rad.WITHIN_0_AND_2PI.applyAsDouble(theta + (0.25 * Math.PI)),
    151                     tree.getCentroid().getNormalizedAzimuth(), TEST_EPS);
    152         }
    153     }
    154
    155     @Test
    156     void testClassify_full() {
    157         // arrange
    158         final RegionBSPTree1S tree = RegionBSPTree1S.full();
    159
    160         // act/assert
    161         for (double az = -Angle.TWO_PI; az <= 2 * Angle.TWO_PI; az += 0.2) {
    162             checkClassify(tree, RegionLocation.INSIDE, az);
    163         }
    164     }
    165
    166     @Test
    167     void testClassify_empty() {
    168         // arrange
    169         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    170
    171         // act/assert
    172         for (double az = -Angle.TWO_PI; az <= 2 * Angle.TWO_PI; az += 0.2) {
    173             checkClassify(tree, RegionLocation.OUTSIDE, az);
    174         }
    175     }
    176
    177     @Test
    178     void testClassify() {
    179         // arrange
    180         final RegionBSPTree1S tree = RegionBSPTree1S.fromInterval(
    181                 AngularInterval.of(-Angle.PI_OVER_TWO, Angle.PI_OVER_TWO, TEST_PRECISION));
    182
    183         // act/assert
    184         checkClassify(tree, RegionLocation.BOUNDARY,
    185                 -Angle.PI_OVER_TWO, Angle.PI_OVER_TWO,
    186                 -Angle.PI_OVER_TWO - Angle.TWO_PI, Angle.PI_OVER_TWO + Angle.TWO_PI);
    187         checkClassify(tree, RegionLocation.INSIDE,
    188                 0.0, 0.5, -0.5,
    189                 Angle.TWO_PI, 0.5 + Angle.TWO_PI, -0.5 - Angle.TWO_PI);
    190         checkClassify(tree, RegionLocation.OUTSIDE,
    191                 Math.PI, Math.PI + 0.5, Math.PI - 0.5,
    192                 Math.PI + Angle.TWO_PI, Math.PI + 0.5 + Angle.TWO_PI,
    193                 Math.PI - 0.5 + Angle.TWO_PI);
    194     }
    195
    196     @Test
    197     void testToIntervals_full() {
    198         // arrange
    199         final RegionBSPTree1S tree = RegionBSPTree1S.full();
    200
    201         // act
    202         final List<AngularInterval> intervals = tree.toIntervals();
    203
    204         // assert
    205         Assertions.assertEquals(1, intervals.size());
    206
    207         final AngularInterval interval = intervals.get(0);
    208         Assertions.assertTrue(interval.isFull());
    209     }
    210
    211     @Test
    212     void testToIntervals_empty() {
    213         // arrange
    214         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    215
    216         // act
    217         final List<AngularInterval> intervals = tree.toIntervals();
    218
    219         // assert
    220         Assertions.assertEquals(0, intervals.size());
    221     }
    222
    223     @Test
    224     void testToIntervals_singleCut() {
    225         // arrange
    226         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    227
    228         for (double theta = 0; theta <= Angle.TWO_PI; theta += 0.2) {
    229             // act/assert
    230             tree.setEmpty();
    231             tree.getRoot().cut(CutAngles.createPositiveFacing(theta, TEST_PRECISION));
    232
    233             checkSingleInterval(tree, 0, theta);
    234
    235             tree.setEmpty();
    236             tree.getRoot().cut(CutAngles.createNegativeFacing(theta, TEST_PRECISION));
    237
    238             checkSingleInterval(tree, theta, Angle.TWO_PI);
    239         }
    240     }
    241
    242     @Test
    243     void testToIntervals_wrapAround_joinedIntervalsOnPositiveSide() {
    244         // arrange
    245         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    246         tree.add(AngularInterval.of(0.25 * Math.PI, Angle.PI_OVER_TWO, TEST_PRECISION));
    247         tree.add(AngularInterval.of(1.5 * Math.PI, 0.25 * Math.PI, TEST_PRECISION));
    248
    249         // act
    250         final List<AngularInterval> intervals = tree.toIntervals();
    251
    252         // assert
    253         Assertions.assertEquals(1, intervals.size());
    254
    255         checkInterval(intervals.get(0), 1.5 * Math.PI, Angle.PI_OVER_TWO);
    256     }
    257
    258     @Test
    259     void testToIntervals_wrapAround_joinedIntervalsOnNegativeSide() {
    260         // arrange
    261         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    262         tree.add(AngularInterval.of(1.75 * Math.PI, Angle.PI_OVER_TWO, TEST_PRECISION));
    263         tree.add(AngularInterval.of(1.5 * Math.PI, 1.75 * Math.PI, TEST_PRECISION));
    264
    265         // act
    266         final List<AngularInterval> intervals = tree.toIntervals();
    267
    268         // assert
    269         Assertions.assertEquals(1, intervals.size());
    270
    271         checkInterval(intervals.get(0), 1.5 * Math.PI, Angle.PI_OVER_TWO);
    272     }
    273
    274     @Test
    275     void testToIntervals_multipleIntervals() {
    276         // arrange
    277         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    278         tree.add(AngularInterval.of(-Angle.PI_OVER_TWO, Angle.PI_OVER_TWO, TEST_PRECISION));
    279         tree.add(AngularInterval.of(Math.PI - 0.5, Math.PI, TEST_PRECISION));
    280         tree.add(AngularInterval.of(Math.PI, Math.PI + 0.5, TEST_PRECISION));
    281
    282         // act
    283         final List<AngularInterval> intervals = tree.toIntervals();
    284
    285         // assert
    286         Assertions.assertEquals(2, intervals.size());
    287
    288         checkInterval(intervals.get(0), Math.PI - 0.5, Math.PI + 0.5);
    289         checkInterval(intervals.get(1), -Angle.PI_OVER_TWO, Angle.PI_OVER_TWO);
    290     }
    291
    292     @Test
    293     void testToIntervals_multipleIntervals_complement() {
    294         // arrange
    295         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    296         tree.add(AngularInterval.of(-Angle.PI_OVER_TWO, Angle.PI_OVER_TWO, TEST_PRECISION));
    297         tree.add(AngularInterval.of(Math.PI - 0.5, Math.PI, TEST_PRECISION));
    298         tree.add(AngularInterval.of(Math.PI, Math.PI + 0.5, TEST_PRECISION));
    299
    300         tree.complement();
    301
    302         // act
    303         final List<AngularInterval> intervals = tree.toIntervals();
    304
    305         // assert
    306         Assertions.assertEquals(2, intervals.size());
    307
    308         checkInterval(intervals.get(0), Angle.PI_OVER_TWO, Math.PI - 0.5);
    309         checkInterval(intervals.get(1), Math.PI + 0.5, -Angle.PI_OVER_TWO);
    310     }
    311
    312     @Test
    313     void testSplit_empty() {
    314         // arrange
    315         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    316
    317         // act/assert
    318         Assertions.assertEquals(SplitLocation.NEITHER,
    319                 tree.split(CutAngles.createPositiveFacing(0, TEST_PRECISION)).getLocation());
    320         Assertions.assertEquals(SplitLocation.NEITHER,
    321                 tree.split(CutAngles.createNegativeFacing(Angle.PI_OVER_TWO, TEST_PRECISION)).getLocation());
    322         Assertions.assertEquals(SplitLocation.NEITHER,
    323                 tree.split(CutAngles.createPositiveFacing(Math.PI, TEST_PRECISION)).getLocation());
    324         Assertions.assertEquals(SplitLocation.NEITHER,
    325                 tree.split(CutAngles.createNegativeFacing(-Angle.PI_OVER_TWO, TEST_PRECISION)).getLocation());
    326         Assertions.assertEquals(SplitLocation.NEITHER,
    327                 tree.split(CutAngles.createPositiveFacing(Angle.TWO_PI, TEST_PRECISION)).getLocation());
    328     }
    329
    330     @Test
    331     void testSplit_full() {
    332         // arrange
    333         final RegionBSPTree1S tree = RegionBSPTree1S.full();
    334
    335         // act/assert
    336         checkSimpleSplit(
    337             tree.split(CutAngles.createPositiveFacing(1e-6, TEST_PRECISION)),
    338             AngularInterval.of(0, 1e-6, TEST_PRECISION),
    339             AngularInterval.of(1e-6, Angle.TWO_PI, TEST_PRECISION)
    340         );
    341         checkSimpleSplit(
    342             tree.split(CutAngles.createNegativeFacing(Angle.PI_OVER_TWO, TEST_PRECISION)),
    343             AngularInterval.of(Angle.PI_OVER_TWO, Angle.TWO_PI, TEST_PRECISION),
    344             AngularInterval.of(0, Angle.PI_OVER_TWO, TEST_PRECISION)
    345         );
    346         checkSimpleSplit(
    347             tree.split(CutAngles.createPositiveFacing(Math.PI, TEST_PRECISION)),
    348             AngularInterval.of(0, Math.PI, TEST_PRECISION),
    349             AngularInterval.of(Math.PI, Angle.TWO_PI, TEST_PRECISION)
    350         );
    351         checkSimpleSplit(
    352             tree.split(CutAngles.createNegativeFacing(-Angle.PI_OVER_TWO, TEST_PRECISION)),
    353             AngularInterval.of(-Angle.PI_OVER_TWO, Angle.TWO_PI, TEST_PRECISION),
    354             AngularInterval.of(0, -Angle.PI_OVER_TWO, TEST_PRECISION)
    355         );
    356         checkSimpleSplit(
    357             tree.split(CutAngles.createPositiveFacing(Angle.TWO_PI - 1e-6, TEST_PRECISION)),
    358             AngularInterval.of(0, Angle.TWO_PI - 1e-6, TEST_PRECISION),
    359             AngularInterval.of(Angle.TWO_PI - 1e-6, Angle.TWO_PI, TEST_PRECISION)
    360         );
    361     }
    362
    363     @Test
    364     void testSplit_full_cutEquivalentToZero() {
    365         // arrange
    366         final RegionBSPTree1S tree = RegionBSPTree1S.full();
    367
    368         final AngularInterval twoPi = AngularInterval.of(0, Angle.TWO_PI, TEST_PRECISION);
    369
    370         // act/assert
    371         checkSimpleSplit(
    372             tree.split(CutAngles.createPositiveFacing(0, TEST_PRECISION)),
    373             null,
    374             twoPi
    375         );
    376         checkSimpleSplit(
    377             tree.split(CutAngles.createNegativeFacing(0, TEST_PRECISION)),
    378             twoPi,
    379             null
    380         );
    381
    382         checkSimpleSplit(
    383             tree.split(CutAngles.createPositiveFacing(Angle.TWO_PI - 1e-18, TEST_PRECISION)),
    384             null,
    385             twoPi
    386         );
    387         checkSimpleSplit(
    388             tree.split(CutAngles.createNegativeFacing(Angle.TWO_PI - 1e-18, TEST_PRECISION)),
    389             twoPi,
    390             null
    391         );
    392     }
    393
    394     @Test
    395     void testSplit_singleInterval() {
    396         // arrange
    397         final AngularInterval interval = AngularInterval.of(Angle.PI_OVER_TWO, -Angle.PI_OVER_TWO, TEST_PRECISION);
    398         final RegionBSPTree1S tree = interval.toTree();
    399
    400         // act
    401         checkSimpleSplit(
    402             tree.split(CutAngles.createNegativeFacing(0, TEST_PRECISION)),
    403             interval,
    404             null
    405         );
    406         checkSimpleSplit(
    407             tree.split(CutAngles.createNegativeFacing(-Angle.TWO_PI, TEST_PRECISION)),
    408             interval,
    409             null
    410         );
    411
    412         checkSimpleSplit(
    413             tree.split(CutAngles.createPositiveFacing(Angle.TWO_PI + Angle.PI_OVER_TWO, TEST_PRECISION)),
    414             null,
    415             interval
    416         );
    417         checkSimpleSplit(
    418             tree.split(CutAngles.createPositiveFacing(1.5 * Math.PI, TEST_PRECISION)),
    419             interval,
    420             null
    421         );
    422
    423         checkSimpleSplit(
    424             tree.split(CutAngles.createNegativeFacing(Math.PI, TEST_PRECISION)),
    425             AngularInterval.of(Math.PI, -Angle.PI_OVER_TWO, TEST_PRECISION),
    426             AngularInterval.of(Angle.PI_OVER_TWO, Math.PI, TEST_PRECISION)
    427         );
    428     }
    429
    430     @Test
    431     void testSplit_singleIntervalSplitIntoTwoIntervalsOnSameSide() {
    432         // arrange
    433         final RegionBSPTree1S tree = AngularInterval.of(-Angle.PI_OVER_TWO, Angle.PI_OVER_TWO, TEST_PRECISION).toTree();
    434
    435         final CutAngle cut = CutAngles.createPositiveFacing(0, TEST_PRECISION);
    436
    437         // act
    438         final Split<RegionBSPTree1S> split = tree.split(cut);
    439
    440         // assert
    441         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
    442
    443         final RegionBSPTree1S minus = split.getMinus();
    444         Assertions.assertNull(minus);
    445
    446         final RegionBSPTree1S plus = split.getPlus();
    447         final List<AngularInterval> plusIntervals = plus.toIntervals();
    448         Assertions.assertEquals(1, plusIntervals.size());
    449         checkInterval(plusIntervals.get(0), -Angle.PI_OVER_TWO, Angle.PI_OVER_TWO);
    450     }
    451
    452     @Test
    453     void testSplit_multipleRegions() {
    454         // arrange
    455         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    456         tree.add(AngularInterval.of(Angle.TWO_PI - 1, Angle.PI_OVER_TWO, TEST_PRECISION));
    457         tree.add(AngularInterval.of(Math.PI, -Angle.PI_OVER_TWO, TEST_PRECISION));
    458
    459         final CutAngle cut = CutAngles.createNegativeFacing(1, TEST_PRECISION);
    460
    461         // act
    462         final Split<RegionBSPTree1S> split = tree.split(cut);
    463
    464         // assert
    465         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
    466
    467         final RegionBSPTree1S minus = split.getMinus();
    468         final List<AngularInterval> minusIntervals = minus.toIntervals();
    469         Assertions.assertEquals(3, minusIntervals.size());
    470         checkInterval(minusIntervals.get(0), 1, Angle.PI_OVER_TWO);
    471         checkInterval(minusIntervals.get(1), Math.PI, -Angle.PI_OVER_TWO);
    472         checkInterval(minusIntervals.get(2), Angle.TWO_PI - 1, 0);
    473
    474         final RegionBSPTree1S plus = split.getPlus();
    475         final List<AngularInterval> plusIntervals = plus.toIntervals();
    476         Assertions.assertEquals(1, plusIntervals.size());
    477         checkInterval(plusIntervals.get(0), 0, 1);
    478     }
    479
    480     @Test
    481     void testSplitDiameter_full() {
    482         // arrange
    483         final RegionBSPTree1S full = RegionBSPTree1S.full();
    484         final CutAngle splitter = CutAngles.createPositiveFacing(Angle.PI_OVER_TWO, TEST_PRECISION);
    485
    486         // act
    487         final Split<RegionBSPTree1S> split = full.splitDiameter(splitter);
    488
    489         // assert
    490         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
    491
    492         final RegionBSPTree1S minus = split.getMinus();
    493         final List<AngularInterval> minusIntervals = minus.toIntervals();
    494         Assertions.assertEquals(1, minusIntervals.size());
    495         checkInterval(minusIntervals.get(0), 1.5 * Math.PI, 2.5 * Math.PI);
    496
    497         final RegionBSPTree1S plus = split.getPlus();
    498         final List<AngularInterval> plusIntervals = plus.toIntervals();
    499         Assertions.assertEquals(1, plusIntervals.size());
    500         checkInterval(plusIntervals.get(0), Angle.PI_OVER_TWO, 1.5 * Math.PI);
    501     }
    502
    503     @Test
    504     void testSplitDiameter_empty() {
    505         // arrange
    506         final RegionBSPTree1S empty = RegionBSPTree1S.empty();
    507         final CutAngle splitter = CutAngles.createPositiveFacing(Angle.PI_OVER_TWO, TEST_PRECISION);
    508
    509         // act
    510         final Split<RegionBSPTree1S> split = empty.splitDiameter(splitter);
    511
    512         // assert
    513         Assertions.assertEquals(SplitLocation.NEITHER, split.getLocation());
    514
    515         final RegionBSPTree1S minus = split.getMinus();
    516         Assertions.assertNull(minus);
    517
    518         final RegionBSPTree1S plus = split.getPlus();
    519         Assertions.assertNull(plus);
    520     }
    521
    522     @Test
    523     void testSplitDiameter_minus_zeroOnMinusSide() {
    524         // arrange
    525         final RegionBSPTree1S tree = AngularInterval.of(0, 1, TEST_PRECISION).toTree();
    526         final CutAngle splitter = CutAngles.createPositiveFacing(1, TEST_PRECISION);
    527
    528         // act
    529         final Split<RegionBSPTree1S> split = tree.splitDiameter(splitter);
    530
    531         // assert
    532         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
    533
    534         final RegionBSPTree1S minus = split.getMinus();
    535         final List<AngularInterval> minusIntervals = minus.toIntervals();
    536         Assertions.assertEquals(1, minusIntervals.size());
    537         checkInterval(minusIntervals.get(0), 0, 1);
    538
    539         final RegionBSPTree1S plus = split.getPlus();
    540         Assertions.assertNull(plus);
    541     }
    542
    543     @Test
    544     void testSplitDiameter_minus_zeroOnPlusSide() {
    545         // arrange
    546         final RegionBSPTree1S tree = AngularInterval.of(1, 2, TEST_PRECISION).toTree();
    547         final CutAngle splitter = CutAngles.createNegativeFacing(0, TEST_PRECISION);
    548
    549         // act
    550         final Split<RegionBSPTree1S> split = tree.splitDiameter(splitter);
    551
    552         // assert
    553         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
    554
    555         final RegionBSPTree1S minus = split.getMinus();
    556         final List<AngularInterval> minusIntervals = minus.toIntervals();
    557         Assertions.assertEquals(1, minusIntervals.size());
    558         checkInterval(minusIntervals.get(0), 1, 2);
    559
    560         final RegionBSPTree1S plus = split.getPlus();
    561         Assertions.assertNull(plus);
    562     }
    563
    564     @Test
    565     void testSplitDiameter_plus_zeroOnMinusSide() {
    566         // arrange
    567         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    568         tree.add(AngularInterval.of(1, 1.1, TEST_PRECISION));
    569         tree.add(AngularInterval.of(2, 2.1, TEST_PRECISION));
    570
    571         final CutAngle splitter = CutAngles.createPositiveFacing(1, TEST_PRECISION);
    572
    573         // act
    574         final Split<RegionBSPTree1S> split = tree.splitDiameter(splitter);
    575
    576         // assert
    577         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
    578
    579         final RegionBSPTree1S minus = split.getMinus();
    580         Assertions.assertNull(minus);
    581
    582         final RegionBSPTree1S plus = split.getPlus();
    583         final List<AngularInterval> plusIntervals = plus.toIntervals();
    584         Assertions.assertEquals(2, plusIntervals.size());
    585         checkInterval(plusIntervals.get(0), 1, 1.1);
    586         checkInterval(plusIntervals.get(1), 2, 2.1);
    587     }
    588
    589     @Test
    590     void testSplitDiameter_plus_zeroOnPlusSide() {
    591         // arrange
    592         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    593         tree.add(AngularInterval.of(1, 1.1, TEST_PRECISION));
    594         tree.add(AngularInterval.of(2, 2.1, TEST_PRECISION));
    595
    596         final CutAngle splitter = CutAngles.createNegativeFacing(Math.PI - 1, TEST_PRECISION);
    597
    598         // act
    599         final Split<RegionBSPTree1S> split = tree.splitDiameter(splitter);
    600
    601         // assert
    602         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
    603
    604         final RegionBSPTree1S minus = split.getMinus();
    605         Assertions.assertNull(minus);
    606
    607         final RegionBSPTree1S plus = split.getPlus();
    608         final List<AngularInterval> plusIntervals = plus.toIntervals();
    609         Assertions.assertEquals(2, plusIntervals.size());
    610         checkInterval(plusIntervals.get(0), 1, 1.1);
    611         checkInterval(plusIntervals.get(1), 2, 2.1);
    612     }
    613
    614     @Test
    615     void testSplitDiameter_both_zeroOnMinusSide() {
    616         // arrange
    617         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    618         tree.add(AngularInterval.of(1, 1.1, TEST_PRECISION));
    619         tree.add(AngularInterval.of(2, 3, TEST_PRECISION));
    620
    621         final CutAngle splitter = CutAngles.createPositiveFacing(2.5, TEST_PRECISION);
    622
    623         // act
    624         final Split<RegionBSPTree1S> split = tree.splitDiameter(splitter);
    625
    626         // assert
    627         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
    628
    629         final RegionBSPTree1S minus = split.getMinus();
    630         final List<AngularInterval> plusIntervals = minus.toIntervals();
    631         Assertions.assertEquals(2, plusIntervals.size());
    632         checkInterval(plusIntervals.get(0), 1, 1.1);
    633         checkInterval(plusIntervals.get(1), 2, 2.5);
    634
    635         final RegionBSPTree1S plus = split.getPlus();
    636         final List<AngularInterval> minusIntervals = plus.toIntervals();
    637         Assertions.assertEquals(1, minusIntervals.size());
    638         checkInterval(minusIntervals.get(0), 2.5, 3);
    639     }
    640
    641     @Test
    642     void testSplitDiameter_both_zeroOnPlusSide() {
    643         // arrange
    644         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    645         tree.add(AngularInterval.of(1, 1.1, TEST_PRECISION));
    646         tree.add(AngularInterval.of(2, 3, TEST_PRECISION));
    647
    648         final CutAngle splitter = CutAngles.createNegativeFacing(2.5, TEST_PRECISION);
    649
    650         // act
    651         final Split<RegionBSPTree1S> split = tree.splitDiameter(splitter);
    652
    653         // assert
    654         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
    655
    656         final RegionBSPTree1S minus = split.getMinus();
    657         final List<AngularInterval> minusIntervals = minus.toIntervals();
    658         Assertions.assertEquals(1, minusIntervals.size());
    659         checkInterval(minusIntervals.get(0), 2.5, 3);
    660
    661         final RegionBSPTree1S plus = split.getPlus();
    662         final List<AngularInterval> plusIntervals = plus.toIntervals();
    663         Assertions.assertEquals(2, plusIntervals.size());
    664         checkInterval(plusIntervals.get(0), 1, 1.1);
    665         checkInterval(plusIntervals.get(1), 2, 2.5);
    666     }
    667
    668     @Test
    669     void testRegionProperties_singleInterval_wrapsZero() {
    670         // arrange
    671         final RegionBSPTree1S tree = AngularInterval.of(-Angle.PI_OVER_TWO, Math.PI,
    672                 TEST_PRECISION).toTree();
    673
    674         // act/assert
    675         Assertions.assertEquals(1.5 * Math.PI, tree.getSize(), TEST_EPS);
    676         Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
    677         Assertions.assertEquals(0.25 * Math.PI, tree.getCentroid().getAzimuth(), TEST_EPS);
    678     }
    679
    680     @Test
    681     void testRegionProperties_singleInterval_doesNotWrap() {
    682         // arrange
    683         final RegionBSPTree1S tree = AngularInterval.of(Angle.PI_OVER_TWO, Angle.TWO_PI,
    684                 TEST_PRECISION).toTree();
    685
    686         // act/assert
    687         Assertions.assertEquals(1.5 * Math.PI, tree.getSize(), TEST_EPS);
    688         Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
    689         Assertions.assertEquals(1.25 * Math.PI, tree.getCentroid().getAzimuth(), TEST_EPS);
    690     }
    691
    692     @Test
    693     void testRegionProperties_multipleIntervals_sameSize() {
    694         // arrange
    695         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    696         tree.add(AngularInterval.of(0, 0.1, TEST_PRECISION));
    697         tree.add(AngularInterval.of(0.2, 0.3, TEST_PRECISION));
    698
    699         // act/assert
    700         Assertions.assertEquals(0.2, tree.getSize(), TEST_EPS);
    701         Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
    702         Assertions.assertEquals(0.15, tree.getCentroid().getAzimuth(), TEST_EPS);
    703     }
    704
    705     @Test
    706     void testRegionProperties_multipleIntervals_differentSizes() {
    707         // arrange
    708         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    709         tree.add(AngularInterval.of(0, 0.2, TEST_PRECISION));
    710         tree.add(AngularInterval.of(0.3, 0.7, TEST_PRECISION));
    711
    712         // act/assert
    713         Assertions.assertEquals(0.6, tree.getSize(), TEST_EPS);
    714         Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
    715
    716         final Vector2D centroidVector = Point1S.of(0.1).getVector().withNorm(0.2)
    717                 .add(Point1S.of(0.5).getVector().withNorm(0.4));
    718         Assertions.assertEquals(Point1S.from(centroidVector).getAzimuth(), tree.getCentroid().getAzimuth(), TEST_EPS);
    719     }
    720
    721     @Test
    722     void testRegionProperties_equalAndOppositeIntervals() {
    723         // arrange
    724         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    725         tree.add(AngularInterval.of(-1, 1, TEST_PRECISION));
    726         tree.add(AngularInterval.of(Math.PI - 1, Math.PI + 1, TEST_PRECISION));
    727
    728         // act/assert
    729         Assertions.assertEquals(4, tree.getSize(), TEST_EPS);
    730         Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
    731         Assertions.assertNull(tree.getCentroid()); // no unique centroid exists
    732     }
    733
    734     @Test
    735     void testTransform_fullAndEmpty() {
    736         // arrange
    737         final RegionBSPTree1S full = RegionBSPTree1S.full();
    738         final RegionBSPTree1S empty = RegionBSPTree1S.empty();
    739
    740         // act
    741         full.transform(PI_MINUS_AZ);
    742         empty.transform(HALF_PI_PLUS_AZ);
    743
    744         // assert
    745         Assertions.assertTrue(full.isFull());
    746         Assertions.assertFalse(full.isEmpty());
    747
    748         Assertions.assertFalse(empty.isFull());
    749         Assertions.assertTrue(empty.isEmpty());
    750     }
    751
    752     @Test
    753     void testTransform_halfPiPlusAz() {
    754         // arrange
    755         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    756         tree.add(AngularInterval.of(-1, 1, TEST_PRECISION));
    757         tree.add(AngularInterval.of(2, 3, TEST_PRECISION));
    758
    759         // act
    760         tree.transform(HALF_PI_PLUS_AZ);
    761
    762         // assert
    763         Assertions.assertEquals(3, tree.getSize(), TEST_EPS);
    764
    765         final List<AngularInterval> intervals = tree.toIntervals();
    766
    767         Assertions.assertEquals(2, intervals.size());
    768         checkInterval(intervals.get(0), Angle.PI_OVER_TWO - 1, Angle.PI_OVER_TWO + 1);
    769         checkInterval(intervals.get(1), Angle.PI_OVER_TWO + 2, Angle.PI_OVER_TWO + 3);
    770     }
    771
    772     @Test
    773     void testTransform_piMinusAz() {
    774         // arrange
    775         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    776         tree.add(AngularInterval.of(-1, 1, TEST_PRECISION));
    777         tree.add(AngularInterval.of(2, 3, TEST_PRECISION));
    778
    779         // act
    780         tree.transform(PI_MINUS_AZ);
    781
    782         // assert
    783         Assertions.assertEquals(3, tree.getSize(), TEST_EPS);
    784
    785         final List<AngularInterval> intervals = tree.toIntervals();
    786
    787         Assertions.assertEquals(2, intervals.size());
    788         checkInterval(intervals.get(0), Math.PI - 3, Math.PI - 2);
    789         checkInterval(intervals.get(1), Math.PI - 1, Math.PI + 1);
    790     }
    791
    792     @Test
    793     void testProject_fullAndEmpty() {
    794         // arrange
    795         final RegionBSPTree1S full = RegionBSPTree1S.full();
    796         final RegionBSPTree1S empty = RegionBSPTree1S.empty();
    797
    798         // act/assert
    799         Assertions.assertNull(full.project(Point1S.ZERO));
    800         Assertions.assertNull(full.project(Point1S.PI));
    801
    802         Assertions.assertNull(empty.project(Point1S.ZERO));
    803         Assertions.assertNull(empty.project(Point1S.PI));
    804     }
    805
    806     @Test
    807     void testProject_withIntervals() {
    808         // arrange
    809         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    810         tree.add(AngularInterval.of(-Angle.PI_OVER_TWO, Angle.PI_OVER_TWO, TEST_PRECISION));
    811         tree.add(AngularInterval.of(Math.PI - 1, Math.PI + 1, TEST_PRECISION));
    812
    813         // act/assert
    814         Assertions.assertEquals(-Angle.PI_OVER_TWO,
    815                 tree.project(Point1S.of(-Angle.PI_OVER_TWO - 0.1)).getAzimuth(), TEST_EPS);
    816         Assertions.assertEquals(-Angle.PI_OVER_TWO,
    817                 tree.project(Point1S.of(-Angle.PI_OVER_TWO)).getAzimuth(), TEST_EPS);
    818         Assertions.assertEquals(-Angle.PI_OVER_TWO,
    819                 tree.project(Point1S.of(-Angle.PI_OVER_TWO + 0.1)).getAzimuth(), TEST_EPS);
    820
    821         Assertions.assertEquals(-Angle.PI_OVER_TWO, tree.project(Point1S.of(-0.1)).getAzimuth(), TEST_EPS);
    822         Assertions.assertEquals(Angle.PI_OVER_TWO, tree.project(Point1S.ZERO).getAzimuth(), TEST_EPS);
    823         Assertions.assertEquals(Angle.PI_OVER_TWO, tree.project(Point1S.of(0.1)).getAzimuth(), TEST_EPS);
    824
    825         Assertions.assertEquals(Math.PI - 1,
    826                 tree.project(Point1S.of(Math.PI - 0.5)).getAzimuth(), TEST_EPS);
    827         Assertions.assertEquals(Math.PI + 1,
    828                 tree.project(Point1S.of(Math.PI + 0.5)).getAzimuth(), TEST_EPS);
    829     }
    830
    831     @Test
    832     void testProject_equidistant() {
    833         // arrange
    834         final RegionBSPTree1S tree = AngularInterval.of(1, 2, TEST_PRECISION).toTree();
    835         final RegionBSPTree1S treeComplement = tree.copy();
    836         treeComplement.complement();
    837
    838         // act/assert
    839         Assertions.assertEquals(1, tree.project(Point1S.of(1.5)).getAzimuth(), TEST_EPS);
    840         Assertions.assertEquals(1, treeComplement.project(Point1S.of(1.5)).getAzimuth(), TEST_EPS);
    841     }
    842
    843     @Test
    844     void testProject_intervalAroundZero_closerOnMinSide() {
    845         // arrange
    846         final double start = -1;
    847         final double end = 0.5;
    848         final RegionBSPTree1S tree = AngularInterval.of(start, end, TEST_PRECISION).toTree();
    849
    850         // act/assert
    851         Assertions.assertEquals(end, tree.project(Point1S.of(-1.5 * Math.PI)).getAzimuth(), TEST_EPS);
    852         Assertions.assertEquals(start, tree.project(Point1S.of(-Math.PI)).getAzimuth(), TEST_EPS);
    853         Assertions.assertEquals(start, tree.project(Point1S.of(-0.5 * Math.PI)).getAzimuth(), TEST_EPS);
    854         Assertions.assertEquals(start, tree.project(Point1S.of(-1)).getAzimuth(), TEST_EPS);
    855         Assertions.assertEquals(start, tree.project(Point1S.of(-0.5)).getAzimuth(), TEST_EPS);
    856         Assertions.assertEquals(end, tree.project(Point1S.of(-0.25)).getAzimuth(), TEST_EPS);
    857         Assertions.assertEquals(end, tree.project(Point1S.of(-0.1)).getAzimuth(), TEST_EPS);
    858         Assertions.assertEquals(end, tree.project(Point1S.ZERO).getAzimuth(), TEST_EPS);
    859         Assertions.assertEquals(end, tree.project(Point1S.of(0.1)).getAzimuth(), TEST_EPS);
    860         Assertions.assertEquals(end, tree.project(Point1S.of(0.25)).getAzimuth(), TEST_EPS);
    861         Assertions.assertEquals(end, tree.project(Point1S.of(0.5)).getAzimuth(), TEST_EPS);
    862         Assertions.assertEquals(end, tree.project(Point1S.of(0.75)).getAzimuth(), TEST_EPS);
    863     }
    864
    865     @Test
    866     void testProject_intervalAroundZero_closerOnMaxSide() {
    867         // arrange
    868         final double start = -0.5;
    869         final double end = 1;
    870         final RegionBSPTree1S tree = AngularInterval.of(start, end, TEST_PRECISION).toTree();
    871
    872         // act/assert
    873         Assertions.assertEquals(end, tree.project(Point1S.of(-1.5 * Math.PI)).getAzimuth(), TEST_EPS);
    874         Assertions.assertEquals(end, tree.project(Point1S.of(-Math.PI)).getAzimuth(), TEST_EPS);
    875         Assertions.assertEquals(start, tree.project(Point1S.of(-0.5 * Math.PI)).getAzimuth(), TEST_EPS);
    876         Assertions.assertEquals(start, tree.project(Point1S.of(-1)).getAzimuth(), TEST_EPS);
    877         Assertions.assertEquals(start, tree.project(Point1S.of(-0.5)).getAzimuth(), TEST_EPS);
    878         Assertions.assertEquals(start, tree.project(Point1S.of(-0.25)).getAzimuth(), TEST_EPS);
    879         Assertions.assertEquals(start, tree.project(Point1S.of(-0.1)).getAzimuth(), TEST_EPS);
    880         Assertions.assertEquals(start, tree.project(Point1S.ZERO).getAzimuth(), TEST_EPS);
    881         Assertions.assertEquals(start, tree.project(Point1S.of(0.1)).getAzimuth(), TEST_EPS);
    882         Assertions.assertEquals(end, tree.project(Point1S.of(0.25)).getAzimuth(), TEST_EPS);
    883         Assertions.assertEquals(end, tree.project(Point1S.of(0.5)).getAzimuth(), TEST_EPS);
    884         Assertions.assertEquals(end, tree.project(Point1S.of(0.75)).getAzimuth(), TEST_EPS);
    885     }
    886
    887     private static void checkSimpleSplit(final Split<RegionBSPTree1S> split, final AngularInterval minusInterval,
    888                                          final AngularInterval plusInterval) {
    889
    890         final RegionBSPTree1S minus = split.getMinus();
    891         if (minusInterval != null) {
    892             Assertions.assertNotNull(minus, "Expected minus region to not be null");
    893             checkSingleInterval(minus, minusInterval.getMin(), minusInterval.getMax());
    894         } else {
    895             Assertions.assertNull(minus, "Expected minus region to be null");
    896         }
    897
    898         final RegionBSPTree1S plus = split.getPlus();
    899         if (plusInterval != null) {
    900             Assertions.assertNotNull(plus, "Expected plus region to not be null");
    901             checkSingleInterval(plus, plusInterval.getMin(), plusInterval.getMax());
    902         } else {
    903             Assertions.assertNull(plus, "Expected plus region to be null");
    904         }
    905     }
    906
    907     private static void checkSingleInterval(final RegionBSPTree1S tree, final double min, final double max) {
    908         final List<AngularInterval> intervals = tree.toIntervals();
    909
    910         Assertions.assertEquals(1, intervals.size(), "Expected a single interval in the tree");
    911
    912         checkInterval(intervals.get(0), min, max);
    913     }
    914
    915     private static void checkInterval(final AngularInterval interval, final double min, final double max) {
    916         final double normalizedMin = Angle.Rad.WITHIN_0_AND_2PI.applyAsDouble(min);
    917         final double normalizedMax = Angle.Rad.WITHIN_0_AND_2PI.applyAsDouble(max);
    918
    919         if (TEST_PRECISION.eq(normalizedMin, normalizedMax)) {
    920             Assertions.assertTrue(interval.isFull());
    921         } else {
    922             Assertions.assertEquals(normalizedMin,
    923                     interval.getMinBoundary().getPoint().getNormalizedAzimuth(), TEST_EPS);
    924             Assertions.assertEquals(normalizedMax,
    925                     interval.getMaxBoundary().getPoint().getNormalizedAzimuth(), TEST_EPS);
    926         }
    927     }
    928
    929     private static void checkClassify(final Region<Point1S> region, final RegionLocation loc, final double... pts) {
    930         for (final double pt : pts) {
    931             Assertions.assertEquals(loc, region.classify(Point1S.of(pt)), "Unexpected location for point " + pt);
    932         }
    933     }
    934 }