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.twod;
    18
    19  import java.util.List;
    20
    21  import org.apache.commons.geometry.core.GeometryTestUtils;
    22  import org.apache.commons.geometry.core.RegionLocation;
    23  import org.apache.commons.geometry.core.partitioning.HyperplaneSubset;
    24  import org.apache.commons.geometry.core.partitioning.Split;
    25  import org.apache.commons.geometry.core.partitioning.SplitLocation;
    26  import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
    27  import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
    28  import org.apache.commons.geometry.euclidean.threed.Vector3D;
    29  import org.apache.commons.geometry.spherical.SphericalTestUtils;
    30  import org.apache.commons.geometry.spherical.oned.AngularInterval;
    31  import org.apache.commons.geometry.spherical.oned.RegionBSPTree1S;
    32  import org.apache.commons.numbers.angle.PlaneAngleRadians;
    33  import org.junit.Assert;
    34  import org.junit.Test;
    35
    36  public class EmbeddedTreeSubGreatCircleTest {
    37
    38      private static final double TEST_EPS = 1e-10;
    39
    40      private static final DoublePrecisionContext TEST_PRECISION =
    41              new EpsilonDoublePrecisionContext(TEST_EPS);
    42
    43      private static final GreatCircle XY_CIRCLE = GreatCircles.fromPoleAndU(
    44              Vector3D.Unit.PLUS_Z, Vector3D.Unit.PLUS_X, TEST_PRECISION);
    45
    46      @Test
    47      public void testCtor_default() {
    48          // act
    49          final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(XY_CIRCLE);
    50
    51          // assert
    52          Assert.assertFalse(sub.isFull());
    53          Assert.assertTrue(sub.isEmpty());
    54          Assert.assertTrue(sub.isFinite());
    55          Assert.assertFalse(sub.isInfinite());
    56
    57          Assert.assertEquals(0, sub.getSize(), TEST_EPS);
    58          Assert.assertNull(sub.getCentroid());
    59
    60          for (double az = 0; az <= PlaneAngleRadians.TWO_PI; az += 0.5) {
    61              for (double p = 0; p <= PlaneAngleRadians.PI; p += 0.5) {
    62                  checkClassify(sub, RegionLocation.OUTSIDE, Point2S.of(az, p));
    63              }
    64          }
    65      }
    66
    67      @Test
    68      public void testCtor_boolean_true() {
    69          // act
    70          final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(XY_CIRCLE, true);
    71
    72          // assert
    73          Assert.assertTrue(sub.isFull());
    74          Assert.assertFalse(sub.isEmpty());
    75          Assert.assertTrue(sub.isFinite());
    76          Assert.assertFalse(sub.isInfinite());
    77
    78          Assert.assertEquals(PlaneAngleRadians.TWO_PI, sub.getSize(), TEST_EPS);
    79          Assert.assertNull(sub.getCentroid());
    80
    81          for (double az = 0; az < PlaneAngleRadians.TWO_PI; az += 0.1) {
    82              checkClassify(sub, RegionLocation.INSIDE, Point2S.of(az, PlaneAngleRadians.PI_OVER_TWO));
    83          }
    84
    85          checkClassify(sub, RegionLocation.OUTSIDE,
    86                  Point2S.PLUS_K, Point2S.of(0, PlaneAngleRadians.PI_OVER_TWO + 0.1),
    87                  Point2S.MINUS_K, Point2S.of(0, PlaneAngleRadians.PI_OVER_TWO - 0.1));
    88      }
    89
    90      @Test
    91      public void testCtor_boolean_false() {
    92          // act
    93          final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(XY_CIRCLE, false);
    94
    95          // assert
    96          Assert.assertFalse(sub.isFull());
    97          Assert.assertTrue(sub.isEmpty());
    98          Assert.assertTrue(sub.isFinite());
    99          Assert.assertFalse(sub.isInfinite());
    100
    101         Assert.assertEquals(0, sub.getSize(), TEST_EPS);
    102         Assert.assertNull(sub.getCentroid());
    103
    104         for (double az = 0; az <= PlaneAngleRadians.TWO_PI; az += 0.5) {
    105             for (double p = 0; p <= PlaneAngleRadians.PI; p += 0.5) {
    106                 checkClassify(sub, RegionLocation.OUTSIDE, Point2S.of(az, p));
    107             }
    108         }
    109     }
    110
    111     @Test
    112     public void testCtor_tree() {
    113         // arrange
    114         final RegionBSPTree1S tree = RegionBSPTree1S.fromInterval(AngularInterval.of(1, 2, TEST_PRECISION));
    115
    116         // act
    117         final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(XY_CIRCLE, tree);
    118
    119         // assert
    120         Assert.assertFalse(sub.isFull());
    121         Assert.assertFalse(sub.isEmpty());
    122         Assert.assertTrue(sub.isFinite());
    123         Assert.assertFalse(sub.isInfinite());
    124
    125         Assert.assertEquals(1, sub.getSize(), TEST_EPS);
    126         SphericalTestUtils.assertPointsEq(Point2S.of(1.5, PlaneAngleRadians.PI_OVER_TWO),
    127                 sub.getCentroid(), TEST_EPS);
    128
    129         checkClassify(sub, RegionLocation.INSIDE, Point2S.of(1.5, PlaneAngleRadians.PI_OVER_TWO));
    130
    131         checkClassify(sub, RegionLocation.BOUNDARY,
    132                 Point2S.of(1, PlaneAngleRadians.PI_OVER_TWO), Point2S.of(2, PlaneAngleRadians.PI_OVER_TWO));
    133
    134         checkClassify(sub, RegionLocation.OUTSIDE,
    135                 Point2S.of(0.5, PlaneAngleRadians.PI_OVER_TWO), Point2S.of(2.5, PlaneAngleRadians.PI_OVER_TWO),
    136                 Point2S.of(1.5, 1), Point2S.of(1.5, PlaneAngleRadians.PI - 1));
    137     }
    138
    139     @Test
    140     public void testTransform() {
    141         // arrange
    142         final GreatCircle circle = GreatCircles.fromPoints(Point2S.PLUS_K, Point2S.MINUS_I, TEST_PRECISION);
    143         final RegionBSPTree1S region = RegionBSPTree1S.empty();
    144         region.add(AngularInterval.of(PlaneAngleRadians.PI, -PlaneAngleRadians.PI_OVER_TWO, TEST_PRECISION));
    145         region.add(AngularInterval.of(0, PlaneAngleRadians.PI_OVER_TWO, TEST_PRECISION));
    146
    147         final Transform2S t = Transform2S.createRotation(Point2S.PLUS_I, PlaneAngleRadians.PI_OVER_TWO)
    148                 .reflect(Point2S.of(-0.25 * PlaneAngleRadians.PI,  PlaneAngleRadians.PI_OVER_TWO));
    149
    150         final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle, region);
    151
    152         // act
    153         final EmbeddedTreeGreatCircleSubset result = sub.transform(t);
    154
    155         // assert
    156         final List<GreatArc> arcs = result.toConvex();
    157         Assert.assertEquals(2, arcs.size());
    158
    159         checkArc(arcs.get(0), Point2S.MINUS_I, Point2S.MINUS_J);
    160         checkArc(arcs.get(1), Point2S.PLUS_I, Point2S.PLUS_J);
    161     }
    162
    163     @Test
    164     public void testSplit_full() {
    165         // arrange
    166         final GreatCircle circle = GreatCircles.fromPoints(Point2S.PLUS_I, Point2S.PLUS_J, TEST_PRECISION);
    167         final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle, true);
    168
    169         final GreatCircle splitter = GreatCircles.fromPole(Vector3D.of(-1, 0, 1), TEST_PRECISION);
    170
    171         // act
    172         final Split<EmbeddedTreeGreatCircleSubset> split = sub.split(splitter);
    173
    174         // assert
    175         Assert.assertEquals(SplitLocation.BOTH, split.getLocation());
    176
    177         final EmbeddedTreeGreatCircleSubset minus = split.getMinus();
    178         Assert.assertSame(sub.getCircle(), minus.getCircle());
    179
    180         final List<GreatArc> minusArcs = minus.toConvex();
    181         Assert.assertEquals(1, minusArcs.size());
    182         checkArc(minusArcs.get(0), Point2S.MINUS_J, Point2S.PLUS_J);
    183
    184         checkClassify(minus, RegionLocation.OUTSIDE, Point2S.MINUS_I);
    185         checkClassify(minus, RegionLocation.INSIDE, Point2S.PLUS_I);
    186
    187         final EmbeddedTreeGreatCircleSubset plus = split.getPlus();
    188         Assert.assertSame(sub.getCircle(), plus.getCircle());
    189
    190         final List<GreatArc> plusArcs = plus.toConvex();
    191         Assert.assertEquals(1, plusArcs.size());
    192         checkArc(plusArcs.get(0), Point2S.PLUS_J, Point2S.MINUS_J);
    193
    194         checkClassify(plus, RegionLocation.INSIDE, Point2S.MINUS_I);
    195         checkClassify(plus, RegionLocation.OUTSIDE, Point2S.PLUS_I);
    196     }
    197
    198     @Test
    199     public void testSplit_empty() {
    200         // arrange
    201         final GreatCircle circle = GreatCircles.fromPoints(Point2S.PLUS_I, Point2S.PLUS_J, TEST_PRECISION);
    202         final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle, false);
    203
    204         final GreatCircle splitter = GreatCircles.fromPole(Vector3D.of(-1, 0, 1), TEST_PRECISION);
    205
    206         // act
    207         final Split<EmbeddedTreeGreatCircleSubset> split = sub.split(splitter);
    208
    209         // assert
    210         Assert.assertEquals(SplitLocation.NEITHER, split.getLocation());
    211
    212         final EmbeddedTreeGreatCircleSubset minus = split.getMinus();
    213         Assert.assertNull(minus);
    214
    215         final EmbeddedTreeGreatCircleSubset plus = split.getPlus();
    216         Assert.assertNull(plus);
    217     }
    218
    219     @Test
    220     public void testSplit_both() {
    221         // arrange
    222         final GreatCircle circle = GreatCircles.fromPoints(Point2S.PLUS_J, Point2S.PLUS_K, TEST_PRECISION);
    223
    224         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
    225         tree.add(AngularInterval.of(0, 1, TEST_PRECISION));
    226         tree.add(AngularInterval.of(PlaneAngleRadians.PI_OVER_TWO, PlaneAngleRadians.PI, TEST_PRECISION));
    227         tree.add(AngularInterval.of(PlaneAngleRadians.PI + 1, PlaneAngleRadians.PI + 2, TEST_PRECISION));
    228
    229         final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle, tree);
    230
    231         final GreatCircle splitter = GreatCircles.fromPole(Vector3D.of(0, 1, 1), TEST_PRECISION);
    232
    233         // act
    234         final Split<EmbeddedTreeGreatCircleSubset> split = sub.split(splitter);
    235
    236         // assert
    237         Assert.assertEquals(SplitLocation.BOTH, split.getLocation());
    238
    239         final EmbeddedTreeGreatCircleSubset minus = split.getMinus();
    240         Assert.assertSame(sub.getCircle(), minus.getCircle());
    241         final List<GreatArc> minusArcs = minus.toConvex();
    242         Assert.assertEquals(2, minusArcs.size());
    243         checkArc(minusArcs.get(0), Point2S.of(1.5 * PlaneAngleRadians.PI, 0.25 * PlaneAngleRadians.PI), Point2S.MINUS_J);
    244         checkArc(minusArcs.get(1), Point2S.of(1.5 * PlaneAngleRadians.PI, PlaneAngleRadians.PI_OVER_TWO + 1),
    245                 Point2S.of(0.5 * PlaneAngleRadians.PI, (1.5 * PlaneAngleRadians.PI) - 2));
    246
    247         final EmbeddedTreeGreatCircleSubset plus = split.getPlus();
    248         Assert.assertSame(sub.getCircle(), plus.getCircle());
    249         final List<GreatArc> plusArcs = plus.toConvex();
    250         Assert.assertEquals(2, plusArcs.size());
    251         checkArc(plusArcs.get(0), Point2S.of(PlaneAngleRadians.PI_OVER_TWO, PlaneAngleRadians.PI_OVER_TWO), Point2S.of(PlaneAngleRadians.PI_OVER_TWO, PlaneAngleRadians.PI_OVER_TWO - 1));
    252         checkArc(plusArcs.get(1), Point2S.of(0, 0), Point2S.of(1.5 * PlaneAngleRadians.PI, 0.25 * PlaneAngleRadians.PI));
    253     }
    254
    255     @Test
    256     public void testSplit_minus() {
    257         // arrange
    258         final GreatCircle circle = GreatCircles.fromPoints(Point2S.PLUS_J, Point2S.PLUS_K, TEST_PRECISION);
    259         final RegionBSPTree1S tree = AngularInterval.of(PlaneAngleRadians.PI_OVER_TWO, PlaneAngleRadians.PI, TEST_PRECISION).toTree();
    260
    261         final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle, tree);
    262
    263         final GreatCircle splitter = GreatCircles.fromPole(Vector3D.Unit.from(-1, 0, -1), TEST_PRECISION);
    264
    265         // act
    266         final Split<EmbeddedTreeGreatCircleSubset> split = sub.split(splitter);
    267
    268         // assert
    269         Assert.assertEquals(SplitLocation.MINUS, split.getLocation());
    270
    271         final EmbeddedTreeGreatCircleSubset minus = split.getMinus();
    272         Assert.assertSame(sub, minus);
    273
    274         final EmbeddedTreeGreatCircleSubset plus = split.getPlus();
    275         Assert.assertNull(plus);
    276     }
    277
    278     @Test
    279     public void testSplit_plus() {
    280         // arrange
    281         final GreatCircle circle = GreatCircles.fromPoints(Point2S.PLUS_J, Point2S.PLUS_K, TEST_PRECISION);
    282         final RegionBSPTree1S tree = AngularInterval.of(PlaneAngleRadians.PI_OVER_TWO, PlaneAngleRadians.PI, TEST_PRECISION).toTree();
    283
    284         final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle, tree);
    285
    286         final GreatCircle splitter = GreatCircles.fromPole(Vector3D.Unit.PLUS_Z, TEST_PRECISION);
    287
    288         // act
    289         final Split<EmbeddedTreeGreatCircleSubset> split = sub.split(splitter);
    290
    291         // assert
    292         Assert.assertEquals(SplitLocation.PLUS, split.getLocation());
    293
    294         final EmbeddedTreeGreatCircleSubset minus = split.getMinus();
    295         Assert.assertNull(minus);
    296
    297         final EmbeddedTreeGreatCircleSubset plus = split.getPlus();
    298         Assert.assertSame(sub, plus);
    299     }
    300
    301     @Test
    302     public void testSplit_parallelAndAntiparallel() {
    303         // arrange
    304         final GreatCircle circle = GreatCircles.fromPoints(Point2S.PLUS_I, Point2S.PLUS_J, TEST_PRECISION);
    305         final RegionBSPTree1S tree = AngularInterval.of(PlaneAngleRadians.PI_OVER_TWO, PlaneAngleRadians.PI, TEST_PRECISION).toTree();
    306
    307         final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle, tree);
    308
    309         // act/assert
    310         Assert.assertEquals(SplitLocation.NEITHER,
    311                 sub.split(GreatCircles.fromPole(Vector3D.Unit.PLUS_Z, TEST_PRECISION)).getLocation());
    312         Assert.assertEquals(SplitLocation.NEITHER,
    313                 sub.split(GreatCircles.fromPole(Vector3D.Unit.MINUS_Z, TEST_PRECISION)).getLocation());
    314     }
    315
    316     @Test
    317     public void testAdd_arc() {
    318         // arrange
    319         final GreatCircle circle = GreatCircles.fromPoints(Point2S.MINUS_K, Point2S.MINUS_J, TEST_PRECISION);
    320         final GreatCircle closeCircle = GreatCircles.fromPoints(Point2S.MINUS_K,
    321                 Point2S.of((1.5 * PlaneAngleRadians.PI) - 1e-11, PlaneAngleRadians.PI_OVER_TWO), TEST_PRECISION);
    322
    323         final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle);
    324
    325         // act
    326         sub.add(circle.arc(Point2S.of(1.5 * PlaneAngleRadians.PI, 0.75 * PlaneAngleRadians.PI), Point2S.MINUS_J));
    327         sub.add(closeCircle.arc(Point2S.PLUS_J, Point2S.of(1.5 * PlaneAngleRadians.PI, 0.75 * PlaneAngleRadians.PI)));
    328
    329         // assert
    330         final List<GreatArc> arcs = sub.toConvex();
    331
    332         Assert.assertEquals(1, arcs.size());
    333         checkArc(arcs.get(0), Point2S.PLUS_J, Point2S.MINUS_J);
    334     }
    335
    336     @Test(expected = IllegalArgumentException.class)
    337     public void testAdd_arc_differentCircle() {
    338         // arrange
    339         final GreatCircle circle = GreatCircles.fromPoints(Point2S.MINUS_K, Point2S.MINUS_J, TEST_PRECISION);
    340         final GreatCircle otherCircle = GreatCircles.fromPoints(Point2S.MINUS_K,
    341                 Point2S.of((1.5 * PlaneAngleRadians.PI) - 1e-2, PlaneAngleRadians.PI_OVER_TWO), TEST_PRECISION);
    342
    343         final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle);
    344
    345         // act/assert
    346         sub.add(otherCircle.arc(Point2S.PLUS_J, Point2S.of(1.5 * PlaneAngleRadians.PI, 0.75 * PlaneAngleRadians.PI)));
    347     }
    348
    349     @Test
    350     public void testAdd_subGreatCircle() {
    351         // arrange
    352         final GreatCircle circle = GreatCircles.fromPoints(Point2S.MINUS_K, Point2S.MINUS_J, TEST_PRECISION);
    353         final GreatCircle closeCircle = GreatCircles.fromPoints(Point2S.MINUS_K,
    354                 Point2S.of((1.5 * PlaneAngleRadians.PI) - 1e-11, PlaneAngleRadians.PI_OVER_TWO), TEST_PRECISION);
    355
    356         final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle);
    357
    358         final RegionBSPTree1S regionA = RegionBSPTree1S.empty();
    359         regionA.add(AngularInterval.of(PlaneAngleRadians.PI, 1.25 * PlaneAngleRadians.PI, TEST_PRECISION));
    360         regionA.add(AngularInterval.of(0.25 * PlaneAngleRadians.PI, PlaneAngleRadians.PI_OVER_TWO, TEST_PRECISION));
    361
    362         final RegionBSPTree1S regionB = RegionBSPTree1S.empty();
    363         regionB.add(AngularInterval.of(1.5 * PlaneAngleRadians.PI, 0.25 * PlaneAngleRadians.PI, TEST_PRECISION));
    364
    365         // act
    366         sub.add(new EmbeddedTreeGreatCircleSubset(circle, regionA));
    367         sub.add(new EmbeddedTreeGreatCircleSubset(closeCircle, regionB));
    368
    369         // assert
    370         final List<GreatArc> arcs = sub.toConvex();
    371
    372         Assert.assertEquals(2, arcs.size());
    373         checkArc(arcs.get(0), Point2S.of(PlaneAngleRadians.PI_OVER_TWO, 0), Point2S.of(PlaneAngleRadians.PI_OVER_TWO, 0.25 * PlaneAngleRadians.PI));
    374         checkArc(arcs.get(1), Point2S.PLUS_J, Point2S.MINUS_J);
    375     }
    376
    377     @Test(expected = IllegalArgumentException.class)
    378     public void testAdd_subGreatCircle_otherCircle() {
    379         // arrange
    380         final GreatCircle circle = GreatCircles.fromPoints(Point2S.MINUS_K, Point2S.MINUS_J, TEST_PRECISION);
    381         final GreatCircle otherCircle = GreatCircles.fromPoints(Point2S.MINUS_K,
    382                 Point2S.of((1.5 * PlaneAngleRadians.PI) - 1e-5, PlaneAngleRadians.PI_OVER_TWO), TEST_PRECISION);
    383
    384         final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle);
    385
    386         // act/assert
    387         sub.add(new EmbeddedTreeGreatCircleSubset(otherCircle, RegionBSPTree1S.full()));
    388     }
    389
    390     @Test
    391     public void testToString() {
    392         // arrange
    393         final GreatCircle circle = GreatCircles.fromPoints(Point2S.PLUS_I, Point2S.PLUS_J, TEST_PRECISION);
    394         final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle);
    395
    396         // act
    397         final String str = sub.toString();
    398
    399         // assert
    400         GeometryTestUtils.assertContains("EmbeddedTreeGreatCircleSubset[", str);
    401         GeometryTestUtils.assertContains("circle= GreatCircle[", str);
    402         GeometryTestUtils.assertContains("region= RegionBSPTree1S[", str);
    403     }
    404
    405     private static void checkClassify(final HyperplaneSubset<Point2S> sub, final RegionLocation loc, final Point2S... pts) {
    406         for (final Point2S pt : pts) {
    407             Assert.assertEquals("Unexpected location for point " + pt, loc, sub.classify(pt));
    408         }
    409     }
    410
    411     private static void checkArc(final GreatArc arc, final Point2S start, final Point2S end) {
    412         SphericalTestUtils.assertPointsEq(start, arc.getStartPoint(), TEST_EPS);
    413         SphericalTestUtils.assertPointsEq(end, arc.getEndPoint(), TEST_EPS);
    414     }
    415 }