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