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 }