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.ArrayList;
    20  import java.util.Arrays;
    21  import java.util.Collections;
    22  import java.util.List;
    23  import java.util.stream.Collectors;
    24
    25  import org.apache.commons.geometry.core.RegionLocation;
    26  import org.apache.commons.geometry.core.partitioning.Split;
    27  import org.apache.commons.geometry.core.partitioning.SplitLocation;
    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.Point1S;
    31  import org.apache.commons.numbers.angle.Angle;
    32  import org.apache.commons.numbers.core.Precision;
    33  import org.junit.jupiter.api.Assertions;
    34  import org.junit.jupiter.api.Test;
    35
    36  class ConvexArea2STest {
    37
    38      private static final double TEST_EPS = 1e-10;
    39
    40      private static final Precision.DoubleEquivalence TEST_PRECISION =
    41              Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
    42
    43      @Test
    44      void testFull() {
    45          // act
    46          final ConvexArea2S area = ConvexArea2S.full();
    47
    48          // assert
    49          Assertions.assertTrue(area.isFull());
    50          Assertions.assertFalse(area.isEmpty());
    51          Assertions.assertEquals(0, area.getBoundarySize(), TEST_EPS);
    52          Assertions.assertEquals(4 * Math.PI, area.getSize(), TEST_EPS);
    53          Assertions.assertNull(area.getCentroid());
    54
    55          Assertions.assertEquals(0, area.getBoundaries().size());
    56
    57          SphericalTestUtils.checkClassify(area, RegionLocation.INSIDE,
    58                  Point2S.PLUS_I, Point2S.MINUS_I,
    59                  Point2S.PLUS_J, Point2S.MINUS_J,
    60                  Point2S.PLUS_K, Point2S.MINUS_K);
    61      }
    62
    63      @Test
    64      void testFromBounds_empty() {
    65          // act
    66          final ConvexArea2S area = ConvexArea2S.fromBounds();
    67
    68          // assert
    69          Assertions.assertTrue(area.isFull());
    70          Assertions.assertFalse(area.isEmpty());
    71          Assertions.assertEquals(0, area.getBoundarySize(), TEST_EPS);
    72          Assertions.assertEquals(4 * Math.PI, area.getSize(), TEST_EPS);
    73          Assertions.assertNull(area.getCentroid());
    74
    75          Assertions.assertEquals(0, area.getBoundaries().size());
    76
    77          SphericalTestUtils.checkClassify(area, RegionLocation.INSIDE,
    78                  Point2S.PLUS_I, Point2S.MINUS_I,
    79                  Point2S.PLUS_J, Point2S.MINUS_J,
    80                  Point2S.PLUS_K, Point2S.MINUS_K);
    81      }
    82
    83      @Test
    84      void testFromBounds_singleBound() {
    85          // arrange
    86          final GreatCircle circle = GreatCircles.fromPoints(Point2S.PLUS_K, Point2S.PLUS_I, TEST_PRECISION);
    87
    88          // act
    89          final ConvexArea2S area = ConvexArea2S.fromBounds(circle);
    90
    91          // assert
    92          Assertions.assertFalse(area.isFull());
    93          Assertions.assertFalse(area.isEmpty());
    94          Assertions.assertEquals(2 * Math.PI, area.getBoundarySize(), TEST_EPS);
    95          Assertions.assertEquals(2 * Math.PI, area.getSize(), TEST_EPS);
    96          SphericalTestUtils.assertPointsEq(Point2S.PLUS_J, area.getCentroid(), TEST_EPS);
    97          checkCentroidConsistency(area);
    98
    99          Assertions.assertEquals(1, area.getBoundaries().size());
    100         final GreatArc arc = area.getBoundaries().get(0);
    101         Assertions.assertTrue(arc.isFull());
    102         SphericalTestUtils.assertPointsEq(Point2S.PLUS_J, arc.getCircle().getPolePoint(), TEST_EPS);
    103
    104         SphericalTestUtils.checkClassify(area, RegionLocation.INSIDE, Point2S.PLUS_J);
    105
    106         SphericalTestUtils.checkClassify(area, RegionLocation.BOUNDARY,
    107                 Point2S.PLUS_I, Point2S.MINUS_I,
    108                 Point2S.PLUS_K, Point2S.MINUS_K);
    109
    110         SphericalTestUtils.checkClassify(area, RegionLocation.OUTSIDE, Point2S.MINUS_J);
    111     }
    112
    113     @Test
    114     void testFromBounds_lune_intersectionAtPoles() {
    115         // arrange
    116         final GreatCircle a = GreatCircles.fromPoints(Point2S.PLUS_K, Point2S.PLUS_I, TEST_PRECISION);
    117         final GreatCircle b = GreatCircles.fromPoints(
    118                 Point2S.of(0.25 * Math.PI, Angle.PI_OVER_TWO), Point2S.PLUS_K, TEST_PRECISION);
    119
    120         // act
    121         final ConvexArea2S area = ConvexArea2S.fromBounds(a, b);
    122
    123         // assert
    124         Assertions.assertFalse(area.isFull());
    125         Assertions.assertFalse(area.isEmpty());
    126         Assertions.assertEquals(2 * Math.PI, area.getBoundarySize(), TEST_EPS);
    127         Assertions.assertEquals(Angle.PI_OVER_TWO, area.getSize(), TEST_EPS);
    128         SphericalTestUtils.assertPointsEq(Point2S.of(0.125 * Math.PI, Angle.PI_OVER_TWO),
    129                 area.getCentroid(), TEST_EPS);
    130         checkCentroidConsistency(area);
    131
    132         final List<GreatArc> arcs = sortArcs(area.getBoundaries());
    133         Assertions.assertEquals(2, arcs.size());
    134         checkArc(arcs.get(0), Point2S.PLUS_K, Point2S.MINUS_K);
    135         checkArc(arcs.get(1), Point2S.MINUS_K, Point2S.PLUS_K);
    136
    137         SphericalTestUtils.checkClassify(area, RegionLocation.INSIDE,
    138                 Point2S.of(0.125 * Math.PI, 0.1),
    139                 Point2S.of(0.125 * Math.PI, Angle.PI_OVER_TWO),
    140                 Point2S.of(0.125 * Math.PI, Math.PI - 0.1));
    141
    142         SphericalTestUtils.checkClassify(area, RegionLocation.BOUNDARY,
    143                 Point2S.PLUS_I, Point2S.of(0.25 * Math.PI, Angle.PI_OVER_TWO),
    144                 Point2S.PLUS_K, Point2S.MINUS_K);
    145
    146         SphericalTestUtils.checkClassify(area, RegionLocation.OUTSIDE,
    147                 Point2S.PLUS_J, Point2S.MINUS_J);
    148     }
    149
    150     @Test
    151     void testFromBounds_lune_intersectionAtEquator() {
    152         // arrange
    153         final GreatCircle a = GreatCircles.fromPoints(Point2S.PLUS_I, Point2S.PLUS_J, TEST_PRECISION);
    154         final GreatCircle b = GreatCircles.fromPoints(Point2S.PLUS_J, Point2S.PLUS_K, TEST_PRECISION);
    155
    156         // act
    157         final ConvexArea2S area = ConvexArea2S.fromBounds(a, b);
    158
    159         // assert
    160         Assertions.assertFalse(area.isFull());
    161         Assertions.assertFalse(area.isEmpty());
    162         Assertions.assertEquals(2 * Math.PI, area.getBoundarySize(), TEST_EPS);
    163         Assertions.assertEquals(Math.PI, area.getSize(), TEST_EPS);
    164         SphericalTestUtils.assertPointsEq(Point2S.of(0, 0.25 * Math.PI), area.getCentroid(), TEST_EPS);
    165         checkCentroidConsistency(area);
    166
    167         final List<GreatArc> arcs = sortArcs(area.getBoundaries());
    168         Assertions.assertEquals(2, arcs.size());
    169         checkArc(arcs.get(0), Point2S.PLUS_J, Point2S.MINUS_J);
    170         checkArc(arcs.get(1), Point2S.MINUS_J, Point2S.PLUS_J);
    171
    172         SphericalTestUtils.checkClassify(area, RegionLocation.INSIDE,
    173                 Point2S.of(0, 0.25 * Math.PI),
    174                 Point2S.of(0.25, 0.4 * Math.PI),
    175                 Point2S.of(-0.25, 0.4 * Math.PI));
    176
    177         SphericalTestUtils.checkClassify(area, RegionLocation.BOUNDARY,
    178                 Point2S.PLUS_I, Point2S.PLUS_K,
    179                 Point2S.PLUS_J, Point2S.MINUS_J);
    180
    181         SphericalTestUtils.checkClassify(area, RegionLocation.OUTSIDE,
    182                 Point2S.MINUS_I, Point2S.MINUS_K,
    183                 Point2S.of(Math.PI, 0.25 * Math.PI),
    184                 Point2S.of(Math.PI, 0.75 * Math.PI));
    185     }
    186
    187     @Test
    188     void testFromBounds_triangle_large() {
    189         // arrange
    190         final GreatCircle a = GreatCircles.fromPole(Vector3D.Unit.PLUS_X, TEST_PRECISION);
    191         final GreatCircle b = GreatCircles.fromPole(Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    192         final GreatCircle c = GreatCircles.fromPole(Vector3D.Unit.PLUS_Z, TEST_PRECISION);
    193
    194         // act
    195         final ConvexArea2S area = ConvexArea2S.fromBounds(Arrays.asList(a, b, c));
    196
    197         // assert
    198         Assertions.assertFalse(area.isFull());
    199         Assertions.assertFalse(area.isEmpty());
    200         Assertions.assertEquals(1.5 * Math.PI, area.getBoundarySize(), TEST_EPS);
    201         Assertions.assertEquals(Angle.PI_OVER_TWO, area.getSize(), TEST_EPS);
    202
    203         final Point2S expectedCentroid = triangleCentroid(Point2S.PLUS_I, Point2S.PLUS_J, Point2S.PLUS_K);
    204         SphericalTestUtils.assertPointsEq(expectedCentroid, area.getCentroid(), TEST_EPS);
    205
    206         checkCentroidConsistency(area);
    207
    208         final List<GreatArc> arcs = sortArcs(area.getBoundaries());
    209         Assertions.assertEquals(3, arcs.size());
    210         checkArc(arcs.get(0), Point2S.PLUS_K, Point2S.PLUS_I);
    211         checkArc(arcs.get(1), Point2S.PLUS_I, Point2S.PLUS_J);
    212         checkArc(arcs.get(2), Point2S.PLUS_J, Point2S.PLUS_K);
    213
    214         SphericalTestUtils.checkClassify(area, RegionLocation.INSIDE,
    215                 Point2S.of(0.25 * Math.PI, 0.25 * Math.PI));
    216
    217         SphericalTestUtils.checkClassify(area, RegionLocation.BOUNDARY,
    218                 Point2S.PLUS_I, Point2S.PLUS_J, Point2S.PLUS_K,
    219                 Point2S.of(0, 0.25 * Math.PI), Point2S.of(Angle.PI_OVER_TWO, 0.304 * Math.PI),
    220                 Point2S.of(0.25 * Math.PI, Angle.PI_OVER_TWO));
    221
    222         SphericalTestUtils.checkClassify(area, RegionLocation.OUTSIDE,
    223                 Point2S.MINUS_I, Point2S.MINUS_J, Point2S.MINUS_K);
    224     }
    225
    226     @Test
    227     void testFromBounds_triangle_small() {
    228         // arrange
    229         final double azMin = 1.12 * Math.PI;
    230         final double azMax = 1.375 * Math.PI;
    231         final double azMid = 0.5 * (azMin + azMax);
    232         final double polarTop = 0.1;
    233         final double polarBottom = 0.25 * Math.PI;
    234
    235         final Point2S p1 = Point2S.of(azMin, polarBottom);
    236         final Point2S p2 = Point2S.of(azMax, polarBottom);
    237         final Point2S p3 = Point2S.of(azMid, polarTop);
    238
    239         final GreatCircle a = GreatCircles.fromPoints(p1, p2, TEST_PRECISION);
    240         final GreatCircle b = GreatCircles.fromPoints(p2, p3, TEST_PRECISION);
    241         final GreatCircle c = GreatCircles.fromPoints(p3, p1, TEST_PRECISION);
    242
    243         // act
    244         final ConvexArea2S area = ConvexArea2S.fromBounds(Arrays.asList(a, b, c));
    245
    246         // assert
    247         Assertions.assertFalse(area.isFull());
    248         Assertions.assertFalse(area.isEmpty());
    249         Assertions.assertEquals(p1.distance(p2) + p2.distance(p3) + p3.distance(p1),
    250                 area.getBoundarySize(), TEST_EPS);
    251         final double size = Angle.TWO_PI - a.angle(b) - b.angle(c) - c.angle(a);
    252         Assertions.assertEquals(size, area.getSize(), TEST_EPS);
    253
    254         final Point2S expectedCentroid = triangleCentroid(p1, p2, p3);
    255         SphericalTestUtils.assertPointsEq(expectedCentroid, area.getCentroid(), TEST_EPS);
    256
    257         checkCentroidConsistency(area);
    258
    259         final List<GreatArc> arcs = sortArcs(area.getBoundaries());
    260         Assertions.assertEquals(3, arcs.size());
    261
    262         checkArc(arcs.get(0), p3, p1);
    263         checkArc(arcs.get(1), p1, p2);
    264         checkArc(arcs.get(2), p2, p3);
    265
    266         SphericalTestUtils.checkClassify(area, RegionLocation.INSIDE, Point2S.of(azMid, 0.11));
    267
    268         SphericalTestUtils.checkClassify(area, RegionLocation.BOUNDARY,
    269                 p1, p2, p3, p1.slerp(p2, 0.2));
    270
    271         SphericalTestUtils.checkClassify(area, RegionLocation.OUTSIDE,
    272                 Point2S.PLUS_I, Point2S.PLUS_J, Point2S.PLUS_K,
    273                 Point2S.MINUS_I, Point2S.MINUS_J, Point2S.MINUS_K);
    274     }
    275
    276     @Test
    277     void testFromBounds_quad() {
    278         // arrange
    279         final Point2S p1 = Point2S.of(0.2, 0.1);
    280         final Point2S p2 = Point2S.of(0.1, 0.2);
    281         final Point2S p3 = Point2S.of(0.2, 0.5);
    282         final Point2S p4 = Point2S.of(0.3, 0.2);
    283
    284         final GreatCircle c1 = GreatCircles.fromPoints(p1, p2, TEST_PRECISION);
    285         final GreatCircle c2 = GreatCircles.fromPoints(p2, p3, TEST_PRECISION);
    286         final GreatCircle c3 = GreatCircles.fromPoints(p3, p4, TEST_PRECISION);
    287         final GreatCircle c4 = GreatCircles.fromPoints(p4, p1, TEST_PRECISION);
    288
    289         // act
    290         final ConvexArea2S area = ConvexArea2S.fromBounds(c1, c2, c3, c4);
    291
    292         // assert
    293         Assertions.assertFalse(area.isFull());
    294         Assertions.assertFalse(area.isEmpty());
    295         Assertions.assertEquals(p1.distance(p2) + p2.distance(p3) + p3.distance(p4) + p4.distance(p1),
    296                 area.getBoundarySize(), TEST_EPS);
    297
    298         final double size = 2 * Math.PI - c1.angle(c2) - c2.angle(c3) - c3.angle(c4) - c4.angle(c1);
    299         Assertions.assertEquals(size, area.getSize(), TEST_EPS);
    300
    301         checkCentroidConsistency(area);
    302
    303         final List<GreatArc> arcs = sortArcs(area.getBoundaries());
    304         Assertions.assertEquals(4, arcs.size());
    305
    306         checkArc(arcs.get(0), p1, p2);
    307         checkArc(arcs.get(1), p2, p3);
    308         checkArc(arcs.get(2), p4, p1);
    309         checkArc(arcs.get(3), p3, p4);
    310
    311         SphericalTestUtils.checkClassify(area, RegionLocation.INSIDE, Point2S.of(0.2, 0.11));
    312
    313         SphericalTestUtils.checkClassify(area, RegionLocation.BOUNDARY,
    314                 p1, p2, p3, p4, p1.slerp(p2, 0.2));
    315
    316         SphericalTestUtils.checkClassify(area, RegionLocation.OUTSIDE,
    317                 Point2S.PLUS_I, Point2S.PLUS_J, Point2S.PLUS_K,
    318                 Point2S.MINUS_I, Point2S.MINUS_J, Point2S.MINUS_K);
    319     }
    320
    321     @Test
    322     void testFromPath_empty() {
    323         // act
    324         final ConvexArea2S area = ConvexArea2S.fromPath(GreatArcPath.empty());
    325
    326         // assert
    327         Assertions.assertSame(ConvexArea2S.full(), area);
    328     }
    329
    330     @Test
    331     void testFromPath() {
    332         // arrange
    333         final GreatArcPath path = GreatArcPath.builder(TEST_PRECISION)
    334                 .append(Point2S.MINUS_I)
    335                 .append(Point2S.MINUS_K)
    336                 .append(Point2S.MINUS_J)
    337                 .close();
    338
    339         // act
    340         final ConvexArea2S area = ConvexArea2S.fromPath(path);
    341
    342         // assert
    343         Assertions.assertFalse(area.isFull());
    344         Assertions.assertFalse(area.isEmpty());
    345         Assertions.assertEquals(1.5 * Math.PI, area.getBoundarySize(), TEST_EPS);
    346         Assertions.assertEquals(Angle.PI_OVER_TWO, area.getSize(), TEST_EPS);
    347
    348         final Point2S expectedCentroid = triangleCentroid(Point2S.MINUS_I, Point2S.MINUS_K, Point2S.MINUS_J);
    349         SphericalTestUtils.assertPointsEq(expectedCentroid, area.getCentroid(), TEST_EPS);
    350
    351         checkCentroidConsistency(area);
    352
    353         final List<GreatArc> arcs = sortArcs(area.getBoundaries());
    354         Assertions.assertEquals(3, arcs.size());
    355         checkArc(arcs.get(0), Point2S.MINUS_I, Point2S.MINUS_K);
    356         checkArc(arcs.get(1), Point2S.MINUS_J, Point2S.MINUS_I);
    357         checkArc(arcs.get(2), Point2S.MINUS_K, Point2S.MINUS_J);
    358
    359         SphericalTestUtils.checkClassify(area, RegionLocation.INSIDE,
    360                 Point2S.of(1.25 * Math.PI, 0.75 * Math.PI));
    361
    362         SphericalTestUtils.checkClassify(area, RegionLocation.BOUNDARY,
    363                 Point2S.MINUS_I, Point2S.MINUS_J, Point2S.MINUS_K);
    364
    365         SphericalTestUtils.checkClassify(area, RegionLocation.OUTSIDE,
    366                 Point2S.PLUS_I, Point2S.PLUS_J, Point2S.PLUS_K);
    367     }
    368
    369     @Test
    370     void testFromVertices_empty() {
    371         // act
    372         final ConvexArea2S area = ConvexArea2S.fromVertices(Collections.emptyList(), TEST_PRECISION);
    373
    374         // assert
    375         Assertions.assertSame(ConvexArea2S.full(), area);
    376     }
    377
    378     @Test
    379     void testFromVertices() {
    380         // arrange
    381         final Point2S p1 = Point2S.PLUS_I;
    382         final Point2S p2 = Point2S.PLUS_J;
    383         final Point2S p3 = Point2S.PLUS_K;
    384
    385         // act
    386         final ConvexArea2S area = ConvexArea2S.fromVertices(Arrays.asList(p1, p2, p3), TEST_PRECISION);
    387
    388         // assert
    389         Assertions.assertFalse(area.isFull());
    390         Assertions.assertFalse(area.isEmpty());
    391         Assertions.assertEquals(2 * Math.PI, area.getBoundarySize(), TEST_EPS);
    392         Assertions.assertEquals(Math.PI, area.getSize(), TEST_EPS);
    393         SphericalTestUtils.assertPointsEq(Point2S.of(0, 0.25 * Math.PI), area.getCentroid(), TEST_EPS);
    394         checkCentroidConsistency(area);
    395
    396         final List<GreatArc> arcs = sortArcs(area.getBoundaries());
    397         Assertions.assertEquals(2, arcs.size());
    398         checkArc(arcs.get(0), Point2S.PLUS_J, Point2S.MINUS_J);
    399         checkArc(arcs.get(1), Point2S.MINUS_J, Point2S.PLUS_J);
    400
    401         SphericalTestUtils.checkClassify(area, RegionLocation.INSIDE,
    402                 Point2S.of(-0.25 * Math.PI, 0.25 * Math.PI),
    403                 Point2S.of(0, 0.25 * Math.PI),
    404                 Point2S.of(0.25 * Math.PI, 0.25 * Math.PI));
    405
    406         SphericalTestUtils.checkClassify(area, RegionLocation.BOUNDARY,
    407                 Point2S.PLUS_I, Point2S.PLUS_J,
    408                 Point2S.PLUS_K, Point2S.MINUS_J);
    409
    410         SphericalTestUtils.checkClassify(area, RegionLocation.OUTSIDE,
    411                 Point2S.MINUS_I, Point2S.MINUS_K);
    412     }
    413
    414     @Test
    415     void testFromVertices_lastVertexRepeated() {
    416         // arrange
    417         final Point2S p1 = Point2S.PLUS_I;
    418         final Point2S p2 = Point2S.PLUS_J;
    419         final Point2S p3 = Point2S.PLUS_K;
    420
    421         // act
    422         final ConvexArea2S area = ConvexArea2S.fromVertices(Arrays.asList(p1, p2, p3, p1), TEST_PRECISION);
    423
    424         // assert
    425         Assertions.assertFalse(area.isFull());
    426         Assertions.assertFalse(area.isEmpty());
    427         Assertions.assertEquals(1.5 * Math.PI, area.getBoundarySize(), TEST_EPS);
    428         Assertions.assertEquals(Angle.PI_OVER_TWO, area.getSize(), TEST_EPS);
    429
    430         final Point2S expectedCentroid = triangleCentroid(Point2S.PLUS_I, Point2S.PLUS_J, Point2S.PLUS_K);
    431         SphericalTestUtils.assertPointsEq(expectedCentroid, area.getCentroid(), TEST_EPS);
    432
    433         checkCentroidConsistency(area);
    434
    435         final List<GreatArc> arcs = sortArcs(area.getBoundaries());
    436         Assertions.assertEquals(3, arcs.size());
    437         checkArc(arcs.get(0), Point2S.PLUS_K, Point2S.PLUS_I);
    438         checkArc(arcs.get(1), Point2S.PLUS_I, Point2S.PLUS_J);
    439         checkArc(arcs.get(2), Point2S.PLUS_J, Point2S.PLUS_K);
    440
    441         SphericalTestUtils.checkClassify(area, RegionLocation.INSIDE,
    442                 Point2S.of(0.25 * Math.PI, 0.25 * Math.PI));
    443
    444         SphericalTestUtils.checkClassify(area, RegionLocation.BOUNDARY,
    445                 Point2S.PLUS_I, Point2S.PLUS_J, Point2S.PLUS_K,
    446                 Point2S.of(0, 0.25 * Math.PI), Point2S.of(Angle.PI_OVER_TWO, 0.304 * Math.PI),
    447                 Point2S.of(0.25 * Math.PI, Angle.PI_OVER_TWO));
    448
    449         SphericalTestUtils.checkClassify(area, RegionLocation.OUTSIDE,
    450                 Point2S.MINUS_I, Point2S.MINUS_J, Point2S.MINUS_K);
    451     }
    452
    453     @Test
    454     void testFromVertices_verticesRepeated() {
    455         // arrange
    456         final Point2S p1 = Point2S.PLUS_I;
    457         final Point2S p2 = Point2S.PLUS_J;
    458         final Point2S p3 = Point2S.PLUS_K;
    459
    460         // act
    461         final ConvexArea2S area = ConvexArea2S.fromVertices(Arrays.asList(
    462                 p1, Point2S.of(1e-17, Angle.PI_OVER_TWO), p2, p3, p3, p1), true, TEST_PRECISION);
    463
    464         // assert
    465         Assertions.assertEquals(Angle.PI_OVER_TWO, area.getSize(), TEST_EPS);
    466
    467         final Point2S expectedCentroid = triangleCentroid(Point2S.PLUS_I, Point2S.PLUS_J, Point2S.PLUS_K);
    468         SphericalTestUtils.assertPointsEq(expectedCentroid, area.getCentroid(), TEST_EPS);
    469
    470         final List<Point2S> vertices = area.getBoundaryPath().getVertices();
    471         Assertions.assertEquals(4, vertices.size());
    472         SphericalTestUtils.assertPointsEq(Point2S.PLUS_K, vertices.get(0), TEST_EPS);
    473         SphericalTestUtils.assertPointsEq(Point2S.PLUS_I, vertices.get(1), TEST_EPS);
    474         SphericalTestUtils.assertPointsEq(Point2S.PLUS_J, vertices.get(2), TEST_EPS);
    475         SphericalTestUtils.assertPointsEq(Point2S.PLUS_K, vertices.get(3), TEST_EPS);
    476     }
    477
    478     @Test
    479     void testFromVertices_invalidArguments() {
    480         // act/assert
    481         Assertions.assertThrows(IllegalStateException.class, () -> ConvexArea2S.fromVertices(Collections.singletonList(Point2S.PLUS_I), TEST_PRECISION));
    482         Assertions.assertThrows(IllegalStateException.class, () -> ConvexArea2S.fromVertices(Arrays.asList(Point2S.PLUS_I, Point2S.of(1e-16, Angle.PI_OVER_TWO)), TEST_PRECISION));
    483     }
    484
    485     @Test
    486     void testFromVertexLoop() {
    487         // arrange
    488         final Point2S p1 = Point2S.PLUS_I;
    489         final Point2S p2 = Point2S.PLUS_J;
    490         final Point2S p3 = Point2S.PLUS_K;
    491
    492         // act
    493         final ConvexArea2S area = ConvexArea2S.fromVertexLoop(Arrays.asList(p1, p2, p3), TEST_PRECISION);
    494
    495         // assert
    496         Assertions.assertFalse(area.isFull());
    497         Assertions.assertFalse(area.isEmpty());
    498         Assertions.assertEquals(1.5 * Math.PI, area.getBoundarySize(), TEST_EPS);
    499         Assertions.assertEquals(Angle.PI_OVER_TWO, area.getSize(), TEST_EPS);
    500
    501         final Point2S expectedCentroid = triangleCentroid(Point2S.PLUS_I, Point2S.PLUS_J, Point2S.PLUS_K);
    502         SphericalTestUtils.assertPointsEq(expectedCentroid, area.getCentroid(), TEST_EPS);
    503
    504         checkCentroidConsistency(area);
    505
    506         final List<GreatArc> arcs = sortArcs(area.getBoundaries());
    507         Assertions.assertEquals(3, arcs.size());
    508         checkArc(arcs.get(0), Point2S.PLUS_K, Point2S.PLUS_I);
    509         checkArc(arcs.get(1), Point2S.PLUS_I, Point2S.PLUS_J);
    510         checkArc(arcs.get(2), Point2S.PLUS_J, Point2S.PLUS_K);
    511
    512         SphericalTestUtils.checkClassify(area, RegionLocation.INSIDE,
    513                 Point2S.of(0.25 * Math.PI, 0.25 * Math.PI));
    514
    515         SphericalTestUtils.checkClassify(area, RegionLocation.BOUNDARY,
    516                 Point2S.PLUS_I, Point2S.PLUS_J, Point2S.PLUS_K,
    517                 Point2S.of(0, 0.25 * Math.PI), Point2S.of(Angle.PI_OVER_TWO, 0.304 * Math.PI),
    518                 Point2S.of(0.25 * Math.PI, Angle.PI_OVER_TWO));
    519
    520         SphericalTestUtils.checkClassify(area, RegionLocation.OUTSIDE,
    521                 Point2S.MINUS_I, Point2S.MINUS_J, Point2S.MINUS_K);
    522     }
    523
    524     @Test
    525     void testFromVertexLoop_empty() {
    526         // act
    527         final ConvexArea2S area = ConvexArea2S.fromVertexLoop(Collections.emptyList(), TEST_PRECISION);
    528
    529         // assert
    530         Assertions.assertSame(ConvexArea2S.full(), area);
    531     }
    532
    533     @Test
    534     void testGetCentroid_diminishingLunes() {
    535         // arrange
    536         final double eps = 1e-14;
    537         final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(eps);
    538
    539         final double centerAz = 1;
    540         final double centerPolar = 0.5 * Math.PI;
    541         final Point2S center = Point2S.of(centerAz, centerPolar);
    542         final Point2S pole = Point2S.PLUS_K;
    543
    544         final double startOffset = Angle.PI_OVER_TWO;
    545         final double minOffset = 1e-14;
    546
    547         ConvexArea2S area;
    548         Point2S p1;
    549         Point2S p2;
    550         Point2S centroid;
    551         for (double offset = startOffset; offset > minOffset; offset *= 0.5) {
    552             p1 = Point2S.of(centerAz - offset, centerPolar);
    553             p2 = Point2S.of(centerAz + offset, centerPolar);
    554
    555             area = ConvexArea2S.fromBounds(
    556                     GreatCircles.fromPoints(pole, p1, precision),
    557                     GreatCircles.fromPoints(p2, pole, precision));
    558
    559             // act
    560             centroid = area.getCentroid();
    561
    562             // assert
    563             Assertions.assertTrue(area.contains(centroid));
    564             SphericalTestUtils.assertPointsEq(center, centroid, TEST_EPS);
    565         }
    566     }
    567
    568     @Test
    569     void testGetCentroid_diminishingSquares() {
    570         // arrange
    571         final double eps = 1e-14;
    572         final Precision.DoubleEquivalence precision = Precision.doubleEquivalenceOfEpsilon(eps);
    573
    574         final double centerAz = 1;
    575         final double centerPolar = 0.5 * Math.PI;
    576         final Point2S center = Point2S.of(centerAz, centerPolar);
    577
    578         final double minOffset = 1e-14;
    579
    580         ConvexArea2S area;
    581         Point2S p1;
    582         Point2S p2;
    583         Point2S p3;
    584         Point2S p4;
    585         Point2S centroid;
    586         for (double offset = 0.5; offset > minOffset; offset *= 0.5) {
    587             p1 = Point2S.of(centerAz, centerPolar - offset);
    588             p2 = Point2S.of(centerAz - offset, centerPolar);
    589             p3 = Point2S.of(centerAz, centerPolar + offset);
    590             p4 = Point2S.of(centerAz + offset, centerPolar);
    591
    592             area = ConvexArea2S.fromVertexLoop(Arrays.asList(p1, p2, p3, p4), precision);
    593
    594             // act
    595             centroid = area.getCentroid();
    596
    597             // assert
    598             Assertions.assertTrue(area.contains(centroid));
    599             SphericalTestUtils.assertPointsEq(center, centroid, TEST_EPS);
    600         }
    601     }
    602
    603     @Test
    604     void testBoundaryStream() {
    605         // arrange
    606         final GreatCircle circle = GreatCircles.fromPole(Vector3D.Unit.PLUS_X, TEST_PRECISION);
    607         final ConvexArea2S area = ConvexArea2S.fromBounds(circle);
    608
    609         // act
    610         final List<GreatArc> arcs = area.boundaryStream().collect(Collectors.toList());
    611
    612         // assert
    613         Assertions.assertEquals(1, arcs.size());
    614         Assertions.assertSame(circle, arcs.get(0).getCircle());
    615     }
    616
    617     @Test
    618     void testBoundaryStream_noBoundaries() {
    619         // arrange
    620         final ConvexArea2S area = ConvexArea2S.full();
    621
    622         // act
    623         final List<GreatArc> arcs = area.boundaryStream().collect(Collectors.toList());
    624
    625         // assert
    626         Assertions.assertEquals(0, arcs.size());
    627     }
    628
    629     @Test
    630     void testGetInteriorAngles_noAngles() {
    631         // act/assert
    632         Assertions.assertEquals(0, ConvexArea2S.full().getInteriorAngles().length);
    633         Assertions.assertEquals(0, ConvexArea2S.fromBounds(GreatCircles.fromPole(Vector3D.Unit.PLUS_X, TEST_PRECISION))
    634                 .getInteriorAngles().length);
    635     }
    636
    637     @Test
    638     void testGetInteriorAngles() {
    639         // arrange
    640         final Point2S p1 = Point2S.PLUS_K;
    641         final Point2S p2 = Point2S.PLUS_I;
    642         final Point2S p4 = Point2S.PLUS_J;
    643
    644         final GreatCircle base = GreatCircles.fromPoints(p2, p4, TEST_PRECISION);
    645         final GreatCircle c1 = base.transform(Transform2S.createRotation(p2, -0.2));
    646         final GreatCircle c2 = base.transform(Transform2S.createRotation(p4, 0.1));
    647
    648         final Point2S p3 = c1.intersection(c2);
    649
    650         // act
    651         final ConvexArea2S area = ConvexArea2S.fromVertexLoop(Arrays.asList(p1, p2, p3, p4), TEST_PRECISION);
    652
    653         // assert
    654         final double[] angles = area.getInteriorAngles();
    655         Assertions.assertEquals(4, angles.length);
    656         Assertions.assertEquals(Angle.PI_OVER_TWO + 0.2, angles[0], TEST_EPS);
    657         Assertions.assertEquals(Math.PI - c1.angle(c2), angles[1], TEST_EPS);
    658         Assertions.assertEquals(Angle.PI_OVER_TWO + 0.1, angles[2], TEST_EPS);
    659         Assertions.assertEquals(Angle.PI_OVER_TWO, angles[3], TEST_EPS);
    660     }
    661
    662     @Test
    663     void testTransform() {
    664         // arrange
    665         final Transform2S t = Transform2S.createReflection(Point2S.PLUS_J);
    666         final ConvexArea2S input = ConvexArea2S.fromVertexLoop(
    667                 Arrays.asList(Point2S.PLUS_I, Point2S.PLUS_J, Point2S.PLUS_K), TEST_PRECISION);
    668
    669         // act
    670         final ConvexArea2S area = input.transform(t);
    671
    672         // assert
    673         Assertions.assertFalse(area.isFull());
    674         Assertions.assertFalse(area.isEmpty());
    675         Assertions.assertEquals(1.5 * Math.PI, area.getBoundarySize(), TEST_EPS);
    676         Assertions.assertEquals(Angle.PI_OVER_TWO, area.getSize(), TEST_EPS);
    677
    678         final Point2S expectedCentroid = triangleCentroid(Point2S.MINUS_J, Point2S.PLUS_I, Point2S.PLUS_K);
    679         SphericalTestUtils.assertPointsEq(expectedCentroid, area.getCentroid(), TEST_EPS);
    680
    681         checkCentroidConsistency(area);
    682
    683         final List<GreatArc> arcs = sortArcs(area.getBoundaries());
    684         Assertions.assertEquals(3, arcs.size());
    685         checkArc(arcs.get(0), Point2S.PLUS_K, Point2S.MINUS_J);
    686         checkArc(arcs.get(1), Point2S.PLUS_I, Point2S.PLUS_K);
    687         checkArc(arcs.get(2), Point2S.MINUS_J, Point2S.PLUS_I);
    688
    689         SphericalTestUtils.checkClassify(area, RegionLocation.INSIDE,
    690                 Point2S.of(-0.25 * Math.PI, 0.25 * Math.PI));
    691
    692         SphericalTestUtils.checkClassify(area, RegionLocation.BOUNDARY,
    693                 Point2S.PLUS_I, Point2S.MINUS_J, Point2S.PLUS_K,
    694                 Point2S.of(0, 0.25 * Math.PI), Point2S.of(-Angle.PI_OVER_TWO, 0.304 * Math.PI),
    695                 Point2S.of(-0.25 * Math.PI, Angle.PI_OVER_TWO));
    696
    697         SphericalTestUtils.checkClassify(area, RegionLocation.OUTSIDE,
    698                 Point2S.PLUS_J, Point2S.MINUS_I, Point2S.MINUS_K);
    699     }
    700
    701     @Test
    702     void testTrim() {
    703         // arrange
    704         final GreatCircle c1 = GreatCircles.fromPole(Vector3D.Unit.MINUS_X, TEST_PRECISION);
    705         final GreatCircle c2 = GreatCircles.fromPole(Vector3D.of(1, 1, 0), TEST_PRECISION);
    706
    707         final GreatCircle slanted = GreatCircles.fromPole(Vector3D.of(-1, 0, 1), TEST_PRECISION);
    708
    709         final ConvexArea2S area = ConvexArea2S.fromBounds(c1, c2);
    710
    711         // act/assert
    712         checkArc(area.trim(GreatCircles.arcFromPoints(Point2S.of(0.1, Angle.PI_OVER_TWO), Point2S.MINUS_I, TEST_PRECISION)),
    713                 Point2S.PLUS_J, Point2S.of(0.75 * Math.PI, Angle.PI_OVER_TWO));
    714
    715         checkArc(area.trim(GreatCircles.arcFromPoints(Point2S.MINUS_I, Point2S.of(0.2, Angle.PI_OVER_TWO), TEST_PRECISION)),
    716                 Point2S.of(0.75 * Math.PI, Angle.PI_OVER_TWO), Point2S.PLUS_J);
    717
    718         checkArc(area.trim(GreatCircles.arcFromPoints(Point2S.of(0.6 * Math.PI, 0.1), Point2S.of(0.7 * Math.PI, 0.8), TEST_PRECISION)),
    719                 Point2S.of(0.6 * Math.PI, 0.1), Point2S.of(0.7 * Math.PI, 0.8));
    720
    721         Assertions.assertNull(area.trim(GreatCircles.arcFromPoints(Point2S.MINUS_I, Point2S.MINUS_J, TEST_PRECISION)));
    722
    723         checkArc(area.trim(slanted.span()), c1.intersection(slanted), slanted.intersection(c2));
    724     }
    725
    726     @Test
    727     void testSplit_both() {
    728         // arrange
    729         final GreatCircle c1 = GreatCircles.fromPole(Vector3D.Unit.MINUS_X, TEST_PRECISION);
    730         final GreatCircle c2 = GreatCircles.fromPole(Vector3D.of(1, 1, 0), TEST_PRECISION);
    731
    732         final ConvexArea2S area = ConvexArea2S.fromBounds(c1, c2);
    733
    734         final GreatCircle splitter = GreatCircles.fromPole(Vector3D.of(-1, 0, 1), TEST_PRECISION);
    735
    736         // act
    737         final Split<ConvexArea2S> split = area.split(splitter);
    738
    739         // assert
    740         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
    741
    742         final Point2S p1 = c1.intersection(splitter);
    743         final Point2S p2 = splitter.intersection(c2);
    744
    745         final ConvexArea2S minus = split.getMinus();
    746         assertPath(minus.getBoundaryPath(), Point2S.PLUS_K, p1, p2, Point2S.PLUS_K);
    747
    748         final ConvexArea2S plus = split.getPlus();
    749         assertPath(plus.getBoundaryPath(), p1, Point2S.MINUS_K, p2, p1);
    750
    751         Assertions.assertEquals(area.getSize(), minus.getSize() + plus.getSize(), TEST_EPS);
    752     }
    753
    754     @Test
    755     void testSplit_minus() {
    756         // arrange
    757         final ConvexArea2S area = ConvexArea2S.fromVertexLoop(Arrays.asList(
    758                     Point2S.PLUS_I, Point2S.PLUS_K, Point2S.MINUS_J
    759                 ), TEST_PRECISION);
    760
    761         final GreatCircle splitter = GreatCircles.fromPole(Vector3D.of(0, -1, 1), TEST_PRECISION);
    762
    763         // act
    764         final Split<ConvexArea2S> split = area.split(splitter);
    765
    766         // assert
    767         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
    768
    769         Assertions.assertSame(area, split.getMinus());
    770         Assertions.assertNull(split.getPlus());
    771     }
    772
    773     @Test
    774     void testSplit_plus() {
    775         // arrange
    776         final ConvexArea2S area = ConvexArea2S.fromVertexLoop(Arrays.asList(
    777                     Point2S.PLUS_I, Point2S.PLUS_K, Point2S.MINUS_J
    778                 ), TEST_PRECISION);
    779
    780         final GreatCircle splitter = GreatCircles.fromPole(Vector3D.of(0, 1, -1), TEST_PRECISION);
    781
    782         // act
    783         final Split<ConvexArea2S> split = area.split(splitter);
    784
    785         // assert
    786         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
    787
    788         Assertions.assertNull(split.getMinus());
    789         Assertions.assertSame(area, split.getPlus());
    790     }
    791
    792     @Test
    793     void testToList_full() {
    794         // arrange
    795         final ConvexArea2S area = ConvexArea2S.full();
    796
    797         // act
    798         final BoundaryList2S list = area.toList();
    799
    800         // assert
    801         Assertions.assertEquals(0, list.count());
    802     }
    803
    804     @Test
    805     void testToList() {
    806         // arrange
    807         final ConvexArea2S area = ConvexArea2S.fromVertexLoop(Arrays.asList(
    808                     Point2S.of(0.1, 0.1), Point2S.of(-0.4, 1),
    809                     Point2S.of(0.15, 1.5), Point2S.of(0.3, 1.2),
    810                     Point2S.of(0.1, 0.1)
    811                 ), TEST_PRECISION);
    812
    813         // act
    814         final BoundaryList2S list = area.toList();
    815
    816         // assert
    817         Assertions.assertEquals(4, list.count());
    818         Assertions.assertEquals(area.getSize(), list.toTree().getSize(), TEST_EPS);
    819     }
    820
    821     @Test
    822     void testToTree_full() {
    823         // arrange
    824         final ConvexArea2S area = ConvexArea2S.full();
    825
    826         // act
    827         final RegionBSPTree2S tree = area.toTree();
    828
    829         // assert
    830         Assertions.assertTrue(tree.isFull());
    831         Assertions.assertFalse(tree.isEmpty());
    832     }
    833
    834     @Test
    835     void testToTree() {
    836         // arrange
    837         final ConvexArea2S area = ConvexArea2S.fromVertexLoop(Arrays.asList(
    838                     Point2S.of(0.1, 0.1), Point2S.of(-0.4, 1),
    839                     Point2S.of(0.15, 1.5), Point2S.of(0.3, 1.2),
    840                     Point2S.of(0.1, 0.1)
    841                 ), TEST_PRECISION);
    842
    843         // act
    844         final RegionBSPTree2S tree = area.toTree();
    845
    846         // assert
    847         Assertions.assertFalse(tree.isFull());
    848         Assertions.assertFalse(tree.isEmpty());
    849
    850         Assertions.assertEquals(area.getSize(), tree.getSize(), TEST_EPS);
    851         SphericalTestUtils.assertPointsEq(area.getCentroid(), tree.getCentroid(), TEST_EPS);
    852     }
    853
    854     private static List<GreatArc> sortArcs(final List<GreatArc> arcs) {
    855         final List<GreatArc> result = new ArrayList<>(arcs);
    856
    857         result.sort((a, b) ->
    858                 Point2S.POLAR_AZIMUTH_ASCENDING_ORDER.compare(a.getStartPoint(), b.getStartPoint()));
    859
    860         return result;
    861     }
    862
    863     private static Point2S triangleCentroid(final Point2S p1, final Point2S p2, final Point2S p3) {
    864         // compute the centroid as the sum of the cross product of each point pair weighted by
    865         // the angle between the points
    866         final Vector3D v1 = p1.getVector();
    867         final Vector3D v2 = p2.getVector();
    868         final Vector3D v3 = p3.getVector();
    869
    870         Vector3D sum = Vector3D.ZERO;
    871         sum = sum.add(v1.cross(v2).withNorm(v1.angle(v2)));
    872         sum = sum.add(v2.cross(v3).withNorm(v2.angle(v3)));
    873         sum = sum.add(v3.cross(v1).withNorm(v3.angle(v1)));
    874
    875         return Point2S.from(sum);
    876     }
    877
    878     private static void checkArc(final GreatArc arc, final Point2S start, final Point2S end) {
    879         SphericalTestUtils.assertPointsEq(start, arc.getStartPoint(), TEST_EPS);
    880         SphericalTestUtils.assertPointsEq(end, arc.getEndPoint(), TEST_EPS);
    881     }
    882
    883     private static void assertPath(final GreatArcPath path, final Point2S... expectedVertices) {
    884         final List<Point2S> vertices = path.getVertices();
    885
    886         Assertions.assertEquals(expectedVertices.length, vertices.size());
    887         for (int i = 0; i < expectedVertices.length; ++i) {
    888
    889             if (!expectedVertices[i].eq(vertices.get(i), TEST_PRECISION)) {
    890                 final String msg = "Unexpected point in path at index " + i + ". Expected " +
    891                         Arrays.toString(expectedVertices) + " but received " + vertices;
    892                 Assertions.fail(msg);
    893             }
    894         }
    895     }
    896
    897     private static void checkCentroidConsistency(final ConvexArea2S area) {
    898         final Point2S centroid = area.getCentroid();
    899         final double size = area.getSize();
    900
    901         SphericalTestUtils.checkClassify(area, RegionLocation.INSIDE, centroid);
    902
    903         final GreatCircle circle = GreatCircles.fromPole(centroid.getVector(), TEST_PRECISION);
    904         for (double az = 0; az <= Angle.TWO_PI; az += 0.2) {
    905             final Point2S pt = circle.toSpace(Point1S.of(az));
    906             final GreatCircle splitter = GreatCircles.fromPoints(centroid, pt, TEST_PRECISION);
    907
    908             final Split<ConvexArea2S> split = area.split(splitter);
    909
    910             Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
    911
    912             final ConvexArea2S minus = split.getMinus();
    913             final double minusSize = minus.getSize();
    914
    915             final ConvexArea2S plus = split.getPlus();
    916             final double plusSize = plus.getSize();
    917
    918             final Vector3D minusWeightedCentroid = minus.getWeightedCentroidVector();
    919             final Vector3D plusWeightedCentroid = plus.getWeightedCentroidVector();
    920
    921             final Point2S computedCentroid = Point2S.from(minusWeightedCentroid.add(plusWeightedCentroid));
    922
    923             Assertions.assertEquals(size, minusSize + plusSize, TEST_EPS);
    924             SphericalTestUtils.assertPointsEq(centroid, computedCentroid, TEST_EPS);
    925         }
    926     }
    927 }