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