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