1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.geometry.spherical.twod;
18
19 import java.util.List;
20
21 import org.apache.commons.geometry.core.GeometryTestUtils;
22 import org.apache.commons.geometry.core.RegionLocation;
23 import org.apache.commons.geometry.core.partitioning.HyperplaneSubset;
24 import org.apache.commons.geometry.core.partitioning.Split;
25 import org.apache.commons.geometry.core.partitioning.SplitLocation;
26 import org.apache.commons.geometry.euclidean.threed.Vector3D;
27 import org.apache.commons.geometry.spherical.SphericalTestUtils;
28 import org.apache.commons.geometry.spherical.oned.AngularInterval;
29 import org.apache.commons.geometry.spherical.oned.Point1S;
30 import org.apache.commons.geometry.spherical.oned.RegionBSPTree1S;
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 EmbeddedTreeSubGreatCircleTest {
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 private static final GreatCircle XY_CIRCLE = GreatCircles.fromPoleAndU(
44 Vector3D.Unit.PLUS_Z, Vector3D.Unit.PLUS_X, TEST_PRECISION);
45
46 @Test
47 void testCtor_default() {
48
49 final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(XY_CIRCLE);
50
51
52 Assertions.assertSame(XY_CIRCLE, sub.getHyperplane());
53 Assertions.assertSame(TEST_PRECISION, sub.getPrecision());
54 Assertions.assertFalse(sub.isFull());
55 Assertions.assertTrue(sub.isEmpty());
56 Assertions.assertTrue(sub.isFinite());
57 Assertions.assertFalse(sub.isInfinite());
58
59 Assertions.assertEquals(0, sub.getSize(), TEST_EPS);
60 Assertions.assertNull(sub.getCentroid());
61
62 for (double az = 0; az <= Angle.TWO_PI; az += 0.5) {
63 for (double p = 0; p <= Math.PI; p += 0.5) {
64 checkClassify(sub, RegionLocation.OUTSIDE, Point2S.of(az, p));
65 }
66 }
67 }
68
69 @Test
70 void testCtor_boolean_true() {
71
72 final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(XY_CIRCLE, true);
73
74
75 Assertions.assertTrue(sub.isFull());
76 Assertions.assertFalse(sub.isEmpty());
77 Assertions.assertTrue(sub.isFinite());
78 Assertions.assertFalse(sub.isInfinite());
79
80 Assertions.assertEquals(Angle.TWO_PI, sub.getSize(), TEST_EPS);
81 Assertions.assertNull(sub.getCentroid());
82
83 for (double az = 0; az < Angle.TWO_PI; az += 0.1) {
84 checkClassify(sub, RegionLocation.INSIDE, Point2S.of(az, Angle.PI_OVER_TWO));
85 }
86
87 checkClassify(sub, RegionLocation.OUTSIDE,
88 Point2S.PLUS_K, Point2S.of(0, Angle.PI_OVER_TWO + 0.1),
89 Point2S.MINUS_K, Point2S.of(0, Angle.PI_OVER_TWO - 0.1));
90 }
91
92 @Test
93 void testCtor_boolean_false() {
94
95 final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(XY_CIRCLE, false);
96
97
98 Assertions.assertFalse(sub.isFull());
99 Assertions.assertTrue(sub.isEmpty());
100 Assertions.assertTrue(sub.isFinite());
101 Assertions.assertFalse(sub.isInfinite());
102
103 Assertions.assertEquals(0, sub.getSize(), TEST_EPS);
104 Assertions.assertNull(sub.getCentroid());
105
106 for (double az = 0; az <= Angle.TWO_PI; az += 0.5) {
107 for (double p = 0; p <= Math.PI; p += 0.5) {
108 checkClassify(sub, RegionLocation.OUTSIDE, Point2S.of(az, p));
109 }
110 }
111 }
112
113 @Test
114 void testCtor_tree() {
115
116 final RegionBSPTree1S tree = RegionBSPTree1S.fromInterval(AngularInterval.of(1, 2, TEST_PRECISION));
117
118
119 final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(XY_CIRCLE, tree);
120
121
122 Assertions.assertFalse(sub.isFull());
123 Assertions.assertFalse(sub.isEmpty());
124 Assertions.assertTrue(sub.isFinite());
125 Assertions.assertFalse(sub.isInfinite());
126
127 Assertions.assertEquals(1, sub.getSize(), TEST_EPS);
128 SphericalTestUtils.assertPointsEq(Point2S.of(1.5, Angle.PI_OVER_TWO),
129 sub.getCentroid(), TEST_EPS);
130
131 checkClassify(sub, RegionLocation.INSIDE, Point2S.of(1.5, Angle.PI_OVER_TWO));
132
133 checkClassify(sub, RegionLocation.BOUNDARY,
134 Point2S.of(1, Angle.PI_OVER_TWO), Point2S.of(2, Angle.PI_OVER_TWO));
135
136 checkClassify(sub, RegionLocation.OUTSIDE,
137 Point2S.of(0.5, Angle.PI_OVER_TWO), Point2S.of(2.5, Angle.PI_OVER_TWO),
138 Point2S.of(1.5, 1), Point2S.of(1.5, Math.PI - 1));
139 }
140
141 @Test
142 void testToSubspace() {
143
144 final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(XY_CIRCLE);
145
146
147 SphericalTestUtils.assertPointsEqual(Point1S.of(1), sub.toSubspace(Point2S.of(1, 0.5)), TEST_EPS);
148 SphericalTestUtils.assertPointsEqual(Point1S.of(1), sub.toSubspace(Point2S.of(1, 0.75)), TEST_EPS);
149 }
150
151 @Test
152 void testToSpace() {
153
154 final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(XY_CIRCLE);
155
156
157 SphericalTestUtils.assertPointsEqual(Point2S.of(0, 0.5 * Math.PI), sub.toSpace(Point1S.of(0)), TEST_EPS);
158 SphericalTestUtils.assertPointsEqual(Point2S.of(1, 0.5 * Math.PI), sub.toSpace(Point1S.of(1)), TEST_EPS);
159 }
160
161 @Test
162 void testClosest() {
163
164 final RegionBSPTree1S tree = RegionBSPTree1S.fromInterval(AngularInterval.of(1, 2, TEST_PRECISION));
165 final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(XY_CIRCLE, tree);
166
167 final double halfPi = 0.5 * Math.PI;
168 final double above = halfPi - 0.1;
169 final double below = halfPi + 0.1;
170
171
172 SphericalTestUtils.assertPointsEq(Point2S.of(1, halfPi), sub.closest(Point2S.of(0, above)), TEST_EPS);
173 SphericalTestUtils.assertPointsEq(Point2S.of(1, halfPi), sub.closest(Point2S.of(0, below)), TEST_EPS);
174
175 SphericalTestUtils.assertPointsEq(Point2S.of(1, halfPi), sub.closest(Point2S.of(1, above)), TEST_EPS);
176 SphericalTestUtils.assertPointsEq(Point2S.of(1, halfPi), sub.closest(Point2S.of(1, below)), TEST_EPS);
177
178 SphericalTestUtils.assertPointsEq(Point2S.of(1.5, halfPi), sub.closest(Point2S.of(1.5, above)), TEST_EPS);
179 SphericalTestUtils.assertPointsEq(Point2S.of(1.5, halfPi), sub.closest(Point2S.of(1.5, below)), TEST_EPS);
180
181 SphericalTestUtils.assertPointsEq(Point2S.of(2, halfPi), sub.closest(Point2S.of(2, above)), TEST_EPS);
182 SphericalTestUtils.assertPointsEq(Point2S.of(2, halfPi), sub.closest(Point2S.of(2, below)), TEST_EPS);
183
184 SphericalTestUtils.assertPointsEq(Point2S.of(2, halfPi), sub.closest(Point2S.of(3, above)), TEST_EPS);
185 SphericalTestUtils.assertPointsEq(Point2S.of(2, halfPi), sub.closest(Point2S.of(3, below)), TEST_EPS);
186 }
187
188 @Test
189 void testTransform() {
190
191 final GreatCircle circle = GreatCircles.fromPoints(Point2S.PLUS_K, Point2S.MINUS_I, TEST_PRECISION);
192 final RegionBSPTree1S region = RegionBSPTree1S.empty();
193 region.add(AngularInterval.of(Math.PI, -Angle.PI_OVER_TWO, TEST_PRECISION));
194 region.add(AngularInterval.of(0, Angle.PI_OVER_TWO, TEST_PRECISION));
195
196 final Transform2S t = Transform2S.createRotation(Point2S.PLUS_I, Angle.PI_OVER_TWO)
197 .reflect(Point2S.of(-0.25 * Math.PI, Angle.PI_OVER_TWO));
198
199 final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle, region);
200
201
202 final EmbeddedTreeGreatCircleSubset result = sub.transform(t);
203
204
205 final List<GreatArc> arcs = result.toConvex();
206 Assertions.assertEquals(2, arcs.size());
207
208 checkArc(arcs.get(0), Point2S.MINUS_I, Point2S.MINUS_J);
209 checkArc(arcs.get(1), Point2S.PLUS_I, Point2S.PLUS_J);
210 }
211
212 @Test
213 void testSplit_full() {
214
215 final GreatCircle circle = GreatCircles.fromPoints(Point2S.PLUS_I, Point2S.PLUS_J, TEST_PRECISION);
216 final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle, true);
217
218 final GreatCircle splitter = GreatCircles.fromPole(Vector3D.of(-1, 0, 1), TEST_PRECISION);
219
220
221 final Split<EmbeddedTreeGreatCircleSubset> split = sub.split(splitter);
222
223
224 Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
225
226 final EmbeddedTreeGreatCircleSubset minus = split.getMinus();
227 Assertions.assertSame(sub.getCircle(), minus.getCircle());
228
229 final List<GreatArc> minusArcs = minus.toConvex();
230 Assertions.assertEquals(1, minusArcs.size());
231 checkArc(minusArcs.get(0), Point2S.MINUS_J, Point2S.PLUS_J);
232
233 checkClassify(minus, RegionLocation.OUTSIDE, Point2S.MINUS_I);
234 checkClassify(minus, RegionLocation.INSIDE, Point2S.PLUS_I);
235
236 final EmbeddedTreeGreatCircleSubset plus = split.getPlus();
237 Assertions.assertSame(sub.getCircle(), plus.getCircle());
238
239 final List<GreatArc> plusArcs = plus.toConvex();
240 Assertions.assertEquals(1, plusArcs.size());
241 checkArc(plusArcs.get(0), Point2S.PLUS_J, Point2S.MINUS_J);
242
243 checkClassify(plus, RegionLocation.INSIDE, Point2S.MINUS_I);
244 checkClassify(plus, RegionLocation.OUTSIDE, Point2S.PLUS_I);
245 }
246
247 @Test
248 void testSplit_empty() {
249
250 final GreatCircle circle = GreatCircles.fromPoints(Point2S.PLUS_I, Point2S.PLUS_J, TEST_PRECISION);
251 final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle, false);
252
253 final GreatCircle splitter = GreatCircles.fromPole(Vector3D.of(-1, 0, 1), TEST_PRECISION);
254
255
256 final Split<EmbeddedTreeGreatCircleSubset> split = sub.split(splitter);
257
258
259 Assertions.assertEquals(SplitLocation.NEITHER, split.getLocation());
260
261 final EmbeddedTreeGreatCircleSubset minus = split.getMinus();
262 Assertions.assertNull(minus);
263
264 final EmbeddedTreeGreatCircleSubset plus = split.getPlus();
265 Assertions.assertNull(plus);
266 }
267
268 @Test
269 void testSplit_both() {
270
271 final GreatCircle circle = GreatCircles.fromPoints(Point2S.PLUS_J, Point2S.PLUS_K, TEST_PRECISION);
272
273 final RegionBSPTree1S tree = RegionBSPTree1S.empty();
274 tree.add(AngularInterval.of(0, 1, TEST_PRECISION));
275 tree.add(AngularInterval.of(Angle.PI_OVER_TWO, Math.PI, TEST_PRECISION));
276 tree.add(AngularInterval.of(Math.PI + 1, Math.PI + 2, TEST_PRECISION));
277
278 final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle, tree);
279
280 final GreatCircle splitter = GreatCircles.fromPole(Vector3D.of(0, 1, 1), TEST_PRECISION);
281
282
283 final Split<EmbeddedTreeGreatCircleSubset> split = sub.split(splitter);
284
285
286 Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
287
288 final EmbeddedTreeGreatCircleSubset minus = split.getMinus();
289 Assertions.assertSame(sub.getCircle(), minus.getCircle());
290 final List<GreatArc> minusArcs = minus.toConvex();
291 Assertions.assertEquals(2, minusArcs.size());
292 checkArc(minusArcs.get(0), Point2S.of(1.5 * Math.PI, 0.25 * Math.PI), Point2S.MINUS_J);
293 checkArc(minusArcs.get(1), Point2S.of(1.5 * Math.PI, Angle.PI_OVER_TWO + 1),
294 Point2S.of(0.5 * Math.PI, (1.5 * Math.PI) - 2));
295
296 final EmbeddedTreeGreatCircleSubset plus = split.getPlus();
297 Assertions.assertSame(sub.getCircle(), plus.getCircle());
298 final List<GreatArc> plusArcs = plus.toConvex();
299 Assertions.assertEquals(2, plusArcs.size());
300 checkArc(plusArcs.get(0), Point2S.of(Angle.PI_OVER_TWO, Angle.PI_OVER_TWO), Point2S.of(Angle.PI_OVER_TWO, Angle.PI_OVER_TWO - 1));
301 checkArc(plusArcs.get(1), Point2S.of(0, 0), Point2S.of(1.5 * Math.PI, 0.25 * Math.PI));
302 }
303
304 @Test
305 void testSplit_minus() {
306
307 final GreatCircle circle = GreatCircles.fromPoints(Point2S.PLUS_J, Point2S.PLUS_K, TEST_PRECISION);
308 final RegionBSPTree1S tree = AngularInterval.of(Angle.PI_OVER_TWO, Math.PI, TEST_PRECISION).toTree();
309
310 final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle, tree);
311
312 final GreatCircle splitter = GreatCircles.fromPole(Vector3D.Unit.from(-1, 0, -1), TEST_PRECISION);
313
314
315 final Split<EmbeddedTreeGreatCircleSubset> split = sub.split(splitter);
316
317
318 Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
319
320 final EmbeddedTreeGreatCircleSubset minus = split.getMinus();
321 Assertions.assertSame(sub, minus);
322
323 final EmbeddedTreeGreatCircleSubset plus = split.getPlus();
324 Assertions.assertNull(plus);
325 }
326
327 @Test
328 void testSplit_plus() {
329
330 final GreatCircle circle = GreatCircles.fromPoints(Point2S.PLUS_J, Point2S.PLUS_K, TEST_PRECISION);
331 final RegionBSPTree1S tree = AngularInterval.of(Angle.PI_OVER_TWO, Math.PI, TEST_PRECISION).toTree();
332
333 final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle, tree);
334
335 final GreatCircle splitter = GreatCircles.fromPole(Vector3D.Unit.PLUS_Z, TEST_PRECISION);
336
337
338 final Split<EmbeddedTreeGreatCircleSubset> split = sub.split(splitter);
339
340
341 Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
342
343 final EmbeddedTreeGreatCircleSubset minus = split.getMinus();
344 Assertions.assertNull(minus);
345
346 final EmbeddedTreeGreatCircleSubset plus = split.getPlus();
347 Assertions.assertSame(sub, plus);
348 }
349
350 @Test
351 void testSplit_parallelAndAntiparallel() {
352
353 final GreatCircle circle = GreatCircles.fromPoints(Point2S.PLUS_I, Point2S.PLUS_J, TEST_PRECISION);
354 final RegionBSPTree1S tree = AngularInterval.of(Angle.PI_OVER_TWO, Math.PI, TEST_PRECISION).toTree();
355
356 final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle, tree);
357
358
359 Assertions.assertEquals(SplitLocation.NEITHER,
360 sub.split(GreatCircles.fromPole(Vector3D.Unit.PLUS_Z, TEST_PRECISION)).getLocation());
361 Assertions.assertEquals(SplitLocation.NEITHER,
362 sub.split(GreatCircles.fromPole(Vector3D.Unit.MINUS_Z, TEST_PRECISION)).getLocation());
363 }
364
365 @Test
366 void testAdd_arc() {
367
368 final GreatCircle circle = GreatCircles.fromPoints(Point2S.MINUS_K, Point2S.MINUS_J, TEST_PRECISION);
369 final GreatCircle closeCircle = GreatCircles.fromPoints(Point2S.MINUS_K,
370 Point2S.of((1.5 * Math.PI) - 1e-11, Angle.PI_OVER_TWO), TEST_PRECISION);
371
372 final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle);
373
374
375 sub.add(circle.arc(Point2S.of(1.5 * Math.PI, 0.75 * Math.PI), Point2S.MINUS_J));
376 sub.add(closeCircle.arc(Point2S.PLUS_J, Point2S.of(1.5 * Math.PI, 0.75 * Math.PI)));
377
378
379 final List<GreatArc> arcs = sub.toConvex();
380
381 Assertions.assertEquals(1, arcs.size());
382 checkArc(arcs.get(0), Point2S.PLUS_J, Point2S.MINUS_J);
383 }
384
385 @Test
386 void testAdd_arc_differentCircle() {
387
388 final GreatCircle circle = GreatCircles.fromPoints(Point2S.MINUS_K, Point2S.MINUS_J, TEST_PRECISION);
389 final GreatCircle otherCircle = GreatCircles.fromPoints(Point2S.MINUS_K,
390 Point2S.of((1.5 * Math.PI) - 1e-2, Angle.PI_OVER_TWO), TEST_PRECISION);
391
392 final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle);
393
394 Assertions.assertThrows(IllegalArgumentException.class, () -> sub.add(otherCircle.arc(Point2S.PLUS_J, Point2S.of(1.5 * Math.PI, 0.75 * Math.PI))));
395 }
396
397 @Test
398 void testAdd_subGreatCircle() {
399
400 final GreatCircle circle = GreatCircles.fromPoints(Point2S.MINUS_K, Point2S.MINUS_J, TEST_PRECISION);
401 final GreatCircle closeCircle = GreatCircles.fromPoints(Point2S.MINUS_K,
402 Point2S.of((1.5 * Math.PI) - 1e-11, Angle.PI_OVER_TWO), TEST_PRECISION);
403
404 final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle);
405
406 final RegionBSPTree1S regionA = RegionBSPTree1S.empty();
407 regionA.add(AngularInterval.of(Math.PI, 1.25 * Math.PI, TEST_PRECISION));
408 regionA.add(AngularInterval.of(0.25 * Math.PI, Angle.PI_OVER_TWO, TEST_PRECISION));
409
410 final RegionBSPTree1S regionB = RegionBSPTree1S.empty();
411 regionB.add(AngularInterval.of(1.5 * Math.PI, 0.25 * Math.PI, TEST_PRECISION));
412
413
414 sub.add(new EmbeddedTreeGreatCircleSubset(circle, regionA));
415 sub.add(new EmbeddedTreeGreatCircleSubset(closeCircle, regionB));
416
417
418 final List<GreatArc> arcs = sub.toConvex();
419
420 Assertions.assertEquals(2, arcs.size());
421 checkArc(arcs.get(0), Point2S.of(Angle.PI_OVER_TWO, 0), Point2S.of(Angle.PI_OVER_TWO, 0.25 * Math.PI));
422 checkArc(arcs.get(1), Point2S.PLUS_J, Point2S.MINUS_J);
423 }
424
425 @Test
426 void testAdd_subGreatCircle_otherCircle() {
427
428 final GreatCircle circle = GreatCircles.fromPoints(Point2S.MINUS_K, Point2S.MINUS_J, TEST_PRECISION);
429 final GreatCircle otherCircle = GreatCircles.fromPoints(Point2S.MINUS_K, Point2S.of((1.5 * Math.PI) - 1e-5, Angle.PI_OVER_TWO), TEST_PRECISION);
430
431 final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle);
432
433
434 Assertions.assertThrows(IllegalArgumentException.class, () -> sub.add(new EmbeddedTreeGreatCircleSubset(otherCircle, RegionBSPTree1S.full())));
435 }
436
437 @Test
438 void testToString() {
439
440 final GreatCircle circle = GreatCircles.fromPoints(Point2S.PLUS_I, Point2S.PLUS_J, TEST_PRECISION);
441 final EmbeddedTreeGreatCircleSubset sub = new EmbeddedTreeGreatCircleSubset(circle);
442
443
444 final String str = sub.toString();
445
446
447 GeometryTestUtils.assertContains("EmbeddedTreeGreatCircleSubset[", str);
448 GeometryTestUtils.assertContains("circle= GreatCircle[", str);
449 GeometryTestUtils.assertContains("region= RegionBSPTree1S[", str);
450 }
451
452 private static void checkClassify(final HyperplaneSubset<Point2S> sub, final RegionLocation loc, final Point2S... pts) {
453 for (final Point2S pt : pts) {
454 Assertions.assertEquals(loc, sub.classify(pt), "Unexpected location for point " + pt);
455 }
456 }
457
458 private static void checkArc(final GreatArc arc, final Point2S start, final Point2S end) {
459 SphericalTestUtils.assertPointsEq(start, arc.getStartPoint(), TEST_EPS);
460 SphericalTestUtils.assertPointsEq(end, arc.getEndPoint(), TEST_EPS);
461 }
462 }