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  import java.util.stream.Stream;
    25
    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.euclidean.threed.Vector3D;
    30  import org.apache.commons.geometry.spherical.SphericalTestUtils;
    31  import org.apache.commons.geometry.spherical.oned.Point1S;
    32  import org.apache.commons.geometry.spherical.twod.RegionBSPTree2S.RegionNode2S;
    33  import org.apache.commons.numbers.angle.Angle;
    34  import org.apache.commons.numbers.core.Precision;
    35  import org.junit.jupiter.api.Assertions;
    36  import org.junit.jupiter.api.Test;
    37
    38  class RegionBSPTree2STest {
    39
    40      private static final double TEST_EPS = 1e-10;
    41
    42      // alternative epsilon value for checking the centroids of complex
    43      // or very small regions
    44      private static final double CENTROID_EPS = 1e-5;
    45
    46      private static final Precision.DoubleEquivalence TEST_PRECISION =
    47              Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
    48
    49      private static final GreatCircle EQUATOR = GreatCircles.fromPoleAndU(
    50              Vector3D.Unit.PLUS_Z, Vector3D.Unit.PLUS_X, TEST_PRECISION);
    51
    52      private static final GreatCircle X_MERIDIAN = GreatCircles.fromPoleAndU(
    53              Vector3D.Unit.PLUS_Y, Vector3D.Unit.PLUS_X, TEST_PRECISION);
    54
    55      private static final GreatCircle Y_MERIDIAN = GreatCircles.fromPoleAndU(
    56              Vector3D.Unit.PLUS_X, Vector3D.Unit.PLUS_Y, TEST_PRECISION);
    57
    58      @Test
    59      void testCtor_booleanArg_true() {
    60          // act
    61          final RegionBSPTree2S tree = new RegionBSPTree2S(true);
    62
    63          // assert
    64          Assertions.assertTrue(tree.isFull());
    65          Assertions.assertFalse(tree.isEmpty());
    66          Assertions.assertEquals(1, tree.count());
    67      }
    68
    69      @Test
    70      void testCtor_booleanArg_false() {
    71          // act
    72          final RegionBSPTree2S tree = new RegionBSPTree2S(false);
    73
    74          // assert
    75          Assertions.assertFalse(tree.isFull());
    76          Assertions.assertTrue(tree.isEmpty());
    77          Assertions.assertEquals(1, tree.count());
    78      }
    79
    80      @Test
    81      void testCtor_default() {
    82          // act
    83          final RegionBSPTree2S tree = new RegionBSPTree2S();
    84
    85          // assert
    86          Assertions.assertFalse(tree.isFull());
    87          Assertions.assertTrue(tree.isEmpty());
    88          Assertions.assertEquals(1, tree.count());
    89      }
    90
    91      @Test
    92      void testFull_factoryMethod() {
    93          // act
    94          final RegionBSPTree2S tree = RegionBSPTree2S.full();
    95
    96          // assert
    97          Assertions.assertTrue(tree.isFull());
    98          Assertions.assertFalse(tree.isEmpty());
    99          Assertions.assertEquals(1, tree.count());
    100     }
    101
    102     @Test
    103     void testEmpty_factoryMethod() {
    104         // act
    105         final RegionBSPTree2S tree = RegionBSPTree2S.empty();
    106
    107         // assert
    108         Assertions.assertFalse(tree.isFull());
    109         Assertions.assertTrue(tree.isEmpty());
    110         Assertions.assertEquals(1, tree.count());
    111     }
    112
    113     @Test
    114     void testFrom_boundaries_noBoundaries() {
    115         // act/assert
    116         Assertions.assertTrue(RegionBSPTree2S.from(Collections.emptyList()).isEmpty());
    117         Assertions.assertTrue(RegionBSPTree2S.from(Collections.emptyList(), true).isFull());
    118         Assertions.assertTrue(RegionBSPTree2S.from(Collections.emptyList(), false).isEmpty());
    119     }
    120
    121     @Test
    122     void testFrom_boundaries() {
    123         // act
    124         final RegionBSPTree2S tree = RegionBSPTree2S.from(Arrays.asList(
    125                     EQUATOR.arc(Point2S.PLUS_I, Point2S.PLUS_J),
    126                     X_MERIDIAN.arc(Point2S.PLUS_K, Point2S.PLUS_I),
    127                     Y_MERIDIAN.arc(Point2S.PLUS_J, Point2S.PLUS_K)
    128                 ));
    129
    130         // assert
    131         Assertions.assertFalse(tree.isFull());
    132         Assertions.assertFalse(tree.isEmpty());
    133
    134         Assertions.assertEquals(RegionLocation.OUTSIDE, tree.getRoot().getLocation());
    135
    136         SphericalTestUtils.checkClassify(tree, RegionLocation.INSIDE, Point2S.of(1, 0.5));
    137         SphericalTestUtils.checkClassify(tree, RegionLocation.OUTSIDE,
    138                 Point2S.of(-1, 0.5), Point2S.of(Math.PI, 0.5 * Math.PI));
    139     }
    140
    141     @Test
    142     void testFrom_boundaries_fullIsTrue() {
    143         // act
    144         final RegionBSPTree2S tree = RegionBSPTree2S.from(Arrays.asList(
    145                     EQUATOR.arc(Point2S.PLUS_I, Point2S.PLUS_J),
    146                     X_MERIDIAN.arc(Point2S.PLUS_K, Point2S.PLUS_I),
    147                     Y_MERIDIAN.arc(Point2S.PLUS_J, Point2S.PLUS_K)
    148                 ), true);
    149
    150         // assert
    151         Assertions.assertFalse(tree.isFull());
    152         Assertions.assertFalse(tree.isEmpty());
    153
    154         Assertions.assertEquals(RegionLocation.INSIDE, tree.getRoot().getLocation());
    155
    156         SphericalTestUtils.checkClassify(tree, RegionLocation.INSIDE, Point2S.of(1, 0.5));
    157         SphericalTestUtils.checkClassify(tree, RegionLocation.OUTSIDE,
    158                 Point2S.of(-1, 0.5), Point2S.of(Math.PI, 0.5 * Math.PI));
    159     }
    160
    161     @Test
    162     void testCopy() {
    163         // arrange
    164         final RegionBSPTree2S tree = new RegionBSPTree2S(true);
    165         tree.getRoot().cut(EQUATOR);
    166
    167         // act
    168         final RegionBSPTree2S copy = tree.copy();
    169
    170         // assert
    171         Assertions.assertNotSame(tree, copy);
    172         Assertions.assertEquals(3, copy.count());
    173     }
    174
    175     @Test
    176     void testBoundaries() {
    177         // arrange
    178         final RegionBSPTree2S tree = RegionBSPTree2S.empty();
    179         insertPositiveQuadrant(tree);
    180
    181         // act
    182         final List<GreatArc> arcs = new ArrayList<>();
    183         tree.boundaries().forEach(arcs::add);
    184
    185         // assert
    186         Assertions.assertEquals(3, arcs.size());
    187     }
    188
    189     @Test
    190     void testGetBoundaries() {
    191         // arrange
    192         final RegionBSPTree2S tree = RegionBSPTree2S.empty();
    193         insertPositiveQuadrant(tree);
    194
    195         // act
    196         final List<GreatArc> arcs = tree.getBoundaries();
    197
    198         // assert
    199         Assertions.assertEquals(3, arcs.size());
    200     }
    201
    202     @Test
    203     void testBoundaryStream() {
    204         // arrange
    205         final RegionBSPTree2S tree = RegionBSPTree2S.empty();
    206         insertPositiveQuadrant(tree);
    207
    208         // act
    209         final List<GreatArc> arcs = tree.boundaryStream().collect(Collectors.toList());
    210
    211         // assert
    212         Assertions.assertEquals(3, arcs.size());
    213     }
    214
    215     @Test
    216     void testBoundaryStream_noBoundaries() {
    217         // arrange
    218         final RegionBSPTree2S tree = RegionBSPTree2S.empty();
    219
    220         // act
    221         final List<GreatArc> arcs = tree.boundaryStream().collect(Collectors.toList());
    222
    223         // assert
    224         Assertions.assertEquals(0, arcs.size());
    225     }
    226
    227     @Test
    228     void testToList_fullAndEmpty() {
    229         // act/assert
    230         Assertions.assertEquals(0, RegionBSPTree2S.full().toList().count());
    231         Assertions.assertEquals(0, RegionBSPTree2S.empty().toList().count());
    232     }
    233
    234     @Test
    235     void testToList() {
    236         // arrange
    237         final RegionBSPTree2S tree = RegionBSPTree2S.empty();
    238         insertPositiveQuadrant(tree);
    239
    240         // act
    241         final BoundaryList2S list = tree.toList();
    242
    243         // assert
    244         Assertions.assertEquals(3, list.count());
    245         Assertions.assertEquals(0.5 * Math.PI, list.toTree().getSize(), TEST_EPS);
    246     }
    247
    248     @Test
    249     void testToTree_returnsSameInstance() {
    250         // arrange
    251         final RegionBSPTree2S tree = RegionBSPTree2S.empty();
    252         insertPositiveQuadrant(tree);
    253
    254         // act/assert
    255         Assertions.assertSame(tree, tree.toTree());
    256     }
    257
    258     @Test
    259     void testGetBoundaryPaths_cachesResult() {
    260         // arrange
    261         final RegionBSPTree2S tree = RegionBSPTree2S.empty();
    262         insertPositiveQuadrant(tree);
    263
    264         // act
    265         final List<GreatArcPath> a = tree.getBoundaryPaths();
    266         final List<GreatArcPath> b = tree.getBoundaryPaths();
    267
    268         // assert
    269         Assertions.assertSame(a, b);
    270     }
    271
    272     @Test
    273     void testGetBoundaryPaths_recomputesResultOnChange() {
    274         // arrange
    275         final RegionBSPTree2S tree = RegionBSPTree2S.empty();
    276         tree.insert(EQUATOR.span());
    277
    278         // act
    279         final List<GreatArcPath> a = tree.getBoundaryPaths();
    280         tree.insert(X_MERIDIAN.span());
    281         final List<GreatArcPath> b = tree.getBoundaryPaths();
    282
    283         // assert
    284         Assertions.assertNotSame(a, b);
    285     }
    286
    287     @Test
    288     void testGetBoundaryPaths_isUnmodifiable() {
    289         // arrange
    290         final RegionBSPTree2S tree = RegionBSPTree2S.empty();
    291         tree.insert(EQUATOR.span());
    292
    293         // act/assert
    294         Assertions.assertThrows(UnsupportedOperationException.class, () -> tree.getBoundaryPaths().add(GreatArcPath.empty()));
    295     }
    296
    297     @Test
    298     void testToConvex_full() {
    299         // arrange
    300         final RegionBSPTree2S tree = RegionBSPTree2S.full();
    301
    302         // act
    303         final List<ConvexArea2S> result = tree.toConvex();
    304
    305         // assert
    306         Assertions.assertEquals(1, result.size());
    307         Assertions.assertTrue(result.get(0).isFull());
    308     }
    309
    310     @Test
    311     void testToConvex_empty() {
    312         // arrange
    313         final RegionBSPTree2S tree = RegionBSPTree2S.empty();
    314
    315         // act
    316         final List<ConvexArea2S> result = tree.toConvex();
    317
    318         // assert
    319         Assertions.assertEquals(0, result.size());
    320     }
    321
    322     @Test
    323     void testToConvex_doubleLune() {
    324         // arrange
    325         final RegionBSPTree2S tree = GreatArcPath.builder(TEST_PRECISION)
    326                 .append(EQUATOR.arc(0,  Math.PI))
    327                 .append(X_MERIDIAN.arc(Math.PI, 0))
    328                 .append(EQUATOR.reverse().arc(0, Math.PI))
    329                 .append(X_MERIDIAN.reverse().arc(Math.PI, 0))
    330                 .build()
    331                 .toTree();
    332
    333         // act
    334         final List<ConvexArea2S> result = tree.toConvex();
    335
    336         // assert
    337         Assertions.assertEquals(2, result.size());
    338
    339         final double size = result.stream().mapToDouble(ConvexArea2S::getSize).sum();
    340         Assertions.assertEquals(Angle.TWO_PI, size, TEST_EPS);
    341     }
    342
    343     @Test
    344     void testToConvex_doubleLune_complement() {
    345         // arrange
    346         final RegionBSPTree2S tree = GreatArcPath.builder(TEST_PRECISION)
    347                 .append(EQUATOR.arc(0,  Math.PI))
    348                 .append(X_MERIDIAN.arc(Math.PI, 0))
    349                 .append(EQUATOR.reverse().arc(0, Math.PI))
    350                 .append(X_MERIDIAN.reverse().arc(Math.PI, 0))
    351                 .build()
    352                 .toTree();
    353
    354         // act
    355         final List<ConvexArea2S> result = tree.toConvex();
    356
    357         // assert
    358         Assertions.assertEquals(2, result.size());
    359
    360         final double size = result.stream().mapToDouble(ConvexArea2S::getSize).sum();
    361         Assertions.assertEquals(Angle.TWO_PI, size, TEST_EPS);
    362     }
    363
    364     @Test
    365     void testProject() {
    366         // arrange
    367         final RegionBSPTree2S tree = RegionBSPTree2S.empty();
    368         tree.insert(EQUATOR.arc(0, Math.PI));
    369         tree.insert(X_MERIDIAN.arc(Math.PI, 0));
    370
    371         // act/assert
    372         SphericalTestUtils.assertPointsEq(Point2S.of(Angle.PI_OVER_TWO, Angle.PI_OVER_TWO),
    373                 tree.project(Point2S.of(Angle.PI_OVER_TWO, Angle.PI_OVER_TWO + 0.2)), TEST_EPS);
    374         SphericalTestUtils.assertPointsEq(Point2S.PLUS_K,
    375                 tree.project(Point2S.of(-Angle.PI_OVER_TWO, 0.2)), TEST_EPS);
    376
    377         SphericalTestUtils.assertPointsEq(Point2S.PLUS_I,
    378                 tree.project(Point2S.of(-0.5, Angle.PI_OVER_TWO)), TEST_EPS);
    379         SphericalTestUtils.assertPointsEq(Point2S.MINUS_I,
    380                 tree.project(Point2S.of(Math.PI + 0.5, Angle.PI_OVER_TWO)), TEST_EPS);
    381
    382         final Point2S centroid = tree.getCentroid();
    383         SphericalTestUtils.assertPointsEq(Point2S.PLUS_K,
    384                 tree.project(centroid.slerp(Point2S.PLUS_K, 1e-10)), TEST_EPS);
    385         SphericalTestUtils.assertPointsEq(Point2S.PLUS_J,
    386                 tree.project(centroid.slerp(Point2S.PLUS_J, 1e-10)), TEST_EPS);
    387     }
    388
    389     @Test
    390     void testProject_noBoundaries() {
    391         // act/assert
    392         Assertions.assertNull(RegionBSPTree2S.empty().project(Point2S.PLUS_I));
    393         Assertions.assertNull(RegionBSPTree2S.full().project(Point2S.PLUS_I));
    394     }
    395
    396     @Test
    397     void testGeometricProperties_full() {
    398         // arrange
    399         final RegionBSPTree2S tree = RegionBSPTree2S.full();
    400
    401         // act/assert
    402         Assertions.assertEquals(4 * Math.PI, tree.getSize(), TEST_EPS);
    403         Assertions.assertNull(tree.getCentroid());
    404
    405         Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
    406
    407         Assertions.assertEquals(0, tree.getBoundaries().size());
    408         Assertions.assertEquals(0, tree.getBoundaryPaths().size());
    409     }
    410
    411     @Test
    412     void testGeometricProperties_empty() {
    413         // arrange
    414         final RegionBSPTree2S tree = RegionBSPTree2S.empty();
    415
    416         // act/assert
    417         Assertions.assertEquals(0, tree.getSize(), TEST_EPS);
    418         Assertions.assertNull(tree.getCentroid());
    419
    420         Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
    421
    422         Assertions.assertEquals(0, tree.getBoundaries().size());
    423         Assertions.assertEquals(0, tree.getBoundaryPaths().size());
    424     }
    425
    426     @Test
    427     void testGeometricProperties_halfSpace() {
    428         // arrange
    429         final RegionBSPTree2S tree = RegionBSPTree2S.full();
    430         tree.getRoot().cut(EQUATOR);
    431
    432         // act/assert
    433         Assertions.assertEquals(Angle.TWO_PI, tree.getSize(), TEST_EPS);
    434         Assertions.assertEquals(Angle.TWO_PI, tree.getBoundarySize(), TEST_EPS);
    435         SphericalTestUtils.assertPointsEq(Point2S.PLUS_K, tree.getCentroid(), TEST_EPS);
    436
    437         checkCentroidConsistency(tree);
    438
    439         final List<GreatArc> arcs = tree.getBoundaries();
    440         Assertions.assertEquals(1, arcs.size());
    441
    442         final GreatArc arc = arcs.get(0);
    443         Assertions.assertSame(EQUATOR, arc.getCircle());
    444         Assertions.assertNull(arc.getStartPoint());
    445         Assertions.assertNull(arc.getEndPoint());
    446
    447         final List<GreatArcPath> paths = tree.getBoundaryPaths();
    448         Assertions.assertEquals(1, paths.size());
    449
    450         final GreatArcPath path = paths.get(0);
    451         Assertions.assertEquals(1, path.getArcs().size());
    452         Assertions.assertTrue(path.getArcs().get(0).isFull());
    453     }
    454
    455     @Test
    456     void testGeometricProperties_doubleLune() {
    457         // act
    458         final RegionBSPTree2S tree = GreatArcPath.builder(TEST_PRECISION)
    459                 .append(EQUATOR.arc(0,  Math.PI))
    460                 .append(X_MERIDIAN.arc(Math.PI, 0))
    461                 .append(EQUATOR.reverse().arc(0, Math.PI))
    462                 .append(X_MERIDIAN.reverse().arc(Math.PI, 0))
    463                 .build()
    464                 .toTree();
    465
    466         // assert
    467         Assertions.assertEquals(2 * Math.PI, tree.getSize(), TEST_EPS);
    468         Assertions.assertEquals(4 * Math.PI, tree.getBoundarySize(), TEST_EPS);
    469         Assertions.assertNull(tree.getCentroid());
    470
    471         final List<GreatArcPath> paths = tree.getBoundaryPaths();
    472         Assertions.assertEquals(2, paths.size());
    473
    474         assertPath(paths.get(0), Point2S.PLUS_I, Point2S.MINUS_I, Point2S.PLUS_I);
    475         assertPath(paths.get(1), Point2S.PLUS_I, Point2S.MINUS_I, Point2S.PLUS_I);
    476
    477         SphericalTestUtils.checkClassify(tree, RegionLocation.INSIDE,
    478                 Point2S.of(0.5 * Math.PI, 0.25 * Math.PI),
    479                 Point2S.of(1.5 * Math.PI, 0.75 * Math.PI));
    480
    481         SphericalTestUtils.checkClassify(tree, RegionLocation.OUTSIDE,
    482                 Point2S.of(0.5 * Math.PI, 0.75 * Math.PI),
    483                 Point2S.of(1.5 * Math.PI, 0.25 * Math.PI));
    484     }
    485
    486     @Test
    487     void testGeometricProperties_quadrant() {
    488         // act
    489         final RegionBSPTree2S tree = GreatArcPath.builder(TEST_PRECISION)
    490                 .appendVertices(Point2S.MINUS_K, Point2S.PLUS_I, Point2S.MINUS_J)
    491                 .close()
    492                 .toTree();
    493
    494         // assert
    495         Assertions.assertEquals(0.5 * Math.PI, tree.getSize(), TEST_EPS);
    496         Assertions.assertEquals(1.5 * Math.PI, tree.getBoundarySize(), TEST_EPS);
    497
    498         final Point2S center = Point2S.from(Point2S.MINUS_K.getVector()
    499                 .add(Point2S.PLUS_I.getVector())
    500                 .add(Point2S.MINUS_J.getVector()));
    501         SphericalTestUtils.assertPointsEq(center, tree.getCentroid(), TEST_EPS);
    502
    503         checkCentroidConsistency(tree);
    504
    505         final List<GreatArcPath> paths = tree.getBoundaryPaths();
    506         Assertions.assertEquals(1, paths.size());
    507
    508         assertPathLoop(paths.get(0), Point2S.PLUS_I, Point2S.MINUS_J,  Point2S.MINUS_K);
    509
    510         SphericalTestUtils.checkClassify(tree, RegionLocation.INSIDE,
    511                 Point2S.of(1.75 * Math.PI, 0.75 * Math.PI));
    512
    513         SphericalTestUtils.checkClassify(tree, RegionLocation.OUTSIDE,
    514                 Point2S.PLUS_J, Point2S.PLUS_K, Point2S.MINUS_I);
    515     }
    516
    517     @Test
    518     void testGeometricProperties_quadrant_complement() {
    519         // arrange
    520         final RegionBSPTree2S tree = GreatArcPath.builder(TEST_PRECISION)
    521                 .appendVertices(Point2S.MINUS_K, Point2S.PLUS_I, Point2S.MINUS_J)
    522                 .close()
    523                 .toTree();
    524
    525         // act
    526         tree.complement();
    527
    528         // assert
    529         Assertions.assertEquals(3.5 * Math.PI, tree.getSize(), TEST_EPS);
    530         Assertions.assertEquals(1.5 * Math.PI, tree.getBoundarySize(), TEST_EPS);
    531
    532         final Point2S center = Point2S.from(Point2S.MINUS_K.getVector()
    533                 .add(Point2S.PLUS_I.getVector())
    534                 .add(Point2S.MINUS_J.getVector()));
    535         SphericalTestUtils.assertPointsEq(center.antipodal(), tree.getCentroid(), TEST_EPS);
    536
    537         checkCentroidConsistency(tree);
    538
    539         final List<GreatArcPath> paths = tree.getBoundaryPaths();
    540         Assertions.assertEquals(1, paths.size());
    541
    542         assertPathLoop(paths.get(0), Point2S.PLUS_I, Point2S.MINUS_K, Point2S.MINUS_J);
    543
    544         SphericalTestUtils.checkClassify(tree, RegionLocation.OUTSIDE,
    545                 Point2S.of(1.75 * Math.PI, 0.75 * Math.PI));
    546
    547         SphericalTestUtils.checkClassify(tree, RegionLocation.INSIDE,
    548                 Point2S.PLUS_J, Point2S.PLUS_K, Point2S.MINUS_I);
    549     }
    550
    551     @Test
    552     void testGeometricProperties_polygonWithHole() {
    553         // arrange
    554         final Point2S center = Point2S.of(0.5, 2);
    555
    556         final double outerRadius = 1;
    557         final double innerRadius = 0.5;
    558
    559         final RegionBSPTree2S outer = buildDiamond(center, outerRadius);
    560         final RegionBSPTree2S inner = buildDiamond(center, innerRadius);
    561
    562         // rotate the inner diamond a quarter turn to become a square
    563         inner.transform(Transform2S.createRotation(center, 0.25 * Math.PI));
    564
    565         // act
    566         final RegionBSPTree2S tree = RegionBSPTree2S.empty();
    567         tree.difference(outer, inner);
    568
    569         // assert
    570         final double area = 4 * (rightTriangleArea(outerRadius, outerRadius) - rightTriangleArea(innerRadius, innerRadius));
    571         Assertions.assertEquals(area, tree.getSize(), TEST_EPS);
    572
    573         final double outerSideLength = sphericalHypot(outerRadius, outerRadius);
    574         final double innerSideLength = sphericalHypot(innerRadius, innerRadius);
    575         final double boundarySize = 4 * (outerSideLength + innerSideLength);
    576         Assertions.assertEquals(boundarySize, tree.getBoundarySize(), TEST_EPS);
    577
    578         SphericalTestUtils.assertPointsEq(center, tree.getCentroid(), TEST_EPS);
    579         checkCentroidConsistency(tree);
    580
    581         SphericalTestUtils.checkClassify(tree, RegionLocation.OUTSIDE, center);
    582     }
    583
    584     @Test
    585     void testGeometricProperties_polygonWithHole_small() {
    586         // arrange
    587         final Point2S center = Point2S.of(0.5, 2);
    588
    589         final double outerRadius = 1e-5;
    590         final double innerRadius = 1e-7;
    591
    592         final RegionBSPTree2S outer = buildDiamond(center, outerRadius);
    593         final RegionBSPTree2S inner = buildDiamond(center, innerRadius);
    594
    595         // rotate the inner diamond a quarter turn to become a square
    596         inner.transform(Transform2S.createRotation(center, 0.25 * Math.PI));
    597
    598         // act
    599         final RegionBSPTree2S tree = RegionBSPTree2S.empty();
    600         tree.difference(outer, inner);
    601
    602         // assert
    603
    604         // use Euclidean approximations of the area and boundary size since those will be more accurate
    605         // at these sizes
    606         final double area = (2 * outerRadius * outerRadius) - (2 * innerRadius * innerRadius);
    607         Assertions.assertEquals(area, tree.getSize(), TEST_EPS);
    608
    609         final double outerSideLength = Math.hypot(outerRadius, outerRadius);
    610         final double innerSideLength = Math.hypot(innerRadius, innerRadius);
    611         final double boundarySize = 4 * (outerSideLength + innerSideLength);
    612         Assertions.assertEquals(boundarySize, tree.getBoundarySize(), TEST_EPS);
    613
    614         SphericalTestUtils.assertPointsEq(center, tree.getCentroid(), TEST_EPS);
    615         checkCentroidConsistency(tree);
    616
    617         SphericalTestUtils.checkClassify(tree, RegionLocation.OUTSIDE, center);
    618     }
    619
    620     @Test
    621     void testGeometricProperties_polygonWithHole_complex() {
    622         // arrange
    623         final Point2S center = Point2S.of(0.5, 2);
    624
    625         final double outerRadius = 2;
    626         final double midRadius = 1;
    627         final double innerRadius = 0.5;
    628
    629         final RegionBSPTree2S outer = buildDiamond(center, outerRadius);
    630         final RegionBSPTree2S mid = buildDiamond(center, midRadius);
    631         final RegionBSPTree2S inner = buildDiamond(center, innerRadius);
    632
    633         // rotate the middle diamond a quarter turn to become a square
    634         mid.transform(Transform2S.createRotation(center, 0.25 * Math.PI));
    635
    636         // act
    637         final RegionBSPTree2S tree = RegionBSPTree2S.empty();
    638         tree.difference(outer, mid);
    639         tree.union(inner);
    640         tree.complement();
    641
    642         // assert
    643         // compute the area, adjusting the first computation for the fact that the triangles comprising the
    644         // outer diamond have lengths greater than pi/2
    645         final double nonComplementedArea = 4 * ((Math.PI - rightTriangleArea(outerRadius, outerRadius) -
    646                 rightTriangleArea(midRadius, midRadius) + rightTriangleArea(innerRadius, innerRadius)));
    647         final double area = (4 * Math.PI) - nonComplementedArea;
    648         Assertions.assertEquals(area, tree.getSize(), TEST_EPS);
    649
    650         final double outerSideLength = sphericalHypot(outerRadius, outerRadius);
    651         final double midSideLength = sphericalHypot(midRadius, midRadius);
    652         final double innerSideLength = sphericalHypot(innerRadius, innerRadius);
    653         final double boundarySize = 4 * (outerSideLength + midSideLength + innerSideLength);
    654         Assertions.assertEquals(boundarySize, tree.getBoundarySize(), TEST_EPS);
    655
    656         SphericalTestUtils.assertPointsEq(center.antipodal(), tree.getCentroid(), TEST_EPS);
    657         checkCentroidConsistency(tree);
    658
    659         SphericalTestUtils.checkClassify(tree, RegionLocation.OUTSIDE, center);
    660     }
    661
    662     @Test
    663     void testGeometricProperties_smallRightTriangle() {
    664         // arrange
    665         final double azOffset = 1e-5;
    666         final double polarOffset = 1e-6;
    667
    668         final double minAz = 0;
    669         final double maxAz = minAz + azOffset;
    670         final double maxPolar = Angle.PI_OVER_TWO;
    671         final double minPolar = maxPolar - polarOffset;
    672
    673         final Point2S p0 = Point2S.of(minAz, maxPolar);
    674         final Point2S p1 = Point2S.of(maxAz, maxPolar);
    675         final Point2S p2 = Point2S.of(maxAz, minPolar);
    676
    677         // act
    678         final RegionBSPTree2S tree = GreatArcPath.fromVertexLoop(Arrays.asList(p0, p1, p2), TEST_PRECISION)
    679                 .toTree();
    680
    681         // assert
    682
    683         // use Euclidean approximations of the area and boundary size since those will be more accurate
    684         // at these sizes
    685         final double expectedArea = 0.5 * azOffset * polarOffset;
    686         Assertions.assertEquals(expectedArea, tree.getSize(), TEST_EPS);
    687
    688         final double expectedBoundarySize = azOffset + polarOffset + Math.hypot(azOffset, polarOffset);
    689         Assertions.assertEquals(expectedBoundarySize, tree.getBoundarySize(), TEST_EPS);
    690
    691         Assertions.assertTrue(tree.contains(tree.getCentroid()));
    692         checkCentroidConsistency(tree);
    693
    694         SphericalTestUtils.checkClassify(tree, RegionLocation.INSIDE,
    695                 tree.getCentroid(),
    696                 Point2S.of(minAz + (0.75 * azOffset), minPolar + (0.75 * polarOffset)));
    697
    698         SphericalTestUtils.checkClassify(tree, RegionLocation.BOUNDARY,
    699                 p0, p1, p2, p0.slerp(p1, 0.5), p1.slerp(p2, 0.5), p2.slerp(p0, 0.5));
    700
    701         final double midAz = minAz + (0.5 * azOffset);
    702         final double pastMinAz = minAz - azOffset;
    703         final double pastMaxAz = maxAz + azOffset;
    704
    705         final double midPolar = minPolar + (0.5 * polarOffset);
    706         final double pastMinPolar = minPolar - polarOffset;
    707         final double pastMaxPolar = maxPolar + polarOffset;
    708
    709         SphericalTestUtils.checkClassify(tree, RegionLocation.OUTSIDE,
    710                 tree.getCentroid().antipodal(),
    711                 Point2S.of(pastMinAz, midPolar), Point2S.of(pastMaxAz, midPolar),
    712                 Point2S.of(midAz, pastMinPolar), Point2S.of(midAz, pastMaxPolar));
    713     }
    714
    715     @Test
    716     void testGeometricProperties_equalAndOppositeRegions() {
    717         // arrange
    718         final Point2S center = Point2S.PLUS_I;
    719         final double radius = 0.25 * Math.PI;
    720
    721         final RegionBSPTree2S a = buildDiamond(center, radius);
    722         final RegionBSPTree2S b = buildDiamond(center.antipodal(), radius);
    723
    724         // act
    725         final RegionBSPTree2S tree = RegionBSPTree2S.empty();
    726         tree.union(a, b);
    727
    728         // assert
    729         final double area = 8 * rightTriangleArea(radius, radius);
    730         Assertions.assertEquals(area, tree.getSize(), TEST_EPS);
    731
    732         final double boundarySize = 8 * sphericalHypot(radius, radius);
    733         Assertions.assertEquals(boundarySize, tree.getBoundarySize(), TEST_EPS);
    734
    735         // should be null since no unique centroid exists
    736         Assertions.assertNull(tree.getCentroid());
    737     }
    738
    739     @Test
    740     void testSplit_both() {
    741         // arrange
    742         final GreatCircle c1 = GreatCircles.fromPole(Vector3D.Unit.MINUS_X, TEST_PRECISION);
    743         final GreatCircle c2 = GreatCircles.fromPole(Vector3D.of(1, 1, 0), TEST_PRECISION);
    744
    745         final RegionBSPTree2S tree = ConvexArea2S.fromBounds(c1, c2).toTree();
    746
    747         final GreatCircle splitter = GreatCircles.fromPole(Vector3D.of(-1, 0, 1), TEST_PRECISION);
    748
    749         // act
    750         final Split<RegionBSPTree2S> split = tree.split(splitter);
    751
    752         // assert
    753         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
    754
    755         final Point2S p1 = c1.intersection(splitter);
    756         final Point2S p2 = splitter.intersection(c2);
    757
    758         final RegionBSPTree2S minus = split.getMinus();
    759         final List<GreatArcPath> minusPaths = minus.getBoundaryPaths();
    760         Assertions.assertEquals(1, minusPaths.size());
    761         assertPath(minusPaths.get(0), Point2S.PLUS_K, p1, p2, Point2S.PLUS_K);
    762
    763         final RegionBSPTree2S plus = split.getPlus();
    764         final List<GreatArcPath> plusPaths = plus.getBoundaryPaths();
    765         Assertions.assertEquals(1, plusPaths.size());
    766         assertPath(plusPaths.get(0), p1, Point2S.MINUS_K, p2, p1);
    767
    768         Assertions.assertEquals(tree.getSize(), minus.getSize() + plus.getSize(), TEST_EPS);
    769     }
    770
    771     @Test
    772     void testSplit_minus() {
    773         // arrange
    774         final RegionBSPTree2S tree = ConvexArea2S.fromVertexLoop(Arrays.asList(
    775                     Point2S.PLUS_I, Point2S.PLUS_K, Point2S.MINUS_J
    776                 ), TEST_PRECISION).toTree();
    777
    778         final GreatCircle splitter = GreatCircles.fromPole(Vector3D.of(0, -1, 1), TEST_PRECISION);
    779
    780         // act
    781         final Split<RegionBSPTree2S> split = tree.split(splitter);
    782
    783         // assert
    784         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
    785
    786         final RegionBSPTree2S minus = split.getMinus();
    787         Assertions.assertNotSame(tree, minus);
    788         Assertions.assertEquals(tree.getSize(), minus.getSize(), TEST_EPS);
    789
    790         Assertions.assertNull(split.getPlus());
    791     }
    792
    793     @Test
    794     void testSplit_plus() {
    795         // arrange
    796         final RegionBSPTree2S tree = ConvexArea2S.fromVertexLoop(Arrays.asList(
    797                     Point2S.PLUS_I, Point2S.PLUS_K, Point2S.MINUS_J
    798                 ), TEST_PRECISION).toTree();
    799
    800         final GreatCircle splitter = GreatCircles.fromPole(Vector3D.of(0, 1, -1), TEST_PRECISION);
    801
    802         // act
    803         final Split<RegionBSPTree2S> split = tree.split(splitter);
    804
    805         // assert
    806         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
    807
    808         Assertions.assertNull(split.getMinus());
    809
    810         final RegionBSPTree2S plus = split.getPlus();
    811         Assertions.assertNotSame(tree, plus);
    812         Assertions.assertEquals(tree.getSize(), plus.getSize(), TEST_EPS);
    813     }
    814
    815     @Test
    816     void testTransform() {
    817         // arrange
    818         final Transform2S t = Transform2S.createReflection(Point2S.PLUS_J);
    819         final RegionBSPTree2S tree = ConvexArea2S.fromVertexLoop(
    820                 Arrays.asList(Point2S.PLUS_I, Point2S.PLUS_J, Point2S.PLUS_K), TEST_PRECISION).toTree();
    821
    822         // act
    823         tree.transform(t);
    824
    825         // assert
    826         Assertions.assertFalse(tree.isFull());
    827         Assertions.assertFalse(tree.isEmpty());
    828         Assertions.assertEquals(1.5 * Math.PI, tree.getBoundarySize(), TEST_EPS);
    829         Assertions.assertEquals(Angle.PI_OVER_TWO, tree.getSize(), TEST_EPS);
    830
    831         final Point2S expectedCentroid = triangleCentroid(Point2S.MINUS_J, Point2S.PLUS_I, Point2S.PLUS_K);
    832         SphericalTestUtils.assertPointsEq(expectedCentroid, tree.getCentroid(), TEST_EPS);
    833
    834         checkCentroidConsistency(tree);
    835
    836         SphericalTestUtils.checkClassify(tree, RegionLocation.INSIDE,
    837                 Point2S.of(-0.25 * Math.PI, 0.25 * Math.PI));
    838
    839         SphericalTestUtils.checkClassify(tree, RegionLocation.BOUNDARY,
    840                 Point2S.PLUS_I, Point2S.MINUS_J, Point2S.PLUS_K,
    841                 Point2S.of(0, 0.25 * Math.PI), Point2S.of(-Angle.PI_OVER_TWO, 0.304 * Math.PI),
    842                 Point2S.of(-0.25 * Math.PI, Angle.PI_OVER_TWO));
    843
    844         SphericalTestUtils.checkClassify(tree, RegionLocation.OUTSIDE,
    845                 Point2S.PLUS_J, Point2S.MINUS_I, Point2S.MINUS_K);
    846     }
    847
    848     @Test
    849     void testRegionNode_getNodeRegion() {
    850         // arrange
    851         final RegionBSPTree2S tree = RegionBSPTree2S.empty();
    852
    853         final RegionNode2S root = tree.getRoot();
    854         final RegionNode2S minus = root.cut(EQUATOR).getMinus();
    855         final RegionNode2S minusPlus = minus.cut(X_MERIDIAN).getPlus();
    856
    857         // act/assert
    858         final ConvexArea2S rootRegion = root.getNodeRegion();
    859         Assertions.assertEquals(4 * Math.PI, rootRegion.getSize(), TEST_EPS);
    860         Assertions.assertNull(rootRegion.getCentroid());
    861
    862         final ConvexArea2S minusRegion = minus.getNodeRegion();
    863         Assertions.assertEquals(2 * Math.PI, minusRegion.getSize(), TEST_EPS);
    864         SphericalTestUtils.assertPointsEq(Point2S.PLUS_K, minusRegion.getCentroid(), TEST_EPS);
    865
    866         final ConvexArea2S minusPlusRegion = minusPlus.getNodeRegion();
    867         Assertions.assertEquals(Math.PI, minusPlusRegion.getSize(), TEST_EPS);
    868         SphericalTestUtils.assertPointsEq(Point2S.of(1.5 * Math.PI, 0.25 * Math.PI),
    869                 minusPlusRegion.getCentroid(), TEST_EPS);
    870     }
    871
    872     @Test
    873     void testGeographicMap() {
    874         // arrange
    875         final RegionBSPTree2S continental = latLongToTree(TEST_PRECISION, new double[][] {
    876                 {51.14850,  2.51357}, {50.94660,  1.63900}, {50.12717,  1.33876}, {49.34737, -0.98946},
    877                 {49.77634, -1.93349}, {48.64442, -1.61651}, {48.90169, -3.29581}, {48.68416, -4.59234},
    878                 {47.95495, -4.49155}, {47.57032, -2.96327}, {46.01491, -1.19379}, {44.02261, -1.38422},
    879                 {43.42280, -1.90135}, {43.03401, -1.50277}, {42.34338,  1.82679}, {42.47301,  2.98599},
    880                 {43.07520,  3.10041}, {43.39965,  4.55696}, {43.12889,  6.52924}, {43.69384,  7.43518},
    881                 {44.12790,  7.54959}, {45.02851,  6.74995}, {45.33309,  7.09665}, {46.42967,  6.50009},
    882                 {46.27298,  6.02260}, {46.72577,  6.03738}, {47.62058,  7.46675}, {49.01778,  8.09927},
    883                 {49.20195,  6.65822}, {49.44266,  5.89775}, {49.98537,  4.79922}
    884             });
    885         final RegionBSPTree2S corsica = latLongToTree(TEST_PRECISION, new double[][] {
    886                 {42.15249,  9.56001}, {43.00998,  9.39000}, {42.62812,  8.74600}, {42.25651,  8.54421},
    887                 {41.58361,  8.77572}, {41.38000,  9.22975}
    888             });
    889
    890         // act
    891         final RegionBSPTree2S france = RegionBSPTree2S.empty();
    892         france.union(continental, corsica);
    893
    894         // assert
    895         Assertions.assertEquals(0.6316801448267251, france.getBoundarySize(), TEST_EPS);
    896         Assertions.assertEquals(0.013964220234478741, france.getSize(), TEST_EPS);
    897
    898         SphericalTestUtils.assertPointsEq(Point2S.of(0.04368552749392928, 0.7590839905197961),
    899                 france.getCentroid(), CENTROID_EPS);
    900
    901         checkCentroidConsistency(france);
    902     }
    903
    904     @Test
    905     void testCircleToPolygonCentroid() {
    906         final double radius = 0.0001;
    907         final Point2S center = Point2S.of(1.0, 1.0);
    908         final int numPts = 200;
    909
    910         // counterclockwise
    911         final RegionBSPTree2S ccw = circleToPolygon(center, radius, numPts, false, TEST_PRECISION);
    912         SphericalTestUtils.assertPointsEq(center, ccw.getCentroid(), TEST_EPS);
    913
    914         // clockwise; centroid should just be antipodal for the circle center
    915         final RegionBSPTree2S cw = circleToPolygon(center, radius, numPts, true, TEST_PRECISION);
    916
    917         SphericalTestUtils.assertPointsEq(center.antipodal(), cw.getCentroid(), CENTROID_EPS);
    918     }
    919
    920     @Test
    921     void testCircleToPolygonSize() {
    922         final double radius = 0.0001;
    923         final Point2S center = Point2S.of(1.0, 1.0);
    924         final int numPts = 200;
    925
    926         // https://en.wikipedia.org/wiki/Spherical_cap
    927         final double ccwArea = 4.0 * Math.PI * Math.pow(Math.sin(radius / 2.0), 2.0);
    928         final double cwArea = 4.0 * Math.PI - ccwArea;
    929
    930         final RegionBSPTree2S ccw = circleToPolygon(center, radius, numPts, false, TEST_PRECISION);
    931         Assertions.assertEquals(ccwArea, ccw.getSize(), TEST_EPS, "Counterclockwise size");
    932
    933         final RegionBSPTree2S cw = circleToPolygon(center, radius, numPts, true, TEST_PRECISION);
    934         Assertions.assertEquals(cwArea, cw.getSize(), TEST_EPS, "Clockwise size");
    935     }
    936
    937     @Test
    938     void testCircleToPolygonBoundarySize() {
    939         final double radius = 0.0001;
    940         final Point2S center = Point2S.of(1.0, 1.0);
    941         final int numPts = 200;
    942
    943         // boundary size is independent from winding
    944         final double boundary = Angle.TWO_PI * Math.sin(radius);
    945
    946         final RegionBSPTree2S ccw = circleToPolygon(center, radius, numPts, false, TEST_PRECISION);
    947         Assertions.assertEquals(boundary, ccw.getBoundarySize(), 1.0e-7, "Counterclockwise boundary size");
    948
    949         final RegionBSPTree2S cw = circleToPolygon(center, radius, numPts, true, TEST_PRECISION);
    950         Assertions.assertEquals(boundary, cw.getBoundarySize(), 1.0e-7, "Clockwise boundary size");
    951     }
    952
    953     @Test
    954     void testSmallCircleToPolygon() {
    955         // arrange
    956         final double radius = 5.0e-8;
    957         final Point2S center = Point2S.of(0.5, 1.5);
    958         final int numPts = 100;
    959
    960         // act
    961         final RegionBSPTree2S circle = circleToPolygon(center, radius, numPts, false, TEST_PRECISION);
    962
    963         // assert
    964         // https://en.wikipedia.org/wiki/Spherical_cap
    965         final double area = 4.0 * Math.PI * Math.pow(Math.sin(radius / 2.0), 2.0);
    966         final double boundary = Angle.TWO_PI * Math.sin(radius);
    967
    968         SphericalTestUtils.assertPointsEq(center, circle.getCentroid(), TEST_EPS);
    969         Assertions.assertEquals(area, circle.getSize(), TEST_EPS);
    970         Assertions.assertEquals(boundary, circle.getBoundarySize(), TEST_EPS);
    971     }
    972
    973     @Test
    974     void testSmallGeographicalRectangle() {
    975         // arrange
    976         final double[][] vertices = {
    977             {42.656216727628696, -70.61919768884546},
    978             {42.65612858998112, -70.61938607250165},
    979             {42.65579098923594, -70.61909615581666},
    980             {42.655879126692355, -70.61890777301083}
    981         };
    982
    983         // act
    984         final RegionBSPTree2S rectangle = latLongToTree(TEST_PRECISION, vertices);
    985
    986         // assert
    987         // approximate the centroid as average of vertices
    988         final double avgLat = Stream.of(vertices).mapToDouble(v -> v[0]).average().getAsDouble();
    989         final double avgLon = Stream.of(vertices).mapToDouble(v -> v[1]).average().getAsDouble();
    990         final Point2S expectedCentroid = latLongToPoint(avgLat, avgLon);
    991
    992         SphericalTestUtils.assertPointsEq(expectedCentroid, rectangle.getCentroid(), TEST_EPS);
    993
    994         // expected results computed using GeographicLib (https://geographiclib.sourceforge.io/)
    995         Assertions.assertEquals(1.997213869978027E-11, rectangle.getSize(), TEST_EPS);
    996         Assertions.assertEquals(1.9669710464585642E-5, rectangle.getBoundarySize(), TEST_EPS);
    997     }
    998
    999     /**
    1000      * Insert hyperplane convex subsets defining the positive quadrant area.
    1001      * @param tree
    1002      */
    1003     private static void insertPositiveQuadrant(final RegionBSPTree2S tree) {
    1004         tree.insert(Arrays.asList(
    1005                 EQUATOR.arc(Point2S.PLUS_I, Point2S.PLUS_J),
    1006                 X_MERIDIAN.arc(Point2S.PLUS_K, Point2S.PLUS_I),
    1007                 Y_MERIDIAN.arc(Point2S.PLUS_J, Point2S.PLUS_K)
    1008             ));
    1009     }
    1010
    1011     private static Point2S triangleCentroid(final Point2S p1, final Point2S p2, final Point2S p3) {
    1012         // compute the centroid using intersection mid point arcs
    1013         final GreatCircle c1 = GreatCircles.fromPoints(p1, p2.slerp(p3, 0.5), TEST_PRECISION);
    1014         final GreatCircle c2 = GreatCircles.fromPoints(p2, p1.slerp(p3, 0.5), TEST_PRECISION);
    1015
    1016         return c1.intersection(c2);
    1017     }
    1018
    1019     /** Assert that the given path contains {@code vertices} in the exact order given.
    1020      * @param path path to check
    1021      * @param vertices expected vertices
    1022      */
    1023     private static void assertPath(final GreatArcPath path, final Point2S... vertices) {
    1024         final List<Point2S> expected = Arrays.asList(vertices);
    1025         final List<Point2S> actual = path.getVertices();
    1026
    1027         if (expected.size() != actual.size()) {
    1028             Assertions.fail("Unexpected path size. Expected path " + expected +
    1029                     " but was " + actual);
    1030         }
    1031
    1032         for (int i = 0; i < expected.size(); ++i) {
    1033             if (!expected.get(i).eq(actual.get(i), TEST_PRECISION)) {
    1034                 Assertions.fail("Unexpected path vertex at index " + i + ". Expected path " + expected +
    1035                         " but was " + actual);
    1036             }
    1037         }
    1038     }
    1039
    1040     /** Assert that the given path contains {@code vertices} in a closed loop sequence. The
    1041      * actual path may start at any point in the sequence.
    1042      * @param path path to check
    1043      * @param vertices expected vertex loop without repeated points
    1044      */
    1045     private static void assertPathLoop(final GreatArcPath path, final Point2S... vertices) {
    1046         final List<Point2S> expected = Arrays.asList(vertices);
    1047         final List<Point2S> actual = path.getVertices();
    1048
    1049         Assertions.assertTrue(path.isClosed());
    1050         Assertions.assertFalse(path.isEmpty());
    1051         Assertions.assertTrue(actual.get(0).eq(actual.get(actual.size() - 1), TEST_PRECISION));
    1052
    1053         final List<Point2S> actualLoopVertices = actual.subList(0, actual.size() - 1);
    1054
    1055         if (expected.size() != actualLoopVertices.size()) {
    1056             Assertions.fail("Unexpected path loop. Expected vertex loop " + expected +
    1057                     " but " + actual);
    1058         }
    1059
    1060         int offset = -1;
    1061         final Point2S start = expected.get(0);
    1062         for (int i = 0; i < actualLoopVertices.size(); ++i) {
    1063             if (actualLoopVertices.get(i).eq(start, TEST_PRECISION)) {
    1064                 offset = i;
    1065                 break;
    1066             }
    1067         }
    1068
    1069         if (offset < 0) {
    1070             Assertions.fail("Vertex loops do not share any points: expected vertex loop " + expected +
    1071                     " but was " + actual);
    1072         }
    1073
    1074         for (int i = 0; i < expected.size(); ++i) {
    1075             final Point2S expectedVertex = expected.get(i % expected.size());
    1076             final Point2S actualVertex = actualLoopVertices.get((i + offset) % actualLoopVertices.size());
    1077
    1078             if (!expectedVertex.eq(actualVertex, TEST_PRECISION)) {
    1079                 Assertions.fail("Unexpected vertex at index " + i + ": expected " + expectedVertex +
    1080                         " but was " + actualVertex);
    1081             }
    1082         }
    1083     }
    1084
    1085     private static RegionBSPTree2S latLongToTree(final Precision.DoubleEquivalence precision, final double[][] points) {
    1086         final GreatArcPath.Builder pathBuilder = GreatArcPath.builder(precision);
    1087
    1088         for (final double[] point : points) {
    1089             pathBuilder.append(latLongToPoint(point[0], point[1]));
    1090         }
    1091
    1092         return pathBuilder.close().toTree();
    1093     }
    1094
    1095     private static Point2S latLongToPoint(final double latitude, final double longitude) {
    1096         return Point2S.of(Math.toRadians(longitude), Math.toRadians(90.0 - latitude));
    1097     }
    1098
    1099     private static void checkCentroidConsistency(final RegionBSPTree2S region) {
    1100         final Point2S centroid = region.getCentroid();
    1101         final double size = region.getSize();
    1102
    1103         final GreatCircle circle = GreatCircles.fromPole(centroid.getVector(), TEST_PRECISION);
    1104         for (double az = 0; az <= Angle.TWO_PI; az += 0.2) {
    1105             final Point2S pt = circle.toSpace(Point1S.of(az));
    1106             final GreatCircle splitter = GreatCircles.fromPoints(centroid, pt, TEST_PRECISION);
    1107
    1108             final Split<RegionBSPTree2S> split = region.split(splitter);
    1109
    1110             Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
    1111
    1112             final RegionBSPTree2S minus = split.getMinus();
    1113             final double minusSize = minus.getSize();
    1114
    1115             final RegionBSPTree2S plus = split.getPlus();
    1116             final double plusSize = plus.getSize();
    1117
    1118             final Point2S computedCentroid = Point2S.from(weightedCentroidVector(minus)
    1119                     .add(weightedCentroidVector(plus)));
    1120
    1121             Assertions.assertEquals(size, minusSize + plusSize, TEST_EPS);
    1122             SphericalTestUtils.assertPointsEq(centroid, computedCentroid, TEST_EPS);
    1123         }
    1124     }
    1125
    1126     private static Vector3D weightedCentroidVector(final RegionBSPTree2S tree) {
    1127         Vector3D sum = Vector3D.ZERO;
    1128         for (final ConvexArea2S convex : tree.toConvex()) {
    1129             sum = sum.add(convex.getWeightedCentroidVector());
    1130         }
    1131
    1132         return sum;
    1133     }
    1134
    1135     private static RegionBSPTree2S buildDiamond(final Point2S center, final double radius) {
    1136         final Vector3D u = center.getVector();
    1137         final Vector3D w = u.orthogonal(Vector3D.Unit.PLUS_Z);
    1138         final Vector3D v = w.cross(u);
    1139
    1140         final Transform2S rotV = Transform2S.createRotation(v, radius);
    1141         final Transform2S rotW = Transform2S.createRotation(w, radius);
    1142
    1143         final Point2S top = rotV.inverse().apply(center);
    1144         final Point2S bottom = rotV.apply(center);
    1145
    1146         final Point2S right = rotW.apply(center);
    1147         final Point2S left = rotW.inverse().apply(center);
    1148
    1149         return GreatArcPath.fromVertexLoop(Arrays.asList(top, left, bottom, right), TEST_PRECISION)
    1150                 .toTree();
    1151     }
    1152
    1153     /** Solve for the hypotenuse of a spherical right triangle, given the lengths of the
    1154      * other two side. The sides must have lengths less than pi/2.
    1155      * @param a first side; must be less than pi/2
    1156      * @param b second side; must be less than pi/2
    1157      * @return the hypotenuse of the spherical right triangle with sides of the given lengths
    1158      */
    1159     private static double sphericalHypot(final double a, final double b) {
    1160         // use the spherical law of cosines and the fact that cos(pi/2) = 0
    1161         // https://en.wikipedia.org/wiki/Spherical_trigonometry#Cosine_rules
    1162         return Math.acos(Math.cos(a) * Math.cos(b));
    1163     }
    1164
    1165     /**
    1166      * Compute the area of the spherical right triangle with the given sides. The sides must have lengths
    1167      * less than pi/2.
    1168      * @param a first side; must be less than pi/2
    1169      * @param b second side; must be less than pi/2
    1170      * @return the area of the spherical right triangle
    1171      */
    1172     private static double rightTriangleArea(final double a, final double b) {
    1173         final double c = sphericalHypot(a, b);
    1174
    1175         // use the spherical law of sines to determine the interior angles
    1176         // https://en.wikipedia.org/wiki/Spherical_trigonometry#Sine_rules
    1177         final double sinC = Math.sin(c);
    1178         final double angleA = Math.asin(Math.sin(a) / sinC);
    1179         final double angleB = Math.asin(Math.sin(b) / sinC);
    1180
    1181         // use Girard's theorem
    1182         return angleA + angleB - Angle.PI_OVER_TWO;
    1183     }
    1184
    1185     private static RegionBSPTree2S circleToPolygon(final Point2S center, final double radius, final int numPts,
    1186                                                    final boolean clockwise, final Precision.DoubleEquivalence precision) {
    1187         final List<Point2S> pts = new ArrayList<>(numPts);
    1188
    1189         // get an arbitrary point on the circle boundary
    1190         pts.add(Transform2S.createRotation(center.getVector().orthogonal(), radius).apply(center));
    1191
    1192         // create the list of boundary points by rotating the previous point around the circle center
    1193         final double span = Angle.TWO_PI / numPts;
    1194
    1195         // negate the span for clockwise winding
    1196         final Transform2S rotate = Transform2S.createRotation(center, clockwise ? -span : span);
    1197         for (int i = 1; i < numPts; ++i) {
    1198             pts.add(rotate.apply(pts.get(i - 1)));
    1199         }
    1200
    1201         return GreatArcPath.fromVertexLoop(pts, precision).toTree();
    1202     }
    1203 }