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