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.oned;
18  
19  import java.util.List;
20  
21  import org.apache.commons.geometry.core.Region;
22  import org.apache.commons.geometry.core.RegionLocation;
23  import org.apache.commons.geometry.core.partitioning.Split;
24  import org.apache.commons.geometry.core.partitioning.SplitLocation;
25  import org.apache.commons.geometry.euclidean.twod.Vector2D;
26  import org.apache.commons.numbers.angle.Angle;
27  import org.apache.commons.numbers.core.Precision;
28  import org.junit.jupiter.api.Assertions;
29  import org.junit.jupiter.api.Test;
30  
31  class RegionBSPTree1STest {
32  
33      private static final double TEST_EPS = 1e-10;
34  
35      private static final Precision.DoubleEquivalence TEST_PRECISION =
36              Precision.doubleEquivalenceOfEpsilon(TEST_EPS);
37  
38      private static final Transform1S HALF_PI_PLUS_AZ = Transform1S.createRotation(Angle.PI_OVER_TWO);
39  
40      private static final Transform1S PI_MINUS_AZ = Transform1S.createNegation().rotate(Math.PI);
41  
42      @Test
43      void testConstructor_default() {
44          // act
45          final RegionBSPTree1S tree = new RegionBSPTree1S();
46  
47          // assert
48          Assertions.assertFalse(tree.isFull());
49          Assertions.assertTrue(tree.isEmpty());
50  
51          Assertions.assertEquals(0, tree.getSize(), TEST_EPS);
52          Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
53          Assertions.assertNull(tree.getCentroid());
54      }
55  
56      @Test
57      void testConstructor_true() {
58          // act
59          final RegionBSPTree1S tree = new RegionBSPTree1S(true);
60  
61          // assert
62          Assertions.assertTrue(tree.isFull());
63          Assertions.assertFalse(tree.isEmpty());
64  
65          Assertions.assertEquals(Angle.TWO_PI, tree.getSize(), TEST_EPS);
66          Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
67          Assertions.assertNull(tree.getCentroid());
68      }
69  
70      @Test
71      void testConstructor_false() {
72          // act
73          final RegionBSPTree1S tree = new RegionBSPTree1S(false);
74  
75          // assert
76          Assertions.assertFalse(tree.isFull());
77          Assertions.assertTrue(tree.isEmpty());
78  
79          Assertions.assertEquals(0, tree.getSize(), TEST_EPS);
80          Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
81          Assertions.assertNull(tree.getCentroid());
82      }
83  
84      @Test
85      void testFull() {
86          // act
87          final RegionBSPTree1S tree = RegionBSPTree1S.full();
88  
89          // assert
90          Assertions.assertTrue(tree.isFull());
91          Assertions.assertFalse(tree.isEmpty());
92  
93          Assertions.assertEquals(Angle.TWO_PI, tree.getSize(), TEST_EPS);
94          Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
95          Assertions.assertNull(tree.getCentroid());
96      }
97  
98      @Test
99      void testEmpty() {
100         // act
101         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
102 
103         // assert
104         Assertions.assertFalse(tree.isFull());
105         Assertions.assertTrue(tree.isEmpty());
106 
107         Assertions.assertEquals(0, tree.getSize(), TEST_EPS);
108         Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
109         Assertions.assertNull(tree.getCentroid());
110     }
111 
112     @Test
113     void testCopy() {
114         // arrange
115         final RegionBSPTree1S orig = RegionBSPTree1S.fromInterval(AngularInterval.of(0, Math.PI, TEST_PRECISION));
116 
117         // act
118         final RegionBSPTree1S copy = orig.copy();
119 
120         // assert
121         Assertions.assertNotSame(orig, copy);
122 
123         orig.setEmpty();
124 
125         checkSingleInterval(copy, 0, Math.PI);
126     }
127 
128     @Test
129     void testFromInterval_full() {
130         // act
131         final RegionBSPTree1S tree = RegionBSPTree1S.fromInterval(AngularInterval.full());
132 
133         // assert
134         Assertions.assertTrue(tree.isFull());
135     }
136 
137     @Test
138     void testFromInterval_nonFull() {
139         for (double theta = 0.0; theta <= Angle.TWO_PI; theta += 0.2) {
140             // arrange
141             final double max = theta + Angle.PI_OVER_TWO;
142 
143             // act
144             final RegionBSPTree1S tree = RegionBSPTree1S.fromInterval(AngularInterval.of(theta, max, TEST_PRECISION));
145 
146             checkSingleInterval(tree, theta, max);
147 
148             Assertions.assertEquals(Angle.PI_OVER_TWO, tree.getSize(), TEST_EPS);
149             Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
150             Assertions.assertEquals(Angle.Rad.WITHIN_0_AND_2PI.applyAsDouble(theta + (0.25 * Math.PI)),
151                     tree.getCentroid().getNormalizedAzimuth(), TEST_EPS);
152         }
153     }
154 
155     @Test
156     void testClassify_full() {
157         // arrange
158         final RegionBSPTree1S tree = RegionBSPTree1S.full();
159 
160         // act/assert
161         for (double az = -Angle.TWO_PI; az <= 2 * Angle.TWO_PI; az += 0.2) {
162             checkClassify(tree, RegionLocation.INSIDE, az);
163         }
164     }
165 
166     @Test
167     void testClassify_empty() {
168         // arrange
169         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
170 
171         // act/assert
172         for (double az = -Angle.TWO_PI; az <= 2 * Angle.TWO_PI; az += 0.2) {
173             checkClassify(tree, RegionLocation.OUTSIDE, az);
174         }
175     }
176 
177     @Test
178     void testClassify() {
179         // arrange
180         final RegionBSPTree1S tree = RegionBSPTree1S.fromInterval(
181                 AngularInterval.of(-Angle.PI_OVER_TWO, Angle.PI_OVER_TWO, TEST_PRECISION));
182 
183         // act/assert
184         checkClassify(tree, RegionLocation.BOUNDARY,
185                 -Angle.PI_OVER_TWO, Angle.PI_OVER_TWO,
186                 -Angle.PI_OVER_TWO - Angle.TWO_PI, Angle.PI_OVER_TWO + Angle.TWO_PI);
187         checkClassify(tree, RegionLocation.INSIDE,
188                 0.0, 0.5, -0.5,
189                 Angle.TWO_PI, 0.5 + Angle.TWO_PI, -0.5 - Angle.TWO_PI);
190         checkClassify(tree, RegionLocation.OUTSIDE,
191                 Math.PI, Math.PI + 0.5, Math.PI - 0.5,
192                 Math.PI + Angle.TWO_PI, Math.PI + 0.5 + Angle.TWO_PI,
193                 Math.PI - 0.5 + Angle.TWO_PI);
194     }
195 
196     @Test
197     void testToIntervals_full() {
198         // arrange
199         final RegionBSPTree1S tree = RegionBSPTree1S.full();
200 
201         // act
202         final List<AngularInterval> intervals = tree.toIntervals();
203 
204         // assert
205         Assertions.assertEquals(1, intervals.size());
206 
207         final AngularInterval interval = intervals.get(0);
208         Assertions.assertTrue(interval.isFull());
209     }
210 
211     @Test
212     void testToIntervals_empty() {
213         // arrange
214         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
215 
216         // act
217         final List<AngularInterval> intervals = tree.toIntervals();
218 
219         // assert
220         Assertions.assertEquals(0, intervals.size());
221     }
222 
223     @Test
224     void testToIntervals_singleCut() {
225         // arrange
226         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
227 
228         for (double theta = 0; theta <= Angle.TWO_PI; theta += 0.2) {
229             // act/assert
230             tree.setEmpty();
231             tree.getRoot().cut(CutAngles.createPositiveFacing(theta, TEST_PRECISION));
232 
233             checkSingleInterval(tree, 0, theta);
234 
235             tree.setEmpty();
236             tree.getRoot().cut(CutAngles.createNegativeFacing(theta, TEST_PRECISION));
237 
238             checkSingleInterval(tree, theta, Angle.TWO_PI);
239         }
240     }
241 
242     @Test
243     void testToIntervals_wrapAround_joinedIntervalsOnPositiveSide() {
244         // arrange
245         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
246         tree.add(AngularInterval.of(0.25 * Math.PI, Angle.PI_OVER_TWO, TEST_PRECISION));
247         tree.add(AngularInterval.of(1.5 * Math.PI, 0.25 * Math.PI, TEST_PRECISION));
248 
249         // act
250         final List<AngularInterval> intervals = tree.toIntervals();
251 
252         // assert
253         Assertions.assertEquals(1, intervals.size());
254 
255         checkInterval(intervals.get(0), 1.5 * Math.PI, Angle.PI_OVER_TWO);
256     }
257 
258     @Test
259     void testToIntervals_wrapAround_joinedIntervalsOnNegativeSide() {
260         // arrange
261         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
262         tree.add(AngularInterval.of(1.75 * Math.PI, Angle.PI_OVER_TWO, TEST_PRECISION));
263         tree.add(AngularInterval.of(1.5 * Math.PI, 1.75 * Math.PI, TEST_PRECISION));
264 
265         // act
266         final List<AngularInterval> intervals = tree.toIntervals();
267 
268         // assert
269         Assertions.assertEquals(1, intervals.size());
270 
271         checkInterval(intervals.get(0), 1.5 * Math.PI, Angle.PI_OVER_TWO);
272     }
273 
274     @Test
275     void testToIntervals_multipleIntervals() {
276         // arrange
277         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
278         tree.add(AngularInterval.of(-Angle.PI_OVER_TWO, Angle.PI_OVER_TWO, TEST_PRECISION));
279         tree.add(AngularInterval.of(Math.PI - 0.5, Math.PI, TEST_PRECISION));
280         tree.add(AngularInterval.of(Math.PI, Math.PI + 0.5, TEST_PRECISION));
281 
282         // act
283         final List<AngularInterval> intervals = tree.toIntervals();
284 
285         // assert
286         Assertions.assertEquals(2, intervals.size());
287 
288         checkInterval(intervals.get(0), Math.PI - 0.5, Math.PI + 0.5);
289         checkInterval(intervals.get(1), -Angle.PI_OVER_TWO, Angle.PI_OVER_TWO);
290     }
291 
292     @Test
293     void testToIntervals_multipleIntervals_complement() {
294         // arrange
295         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
296         tree.add(AngularInterval.of(-Angle.PI_OVER_TWO, Angle.PI_OVER_TWO, TEST_PRECISION));
297         tree.add(AngularInterval.of(Math.PI - 0.5, Math.PI, TEST_PRECISION));
298         tree.add(AngularInterval.of(Math.PI, Math.PI + 0.5, TEST_PRECISION));
299 
300         tree.complement();
301 
302         // act
303         final List<AngularInterval> intervals = tree.toIntervals();
304 
305         // assert
306         Assertions.assertEquals(2, intervals.size());
307 
308         checkInterval(intervals.get(0), Angle.PI_OVER_TWO, Math.PI - 0.5);
309         checkInterval(intervals.get(1), Math.PI + 0.5, -Angle.PI_OVER_TWO);
310     }
311 
312     @Test
313     void testSplit_empty() {
314         // arrange
315         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
316 
317         // act/assert
318         Assertions.assertEquals(SplitLocation.NEITHER,
319                 tree.split(CutAngles.createPositiveFacing(0, TEST_PRECISION)).getLocation());
320         Assertions.assertEquals(SplitLocation.NEITHER,
321                 tree.split(CutAngles.createNegativeFacing(Angle.PI_OVER_TWO, TEST_PRECISION)).getLocation());
322         Assertions.assertEquals(SplitLocation.NEITHER,
323                 tree.split(CutAngles.createPositiveFacing(Math.PI, TEST_PRECISION)).getLocation());
324         Assertions.assertEquals(SplitLocation.NEITHER,
325                 tree.split(CutAngles.createNegativeFacing(-Angle.PI_OVER_TWO, TEST_PRECISION)).getLocation());
326         Assertions.assertEquals(SplitLocation.NEITHER,
327                 tree.split(CutAngles.createPositiveFacing(Angle.TWO_PI, TEST_PRECISION)).getLocation());
328     }
329 
330     @Test
331     void testSplit_full() {
332         // arrange
333         final RegionBSPTree1S tree = RegionBSPTree1S.full();
334 
335         // act/assert
336         checkSimpleSplit(
337             tree.split(CutAngles.createPositiveFacing(1e-6, TEST_PRECISION)),
338             AngularInterval.of(0, 1e-6, TEST_PRECISION),
339             AngularInterval.of(1e-6, Angle.TWO_PI, TEST_PRECISION)
340         );
341         checkSimpleSplit(
342             tree.split(CutAngles.createNegativeFacing(Angle.PI_OVER_TWO, TEST_PRECISION)),
343             AngularInterval.of(Angle.PI_OVER_TWO, Angle.TWO_PI, TEST_PRECISION),
344             AngularInterval.of(0, Angle.PI_OVER_TWO, TEST_PRECISION)
345         );
346         checkSimpleSplit(
347             tree.split(CutAngles.createPositiveFacing(Math.PI, TEST_PRECISION)),
348             AngularInterval.of(0, Math.PI, TEST_PRECISION),
349             AngularInterval.of(Math.PI, Angle.TWO_PI, TEST_PRECISION)
350         );
351         checkSimpleSplit(
352             tree.split(CutAngles.createNegativeFacing(-Angle.PI_OVER_TWO, TEST_PRECISION)),
353             AngularInterval.of(-Angle.PI_OVER_TWO, Angle.TWO_PI, TEST_PRECISION),
354             AngularInterval.of(0, -Angle.PI_OVER_TWO, TEST_PRECISION)
355         );
356         checkSimpleSplit(
357             tree.split(CutAngles.createPositiveFacing(Angle.TWO_PI - 1e-6, TEST_PRECISION)),
358             AngularInterval.of(0, Angle.TWO_PI - 1e-6, TEST_PRECISION),
359             AngularInterval.of(Angle.TWO_PI - 1e-6, Angle.TWO_PI, TEST_PRECISION)
360         );
361     }
362 
363     @Test
364     void testSplit_full_cutEquivalentToZero() {
365         // arrange
366         final RegionBSPTree1S tree = RegionBSPTree1S.full();
367 
368         final AngularInterval twoPi = AngularInterval.of(0, Angle.TWO_PI, TEST_PRECISION);
369 
370         // act/assert
371         checkSimpleSplit(
372             tree.split(CutAngles.createPositiveFacing(0, TEST_PRECISION)),
373             null,
374             twoPi
375         );
376         checkSimpleSplit(
377             tree.split(CutAngles.createNegativeFacing(0, TEST_PRECISION)),
378             twoPi,
379             null
380         );
381 
382         checkSimpleSplit(
383             tree.split(CutAngles.createPositiveFacing(Angle.TWO_PI - 1e-18, TEST_PRECISION)),
384             null,
385             twoPi
386         );
387         checkSimpleSplit(
388             tree.split(CutAngles.createNegativeFacing(Angle.TWO_PI - 1e-18, TEST_PRECISION)),
389             twoPi,
390             null
391         );
392     }
393 
394     @Test
395     void testSplit_singleInterval() {
396         // arrange
397         final AngularInterval interval = AngularInterval.of(Angle.PI_OVER_TWO, -Angle.PI_OVER_TWO, TEST_PRECISION);
398         final RegionBSPTree1S tree = interval.toTree();
399 
400         // act
401         checkSimpleSplit(
402             tree.split(CutAngles.createNegativeFacing(0, TEST_PRECISION)),
403             interval,
404             null
405         );
406         checkSimpleSplit(
407             tree.split(CutAngles.createNegativeFacing(-Angle.TWO_PI, TEST_PRECISION)),
408             interval,
409             null
410         );
411 
412         checkSimpleSplit(
413             tree.split(CutAngles.createPositiveFacing(Angle.TWO_PI + Angle.PI_OVER_TWO, TEST_PRECISION)),
414             null,
415             interval
416         );
417         checkSimpleSplit(
418             tree.split(CutAngles.createPositiveFacing(1.5 * Math.PI, TEST_PRECISION)),
419             interval,
420             null
421         );
422 
423         checkSimpleSplit(
424             tree.split(CutAngles.createNegativeFacing(Math.PI, TEST_PRECISION)),
425             AngularInterval.of(Math.PI, -Angle.PI_OVER_TWO, TEST_PRECISION),
426             AngularInterval.of(Angle.PI_OVER_TWO, Math.PI, TEST_PRECISION)
427         );
428     }
429 
430     @Test
431     void testSplit_singleIntervalSplitIntoTwoIntervalsOnSameSide() {
432         // arrange
433         final RegionBSPTree1S tree = AngularInterval.of(-Angle.PI_OVER_TWO, Angle.PI_OVER_TWO, TEST_PRECISION).toTree();
434 
435         final CutAngle cut = CutAngles.createPositiveFacing(0, TEST_PRECISION);
436 
437         // act
438         final Split<RegionBSPTree1S> split = tree.split(cut);
439 
440         // assert
441         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
442 
443         final RegionBSPTree1S minus = split.getMinus();
444         Assertions.assertNull(minus);
445 
446         final RegionBSPTree1S plus = split.getPlus();
447         final List<AngularInterval> plusIntervals = plus.toIntervals();
448         Assertions.assertEquals(1, plusIntervals.size());
449         checkInterval(plusIntervals.get(0), -Angle.PI_OVER_TWO, Angle.PI_OVER_TWO);
450     }
451 
452     @Test
453     void testSplit_multipleRegions() {
454         // arrange
455         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
456         tree.add(AngularInterval.of(Angle.TWO_PI - 1, Angle.PI_OVER_TWO, TEST_PRECISION));
457         tree.add(AngularInterval.of(Math.PI, -Angle.PI_OVER_TWO, TEST_PRECISION));
458 
459         final CutAngle cut = CutAngles.createNegativeFacing(1, TEST_PRECISION);
460 
461         // act
462         final Split<RegionBSPTree1S> split = tree.split(cut);
463 
464         // assert
465         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
466 
467         final RegionBSPTree1S minus = split.getMinus();
468         final List<AngularInterval> minusIntervals = minus.toIntervals();
469         Assertions.assertEquals(3, minusIntervals.size());
470         checkInterval(minusIntervals.get(0), 1, Angle.PI_OVER_TWO);
471         checkInterval(minusIntervals.get(1), Math.PI, -Angle.PI_OVER_TWO);
472         checkInterval(minusIntervals.get(2), Angle.TWO_PI - 1, 0);
473 
474         final RegionBSPTree1S plus = split.getPlus();
475         final List<AngularInterval> plusIntervals = plus.toIntervals();
476         Assertions.assertEquals(1, plusIntervals.size());
477         checkInterval(plusIntervals.get(0), 0, 1);
478     }
479 
480     @Test
481     void testSplitDiameter_full() {
482         // arrange
483         final RegionBSPTree1S full = RegionBSPTree1S.full();
484         final CutAngle splitter = CutAngles.createPositiveFacing(Angle.PI_OVER_TWO, TEST_PRECISION);
485 
486         // act
487         final Split<RegionBSPTree1S> split = full.splitDiameter(splitter);
488 
489         // assert
490         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
491 
492         final RegionBSPTree1S minus = split.getMinus();
493         final List<AngularInterval> minusIntervals = minus.toIntervals();
494         Assertions.assertEquals(1, minusIntervals.size());
495         checkInterval(minusIntervals.get(0), 1.5 * Math.PI, 2.5 * Math.PI);
496 
497         final RegionBSPTree1S plus = split.getPlus();
498         final List<AngularInterval> plusIntervals = plus.toIntervals();
499         Assertions.assertEquals(1, plusIntervals.size());
500         checkInterval(plusIntervals.get(0), Angle.PI_OVER_TWO, 1.5 * Math.PI);
501     }
502 
503     @Test
504     void testSplitDiameter_empty() {
505         // arrange
506         final RegionBSPTree1S empty = RegionBSPTree1S.empty();
507         final CutAngle splitter = CutAngles.createPositiveFacing(Angle.PI_OVER_TWO, TEST_PRECISION);
508 
509         // act
510         final Split<RegionBSPTree1S> split = empty.splitDiameter(splitter);
511 
512         // assert
513         Assertions.assertEquals(SplitLocation.NEITHER, split.getLocation());
514 
515         final RegionBSPTree1S minus = split.getMinus();
516         Assertions.assertNull(minus);
517 
518         final RegionBSPTree1S plus = split.getPlus();
519         Assertions.assertNull(plus);
520     }
521 
522     @Test
523     void testSplitDiameter_minus_zeroOnMinusSide() {
524         // arrange
525         final RegionBSPTree1S tree = AngularInterval.of(0, 1, TEST_PRECISION).toTree();
526         final CutAngle splitter = CutAngles.createPositiveFacing(1, TEST_PRECISION);
527 
528         // act
529         final Split<RegionBSPTree1S> split = tree.splitDiameter(splitter);
530 
531         // assert
532         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
533 
534         final RegionBSPTree1S minus = split.getMinus();
535         final List<AngularInterval> minusIntervals = minus.toIntervals();
536         Assertions.assertEquals(1, minusIntervals.size());
537         checkInterval(minusIntervals.get(0), 0, 1);
538 
539         final RegionBSPTree1S plus = split.getPlus();
540         Assertions.assertNull(plus);
541     }
542 
543     @Test
544     void testSplitDiameter_minus_zeroOnPlusSide() {
545         // arrange
546         final RegionBSPTree1S tree = AngularInterval.of(1, 2, TEST_PRECISION).toTree();
547         final CutAngle splitter = CutAngles.createNegativeFacing(0, TEST_PRECISION);
548 
549         // act
550         final Split<RegionBSPTree1S> split = tree.splitDiameter(splitter);
551 
552         // assert
553         Assertions.assertEquals(SplitLocation.MINUS, split.getLocation());
554 
555         final RegionBSPTree1S minus = split.getMinus();
556         final List<AngularInterval> minusIntervals = minus.toIntervals();
557         Assertions.assertEquals(1, minusIntervals.size());
558         checkInterval(minusIntervals.get(0), 1, 2);
559 
560         final RegionBSPTree1S plus = split.getPlus();
561         Assertions.assertNull(plus);
562     }
563 
564     @Test
565     void testSplitDiameter_plus_zeroOnMinusSide() {
566         // arrange
567         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
568         tree.add(AngularInterval.of(1, 1.1, TEST_PRECISION));
569         tree.add(AngularInterval.of(2, 2.1, TEST_PRECISION));
570 
571         final CutAngle splitter = CutAngles.createPositiveFacing(1, TEST_PRECISION);
572 
573         // act
574         final Split<RegionBSPTree1S> split = tree.splitDiameter(splitter);
575 
576         // assert
577         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
578 
579         final RegionBSPTree1S minus = split.getMinus();
580         Assertions.assertNull(minus);
581 
582         final RegionBSPTree1S plus = split.getPlus();
583         final List<AngularInterval> plusIntervals = plus.toIntervals();
584         Assertions.assertEquals(2, plusIntervals.size());
585         checkInterval(plusIntervals.get(0), 1, 1.1);
586         checkInterval(plusIntervals.get(1), 2, 2.1);
587     }
588 
589     @Test
590     void testSplitDiameter_plus_zeroOnPlusSide() {
591         // arrange
592         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
593         tree.add(AngularInterval.of(1, 1.1, TEST_PRECISION));
594         tree.add(AngularInterval.of(2, 2.1, TEST_PRECISION));
595 
596         final CutAngle splitter = CutAngles.createNegativeFacing(Math.PI - 1, TEST_PRECISION);
597 
598         // act
599         final Split<RegionBSPTree1S> split = tree.splitDiameter(splitter);
600 
601         // assert
602         Assertions.assertEquals(SplitLocation.PLUS, split.getLocation());
603 
604         final RegionBSPTree1S minus = split.getMinus();
605         Assertions.assertNull(minus);
606 
607         final RegionBSPTree1S plus = split.getPlus();
608         final List<AngularInterval> plusIntervals = plus.toIntervals();
609         Assertions.assertEquals(2, plusIntervals.size());
610         checkInterval(plusIntervals.get(0), 1, 1.1);
611         checkInterval(plusIntervals.get(1), 2, 2.1);
612     }
613 
614     @Test
615     void testSplitDiameter_both_zeroOnMinusSide() {
616         // arrange
617         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
618         tree.add(AngularInterval.of(1, 1.1, TEST_PRECISION));
619         tree.add(AngularInterval.of(2, 3, TEST_PRECISION));
620 
621         final CutAngle splitter = CutAngles.createPositiveFacing(2.5, TEST_PRECISION);
622 
623         // act
624         final Split<RegionBSPTree1S> split = tree.splitDiameter(splitter);
625 
626         // assert
627         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
628 
629         final RegionBSPTree1S minus = split.getMinus();
630         final List<AngularInterval> plusIntervals = minus.toIntervals();
631         Assertions.assertEquals(2, plusIntervals.size());
632         checkInterval(plusIntervals.get(0), 1, 1.1);
633         checkInterval(plusIntervals.get(1), 2, 2.5);
634 
635         final RegionBSPTree1S plus = split.getPlus();
636         final List<AngularInterval> minusIntervals = plus.toIntervals();
637         Assertions.assertEquals(1, minusIntervals.size());
638         checkInterval(minusIntervals.get(0), 2.5, 3);
639     }
640 
641     @Test
642     void testSplitDiameter_both_zeroOnPlusSide() {
643         // arrange
644         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
645         tree.add(AngularInterval.of(1, 1.1, TEST_PRECISION));
646         tree.add(AngularInterval.of(2, 3, TEST_PRECISION));
647 
648         final CutAngle splitter = CutAngles.createNegativeFacing(2.5, TEST_PRECISION);
649 
650         // act
651         final Split<RegionBSPTree1S> split = tree.splitDiameter(splitter);
652 
653         // assert
654         Assertions.assertEquals(SplitLocation.BOTH, split.getLocation());
655 
656         final RegionBSPTree1S minus = split.getMinus();
657         final List<AngularInterval> minusIntervals = minus.toIntervals();
658         Assertions.assertEquals(1, minusIntervals.size());
659         checkInterval(minusIntervals.get(0), 2.5, 3);
660 
661         final RegionBSPTree1S plus = split.getPlus();
662         final List<AngularInterval> plusIntervals = plus.toIntervals();
663         Assertions.assertEquals(2, plusIntervals.size());
664         checkInterval(plusIntervals.get(0), 1, 1.1);
665         checkInterval(plusIntervals.get(1), 2, 2.5);
666     }
667 
668     @Test
669     void testRegionProperties_singleInterval_wrapsZero() {
670         // arrange
671         final RegionBSPTree1S tree = AngularInterval.of(-Angle.PI_OVER_TWO, Math.PI,
672                 TEST_PRECISION).toTree();
673 
674         // act/assert
675         Assertions.assertEquals(1.5 * Math.PI, tree.getSize(), TEST_EPS);
676         Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
677         Assertions.assertEquals(0.25 * Math.PI, tree.getCentroid().getAzimuth(), TEST_EPS);
678     }
679 
680     @Test
681     void testRegionProperties_singleInterval_doesNotWrap() {
682         // arrange
683         final RegionBSPTree1S tree = AngularInterval.of(Angle.PI_OVER_TWO, Angle.TWO_PI,
684                 TEST_PRECISION).toTree();
685 
686         // act/assert
687         Assertions.assertEquals(1.5 * Math.PI, tree.getSize(), TEST_EPS);
688         Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
689         Assertions.assertEquals(1.25 * Math.PI, tree.getCentroid().getAzimuth(), TEST_EPS);
690     }
691 
692     @Test
693     void testRegionProperties_multipleIntervals_sameSize() {
694         // arrange
695         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
696         tree.add(AngularInterval.of(0, 0.1, TEST_PRECISION));
697         tree.add(AngularInterval.of(0.2, 0.3, TEST_PRECISION));
698 
699         // act/assert
700         Assertions.assertEquals(0.2, tree.getSize(), TEST_EPS);
701         Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
702         Assertions.assertEquals(0.15, tree.getCentroid().getAzimuth(), TEST_EPS);
703     }
704 
705     @Test
706     void testRegionProperties_multipleIntervals_differentSizes() {
707         // arrange
708         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
709         tree.add(AngularInterval.of(0, 0.2, TEST_PRECISION));
710         tree.add(AngularInterval.of(0.3, 0.7, TEST_PRECISION));
711 
712         // act/assert
713         Assertions.assertEquals(0.6, tree.getSize(), TEST_EPS);
714         Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
715 
716         final Vector2D centroidVector = Point1S.of(0.1).getVector().withNorm(0.2)
717                 .add(Point1S.of(0.5).getVector().withNorm(0.4));
718         Assertions.assertEquals(Point1S.from(centroidVector).getAzimuth(), tree.getCentroid().getAzimuth(), TEST_EPS);
719     }
720 
721     @Test
722     void testRegionProperties_equalAndOppositeIntervals() {
723         // arrange
724         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
725         tree.add(AngularInterval.of(-1, 1, TEST_PRECISION));
726         tree.add(AngularInterval.of(Math.PI - 1, Math.PI + 1, TEST_PRECISION));
727 
728         // act/assert
729         Assertions.assertEquals(4, tree.getSize(), TEST_EPS);
730         Assertions.assertEquals(0, tree.getBoundarySize(), TEST_EPS);
731         Assertions.assertNull(tree.getCentroid()); // no unique centroid exists
732     }
733 
734     @Test
735     void testTransform_fullAndEmpty() {
736         // arrange
737         final RegionBSPTree1S full = RegionBSPTree1S.full();
738         final RegionBSPTree1S empty = RegionBSPTree1S.empty();
739 
740         // act
741         full.transform(PI_MINUS_AZ);
742         empty.transform(HALF_PI_PLUS_AZ);
743 
744         // assert
745         Assertions.assertTrue(full.isFull());
746         Assertions.assertFalse(full.isEmpty());
747 
748         Assertions.assertFalse(empty.isFull());
749         Assertions.assertTrue(empty.isEmpty());
750     }
751 
752     @Test
753     void testTransform_halfPiPlusAz() {
754         // arrange
755         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
756         tree.add(AngularInterval.of(-1, 1, TEST_PRECISION));
757         tree.add(AngularInterval.of(2, 3, TEST_PRECISION));
758 
759         // act
760         tree.transform(HALF_PI_PLUS_AZ);
761 
762         // assert
763         Assertions.assertEquals(3, tree.getSize(), TEST_EPS);
764 
765         final List<AngularInterval> intervals = tree.toIntervals();
766 
767         Assertions.assertEquals(2, intervals.size());
768         checkInterval(intervals.get(0), Angle.PI_OVER_TWO - 1, Angle.PI_OVER_TWO + 1);
769         checkInterval(intervals.get(1), Angle.PI_OVER_TWO + 2, Angle.PI_OVER_TWO + 3);
770     }
771 
772     @Test
773     void testTransform_piMinusAz() {
774         // arrange
775         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
776         tree.add(AngularInterval.of(-1, 1, TEST_PRECISION));
777         tree.add(AngularInterval.of(2, 3, TEST_PRECISION));
778 
779         // act
780         tree.transform(PI_MINUS_AZ);
781 
782         // assert
783         Assertions.assertEquals(3, tree.getSize(), TEST_EPS);
784 
785         final List<AngularInterval> intervals = tree.toIntervals();
786 
787         Assertions.assertEquals(2, intervals.size());
788         checkInterval(intervals.get(0), Math.PI - 3, Math.PI - 2);
789         checkInterval(intervals.get(1), Math.PI - 1, Math.PI + 1);
790     }
791 
792     @Test
793     void testProject_fullAndEmpty() {
794         // arrange
795         final RegionBSPTree1S full = RegionBSPTree1S.full();
796         final RegionBSPTree1S empty = RegionBSPTree1S.empty();
797 
798         // act/assert
799         Assertions.assertNull(full.project(Point1S.ZERO));
800         Assertions.assertNull(full.project(Point1S.PI));
801 
802         Assertions.assertNull(empty.project(Point1S.ZERO));
803         Assertions.assertNull(empty.project(Point1S.PI));
804     }
805 
806     @Test
807     void testProject_withIntervals() {
808         // arrange
809         final RegionBSPTree1S tree = RegionBSPTree1S.empty();
810         tree.add(AngularInterval.of(-Angle.PI_OVER_TWO, Angle.PI_OVER_TWO, TEST_PRECISION));
811         tree.add(AngularInterval.of(Math.PI - 1, Math.PI + 1, TEST_PRECISION));
812 
813         // act/assert
814         Assertions.assertEquals(-Angle.PI_OVER_TWO,
815                 tree.project(Point1S.of(-Angle.PI_OVER_TWO - 0.1)).getAzimuth(), TEST_EPS);
816         Assertions.assertEquals(-Angle.PI_OVER_TWO,
817                 tree.project(Point1S.of(-Angle.PI_OVER_TWO)).getAzimuth(), TEST_EPS);
818         Assertions.assertEquals(-Angle.PI_OVER_TWO,
819                 tree.project(Point1S.of(-Angle.PI_OVER_TWO + 0.1)).getAzimuth(), TEST_EPS);
820 
821         Assertions.assertEquals(-Angle.PI_OVER_TWO, tree.project(Point1S.of(-0.1)).getAzimuth(), TEST_EPS);
822         Assertions.assertEquals(Angle.PI_OVER_TWO, tree.project(Point1S.ZERO).getAzimuth(), TEST_EPS);
823         Assertions.assertEquals(Angle.PI_OVER_TWO, tree.project(Point1S.of(0.1)).getAzimuth(), TEST_EPS);
824 
825         Assertions.assertEquals(Math.PI - 1,
826                 tree.project(Point1S.of(Math.PI - 0.5)).getAzimuth(), TEST_EPS);
827         Assertions.assertEquals(Math.PI + 1,
828                 tree.project(Point1S.of(Math.PI + 0.5)).getAzimuth(), TEST_EPS);
829     }
830 
831     @Test
832     void testProject_equidistant() {
833         // arrange
834         final RegionBSPTree1S tree = AngularInterval.of(1, 2, TEST_PRECISION).toTree();
835         final RegionBSPTree1S treeComplement = tree.copy();
836         treeComplement.complement();
837 
838         // act/assert
839         Assertions.assertEquals(1, tree.project(Point1S.of(1.5)).getAzimuth(), TEST_EPS);
840         Assertions.assertEquals(1, treeComplement.project(Point1S.of(1.5)).getAzimuth(), TEST_EPS);
841     }
842 
843     @Test
844     void testProject_intervalAroundZero_closerOnMinSide() {
845         // arrange
846         final double start = -1;
847         final double end = 0.5;
848         final RegionBSPTree1S tree = AngularInterval.of(start, end, TEST_PRECISION).toTree();
849 
850         // act/assert
851         Assertions.assertEquals(end, tree.project(Point1S.of(-1.5 * Math.PI)).getAzimuth(), TEST_EPS);
852         Assertions.assertEquals(start, tree.project(Point1S.of(-Math.PI)).getAzimuth(), TEST_EPS);
853         Assertions.assertEquals(start, tree.project(Point1S.of(-0.5 * Math.PI)).getAzimuth(), TEST_EPS);
854         Assertions.assertEquals(start, tree.project(Point1S.of(-1)).getAzimuth(), TEST_EPS);
855         Assertions.assertEquals(start, tree.project(Point1S.of(-0.5)).getAzimuth(), TEST_EPS);
856         Assertions.assertEquals(end, tree.project(Point1S.of(-0.25)).getAzimuth(), TEST_EPS);
857         Assertions.assertEquals(end, tree.project(Point1S.of(-0.1)).getAzimuth(), TEST_EPS);
858         Assertions.assertEquals(end, tree.project(Point1S.ZERO).getAzimuth(), TEST_EPS);
859         Assertions.assertEquals(end, tree.project(Point1S.of(0.1)).getAzimuth(), TEST_EPS);
860         Assertions.assertEquals(end, tree.project(Point1S.of(0.25)).getAzimuth(), TEST_EPS);
861         Assertions.assertEquals(end, tree.project(Point1S.of(0.5)).getAzimuth(), TEST_EPS);
862         Assertions.assertEquals(end, tree.project(Point1S.of(0.75)).getAzimuth(), TEST_EPS);
863     }
864 
865     @Test
866     void testProject_intervalAroundZero_closerOnMaxSide() {
867         // arrange
868         final double start = -0.5;
869         final double end = 1;
870         final RegionBSPTree1S tree = AngularInterval.of(start, end, TEST_PRECISION).toTree();
871 
872         // act/assert
873         Assertions.assertEquals(end, tree.project(Point1S.of(-1.5 * Math.PI)).getAzimuth(), TEST_EPS);
874         Assertions.assertEquals(end, tree.project(Point1S.of(-Math.PI)).getAzimuth(), TEST_EPS);
875         Assertions.assertEquals(start, tree.project(Point1S.of(-0.5 * Math.PI)).getAzimuth(), TEST_EPS);
876         Assertions.assertEquals(start, tree.project(Point1S.of(-1)).getAzimuth(), TEST_EPS);
877         Assertions.assertEquals(start, tree.project(Point1S.of(-0.5)).getAzimuth(), TEST_EPS);
878         Assertions.assertEquals(start, tree.project(Point1S.of(-0.25)).getAzimuth(), TEST_EPS);
879         Assertions.assertEquals(start, tree.project(Point1S.of(-0.1)).getAzimuth(), TEST_EPS);
880         Assertions.assertEquals(start, tree.project(Point1S.ZERO).getAzimuth(), TEST_EPS);
881         Assertions.assertEquals(start, tree.project(Point1S.of(0.1)).getAzimuth(), TEST_EPS);
882         Assertions.assertEquals(end, tree.project(Point1S.of(0.25)).getAzimuth(), TEST_EPS);
883         Assertions.assertEquals(end, tree.project(Point1S.of(0.5)).getAzimuth(), TEST_EPS);
884         Assertions.assertEquals(end, tree.project(Point1S.of(0.75)).getAzimuth(), TEST_EPS);
885     }
886 
887     private static void checkSimpleSplit(final Split<RegionBSPTree1S> split, final AngularInterval minusInterval,
888                                          final AngularInterval plusInterval) {
889 
890         final RegionBSPTree1S minus = split.getMinus();
891         if (minusInterval != null) {
892             Assertions.assertNotNull(minus, "Expected minus region to not be null");
893             checkSingleInterval(minus, minusInterval.getMin(), minusInterval.getMax());
894         } else {
895             Assertions.assertNull(minus, "Expected minus region to be null");
896         }
897 
898         final RegionBSPTree1S plus = split.getPlus();
899         if (plusInterval != null) {
900             Assertions.assertNotNull(plus, "Expected plus region to not be null");
901             checkSingleInterval(plus, plusInterval.getMin(), plusInterval.getMax());
902         } else {
903             Assertions.assertNull(plus, "Expected plus region to be null");
904         }
905     }
906 
907     private static void checkSingleInterval(final RegionBSPTree1S tree, final double min, final double max) {
908         final List<AngularInterval> intervals = tree.toIntervals();
909 
910         Assertions.assertEquals(1, intervals.size(), "Expected a single interval in the tree");
911 
912         checkInterval(intervals.get(0), min, max);
913     }
914 
915     private static void checkInterval(final AngularInterval interval, final double min, final double max) {
916         final double normalizedMin = Angle.Rad.WITHIN_0_AND_2PI.applyAsDouble(min);
917         final double normalizedMax = Angle.Rad.WITHIN_0_AND_2PI.applyAsDouble(max);
918 
919         if (TEST_PRECISION.eq(normalizedMin, normalizedMax)) {
920             Assertions.assertTrue(interval.isFull());
921         } else {
922             Assertions.assertEquals(normalizedMin,
923                     interval.getMinBoundary().getPoint().getNormalizedAzimuth(), TEST_EPS);
924             Assertions.assertEquals(normalizedMax,
925                     interval.getMaxBoundary().getPoint().getNormalizedAzimuth(), TEST_EPS);
926         }
927     }
928 
929     private static void checkClassify(final Region<Point1S> region, final RegionLocation loc, final double... pts) {
930         for (final double pt : pts) {
931             Assertions.assertEquals(loc, region.classify(Point1S.of(pt)), "Unexpected location for point " + pt);
932         }
933     }
934 }