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    *      https://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  
18  /*
19   * This is not the original file distributed by the Apache Software Foundation
20   * It has been modified by the Hipparchus project
21   */
22  package org.hipparchus.geometry.spherical.oned;
23  
24  import java.util.ArrayList;
25  import java.util.Iterator;
26  import java.util.List;
27  import java.util.NoSuchElementException;
28  
29  import org.hipparchus.exception.MathIllegalArgumentException;
30  import org.hipparchus.geometry.partitioning.BSPTree;
31  import org.hipparchus.geometry.partitioning.Region;
32  import org.hipparchus.geometry.partitioning.Region.Location;
33  import org.hipparchus.geometry.partitioning.RegionFactory;
34  import org.hipparchus.geometry.partitioning.Side;
35  import org.hipparchus.geometry.partitioning.SubHyperplane;
36  import org.hipparchus.util.FastMath;
37  import org.hipparchus.util.MathUtils;
38  import org.hipparchus.util.Precision;
39  import org.junit.Assert;
40  import org.junit.Test;
41  
42  public class ArcsSetTest {
43  
44      @Test
45      public void testArc() {
46          ArcsSet set = new ArcsSet(2.3, 5.7, 1.0e-10);
47          Assert.assertEquals(3.4, set.getSize(), 1.0e-10);
48          Assert.assertEquals(1.0e-10, set.getTolerance(), 1.0e-20);
49          Assert.assertEquals(Region.Location.BOUNDARY, set.checkPoint(new S1Point(2.3)));
50          Assert.assertEquals(Region.Location.BOUNDARY, set.checkPoint(new S1Point(5.7)));
51          Assert.assertEquals(Region.Location.OUTSIDE,  set.checkPoint(new S1Point(1.2)));
52          Assert.assertEquals(Region.Location.OUTSIDE,  set.checkPoint(new S1Point(8.5)));
53          Assert.assertEquals(Region.Location.INSIDE,   set.checkPoint(new S1Point(8.7)));
54          Assert.assertEquals(Region.Location.INSIDE,   set.checkPoint(new S1Point(3.0)));
55          Assert.assertEquals(1, set.asList().size());
56          Assert.assertEquals(2.3, set.asList().get(0).getInf(), 1.0e-10);
57          Assert.assertEquals(5.7, set.asList().get(0).getSup(), 1.0e-10);
58      }
59  
60      @Test
61      public void testWrapAround2PiArc() {
62          ArcsSet set = new ArcsSet(5.7 - MathUtils.TWO_PI, 2.3, 1.0e-10);
63          Assert.assertEquals(MathUtils.TWO_PI - 3.4, set.getSize(), 1.0e-10);
64          Assert.assertEquals(1.0e-10, set.getTolerance(), 1.0e-20);
65          Assert.assertEquals(Region.Location.BOUNDARY, set.checkPoint(new S1Point(2.3)));
66          Assert.assertEquals(Region.Location.BOUNDARY, set.checkPoint(new S1Point(5.7)));
67          Assert.assertEquals(Region.Location.INSIDE,   set.checkPoint(new S1Point(1.2)));
68          Assert.assertEquals(Region.Location.INSIDE,   set.checkPoint(new S1Point(8.5)));
69          Assert.assertEquals(Region.Location.OUTSIDE,  set.checkPoint(new S1Point(8.7)));
70          Assert.assertEquals(Region.Location.OUTSIDE,  set.checkPoint(new S1Point(3.0)));
71          Assert.assertEquals(1, set.asList().size());
72          Assert.assertEquals(5.7, set.asList().get(0).getInf(), 1.0e-10);
73          Assert.assertEquals(2.3 + MathUtils.TWO_PI, set.asList().get(0).getSup(), 1.0e-10);
74      }
75  
76      @Test
77      public void testSplitOver2Pi() {
78          ArcsSet set = new ArcsSet(1.0e-10);
79          Arc     arc = new Arc(1.5 * FastMath.PI, 2.5 * FastMath.PI, 1.0e-10);
80          ArcsSet.Split split = set.split(arc);
81          for (double alpha = 0.0; alpha <= MathUtils.TWO_PI; alpha += 0.01) {
82              S1Point p = new S1Point(alpha);
83              if (alpha < 0.5 * FastMath.PI || alpha > 1.5 * FastMath.PI) {
84                  Assert.assertEquals(Location.OUTSIDE, split.getPlus().checkPoint(p));
85                  Assert.assertEquals(Location.INSIDE,  split.getMinus().checkPoint(p));
86              } else {
87                  Assert.assertEquals(Location.INSIDE,  split.getPlus().checkPoint(p));
88                  Assert.assertEquals(Location.OUTSIDE, split.getMinus().checkPoint(p));
89              }
90          }
91      }
92  
93      @Test
94      public void testSplitAtEnd() {
95          ArcsSet set = new ArcsSet(1.0e-10);
96          Arc     arc = new Arc(FastMath.PI, MathUtils.TWO_PI, 1.0e-10);
97          ArcsSet.Split split = set.split(arc);
98          for (double alpha = 0.01; alpha < MathUtils.TWO_PI; alpha += 0.01) {
99              S1Point p = new S1Point(alpha);
100             if (alpha > FastMath.PI) {
101                 Assert.assertEquals(Location.OUTSIDE, split.getPlus().checkPoint(p));
102                 Assert.assertEquals(Location.INSIDE,  split.getMinus().checkPoint(p));
103             } else {
104                 Assert.assertEquals(Location.INSIDE,  split.getPlus().checkPoint(p));
105                 Assert.assertEquals(Location.OUTSIDE, split.getMinus().checkPoint(p));
106             }
107         }
108 
109         S1Point zero = new S1Point(0.0);
110         Assert.assertEquals(Location.BOUNDARY,  split.getPlus().checkPoint(zero));
111         Assert.assertEquals(Location.BOUNDARY,  split.getMinus().checkPoint(zero));
112 
113         S1Point pi = new S1Point(FastMath.PI);
114         Assert.assertEquals(Location.BOUNDARY,  split.getPlus().checkPoint(pi));
115         Assert.assertEquals(Location.BOUNDARY,  split.getMinus().checkPoint(pi));
116 
117     }
118 
119     @Test(expected=MathIllegalArgumentException.class)
120     public void testWrongInterval() {
121         new ArcsSet(1.2, 0.0, 1.0e-10);
122     }
123 
124     @Test(expected=MathIllegalArgumentException.class)
125     public void testTooSmallTolerance() {
126         new ArcsSet(0.0, 1.0, 0.9 * Sphere1D.SMALLEST_TOLERANCE);
127     }
128 
129     @Test
130     public void testFullEqualEndPoints() {
131         ArcsSet set = new ArcsSet(1.0, 1.0, 1.0e-10);
132         Assert.assertEquals(1.0e-10, set.getTolerance(), 1.0e-20);
133         Assert.assertEquals(Region.Location.INSIDE, set.checkPoint(new S1Point(9.0)));
134         for (double alpha = -20.0; alpha <= 20.0; alpha += 0.1) {
135             Assert.assertEquals(Region.Location.INSIDE, set.checkPoint(new S1Point(alpha)));
136         }
137         Assert.assertEquals(1, set.asList().size());
138         Assert.assertEquals(0.0, set.asList().get(0).getInf(), 1.0e-10);
139         Assert.assertEquals(2 * FastMath.PI, set.asList().get(0).getSup(), 1.0e-10);
140         Assert.assertEquals(2 * FastMath.PI, set.getSize(), 1.0e-10);
141     }
142 
143     @Test
144     public void testFullCircle() {
145         ArcsSet set = new ArcsSet(1.0e-10);
146         Assert.assertEquals(1.0e-10, set.getTolerance(), 1.0e-20);
147         Assert.assertEquals(Region.Location.INSIDE, set.checkPoint(new S1Point(9.0)));
148         for (double alpha = -20.0; alpha <= 20.0; alpha += 0.1) {
149             Assert.assertEquals(Region.Location.INSIDE, set.checkPoint(new S1Point(alpha)));
150         }
151         Assert.assertEquals(1, set.asList().size());
152         Assert.assertEquals(0.0, set.asList().get(0).getInf(), 1.0e-10);
153         Assert.assertEquals(2 * FastMath.PI, set.asList().get(0).getSup(), 1.0e-10);
154         Assert.assertEquals(2 * FastMath.PI, set.getSize(), 1.0e-10);
155     }
156 
157     @Test
158     public void testEmpty() {
159         ArcsSet empty = (ArcsSet) new RegionFactory<Sphere1D>().getComplement(new ArcsSet(1.0e-10));
160         Assert.assertEquals(1.0e-10, empty.getTolerance(), 1.0e-20);
161         Assert.assertEquals(0.0, empty.getSize(), 1.0e-10);
162         Assert.assertTrue(empty.asList().isEmpty());
163     }
164 
165     @Test
166     public void testTiny() {
167         ArcsSet tiny = new ArcsSet(0.0, Precision.SAFE_MIN / 2, 1.0e-10);
168         Assert.assertEquals(1.0e-10, tiny.getTolerance(), 1.0e-20);
169         Assert.assertEquals(Precision.SAFE_MIN / 2, tiny.getSize(), 1.0e-10);
170         Assert.assertEquals(1, tiny.asList().size());
171         Assert.assertEquals(0.0, tiny.asList().get(0).getInf(), 1.0e-10);
172         Assert.assertEquals(Precision.SAFE_MIN / 2, tiny.asList().get(0).getSup(), 1.0e-10);
173     }
174 
175     @Test
176     public void testSpecialConstruction() {
177         List<SubHyperplane<Sphere1D>> boundary = new ArrayList<SubHyperplane<Sphere1D>>();
178         boundary.add(new LimitAngle(new S1Point(0.0), false, 1.0e-10).wholeHyperplane());
179         boundary.add(new LimitAngle(new S1Point(MathUtils.TWO_PI - 1.0e-11), true, 1.0e-10).wholeHyperplane());
180         ArcsSet set = new ArcsSet(boundary, 1.0e-10);
181         Assert.assertEquals(MathUtils.TWO_PI, set.getSize(), 1.0e-10);
182         Assert.assertEquals(1.0e-10, set.getTolerance(), 1.0e-20);
183         Assert.assertEquals(1, set.asList().size());
184         Assert.assertEquals(0.0, set.asList().get(0).getInf(), 1.0e-10);
185         Assert.assertEquals(MathUtils.TWO_PI, set.asList().get(0).getSup(), 1.0e-10);
186     }
187 
188     @Test
189     public void testDifference() {
190 
191         ArcsSet a   = new ArcsSet(1.0, 6.0, 1.0e-10);
192         List<Arc> aList = a.asList();
193         Assert.assertEquals(1,   aList.size());
194         Assert.assertEquals(1.0, aList.get(0).getInf(), 1.0e-10);
195         Assert.assertEquals(6.0, aList.get(0).getSup(), 1.0e-10);
196 
197         ArcsSet b   = new ArcsSet(3.0, 5.0, 1.0e-10);
198         List<Arc> bList = b.asList();
199         Assert.assertEquals(1,   bList.size());
200         Assert.assertEquals(3.0, bList.get(0).getInf(), 1.0e-10);
201         Assert.assertEquals(5.0, bList.get(0).getSup(), 1.0e-10);
202 
203         ArcsSet aMb = (ArcsSet) new RegionFactory<Sphere1D>().difference(a, b);
204         for (int k = -2; k < 3; ++k) {
205             Assert.assertEquals(Location.OUTSIDE,  aMb.checkPoint(new S1Point(0.0 + k * MathUtils.TWO_PI)));
206             Assert.assertEquals(Location.OUTSIDE,  aMb.checkPoint(new S1Point(0.9 + k * MathUtils.TWO_PI)));
207             Assert.assertEquals(Location.BOUNDARY, aMb.checkPoint(new S1Point(1.0 + k * MathUtils.TWO_PI)));
208             Assert.assertEquals(Location.INSIDE,   aMb.checkPoint(new S1Point(1.1 + k * MathUtils.TWO_PI)));
209             Assert.assertEquals(Location.INSIDE,   aMb.checkPoint(new S1Point(2.9 + k * MathUtils.TWO_PI)));
210             Assert.assertEquals(Location.BOUNDARY, aMb.checkPoint(new S1Point(3.0 + k * MathUtils.TWO_PI)));
211             Assert.assertEquals(Location.OUTSIDE,  aMb.checkPoint(new S1Point(3.1 + k * MathUtils.TWO_PI)));
212             Assert.assertEquals(Location.OUTSIDE,  aMb.checkPoint(new S1Point(4.9 + k * MathUtils.TWO_PI)));
213             Assert.assertEquals(Location.BOUNDARY, aMb.checkPoint(new S1Point(5.0 + k * MathUtils.TWO_PI)));
214             Assert.assertEquals(Location.INSIDE,   aMb.checkPoint(new S1Point(5.1 + k * MathUtils.TWO_PI)));
215             Assert.assertEquals(Location.INSIDE,   aMb.checkPoint(new S1Point(5.9 + k * MathUtils.TWO_PI)));
216             Assert.assertEquals(Location.BOUNDARY, aMb.checkPoint(new S1Point(6.0 + k * MathUtils.TWO_PI)));
217             Assert.assertEquals(Location.OUTSIDE,  aMb.checkPoint(new S1Point(6.1 + k * MathUtils.TWO_PI)));
218             Assert.assertEquals(Location.OUTSIDE,  aMb.checkPoint(new S1Point(6.2 + k * MathUtils.TWO_PI)));
219         }
220 
221         List<Arc> aMbList = aMb.asList();
222         Assert.assertEquals(2,   aMbList.size());
223         Assert.assertEquals(1.0, aMbList.get(0).getInf(), 1.0e-10);
224         Assert.assertEquals(3.0, aMbList.get(0).getSup(), 1.0e-10);
225         Assert.assertEquals(5.0, aMbList.get(1).getInf(), 1.0e-10);
226         Assert.assertEquals(6.0, aMbList.get(1).getSup(), 1.0e-10);
227 
228 
229     }
230 
231     @Test
232     public void testIntersection() {
233 
234         ArcsSet a   = (ArcsSet) new RegionFactory<Sphere1D>().union(new ArcsSet(1.0, 3.0, 1.0e-10),
235                                                                     new ArcsSet(5.0, 6.0, 1.0e-10));
236         List<Arc> aList = a.asList();
237         Assert.assertEquals(2,   aList.size());
238         Assert.assertEquals(1.0, aList.get(0).getInf(), 1.0e-10);
239         Assert.assertEquals(3.0, aList.get(0).getSup(), 1.0e-10);
240         Assert.assertEquals(5.0, aList.get(1).getInf(), 1.0e-10);
241         Assert.assertEquals(6.0, aList.get(1).getSup(), 1.0e-10);
242 
243         ArcsSet b   = new ArcsSet(0.0, 5.5, 1.0e-10);
244         List<Arc> bList = b.asList();
245         Assert.assertEquals(1,   bList.size());
246         Assert.assertEquals(0.0, bList.get(0).getInf(), 1.0e-10);
247         Assert.assertEquals(5.5, bList.get(0).getSup(), 1.0e-10);
248 
249         ArcsSet aMb = (ArcsSet) new RegionFactory<Sphere1D>().intersection(a, b);
250         for (int k = -2; k < 3; ++k) {
251             Assert.assertEquals(Location.OUTSIDE,  aMb.checkPoint(new S1Point(0.0 + k * MathUtils.TWO_PI)));
252             Assert.assertEquals(Location.BOUNDARY, aMb.checkPoint(new S1Point(1.0 + k * MathUtils.TWO_PI)));
253             Assert.assertEquals(Location.INSIDE,   aMb.checkPoint(new S1Point(1.1 + k * MathUtils.TWO_PI)));
254             Assert.assertEquals(Location.INSIDE,   aMb.checkPoint(new S1Point(2.9 + k * MathUtils.TWO_PI)));
255             Assert.assertEquals(Location.BOUNDARY, aMb.checkPoint(new S1Point(3.0 + k * MathUtils.TWO_PI)));
256             Assert.assertEquals(Location.OUTSIDE,  aMb.checkPoint(new S1Point(3.1 + k * MathUtils.TWO_PI)));
257             Assert.assertEquals(Location.OUTSIDE,  aMb.checkPoint(new S1Point(4.9 + k * MathUtils.TWO_PI)));
258             Assert.assertEquals(Location.BOUNDARY, aMb.checkPoint(new S1Point(5.0 + k * MathUtils.TWO_PI)));
259             Assert.assertEquals(Location.INSIDE,   aMb.checkPoint(new S1Point(5.1 + k * MathUtils.TWO_PI)));
260             Assert.assertEquals(Location.INSIDE,   aMb.checkPoint(new S1Point(5.4 + k * MathUtils.TWO_PI)));
261             Assert.assertEquals(Location.BOUNDARY, aMb.checkPoint(new S1Point(5.5 + k * MathUtils.TWO_PI)));
262             Assert.assertEquals(Location.OUTSIDE,  aMb.checkPoint(new S1Point(5.6 + k * MathUtils.TWO_PI)));
263             Assert.assertEquals(Location.OUTSIDE,  aMb.checkPoint(new S1Point(6.2 + k * MathUtils.TWO_PI)));
264         }
265 
266         List<Arc> aMbList = aMb.asList();
267         Assert.assertEquals(2,   aMbList.size());
268         Assert.assertEquals(1.0, aMbList.get(0).getInf(), 1.0e-10);
269         Assert.assertEquals(3.0, aMbList.get(0).getSup(), 1.0e-10);
270         Assert.assertEquals(5.0, aMbList.get(1).getInf(), 1.0e-10);
271         Assert.assertEquals(5.5, aMbList.get(1).getSup(), 1.0e-10);
272 
273 
274     }
275 
276     @Test
277     public void testMultiple() {
278         RegionFactory<Sphere1D> factory = new RegionFactory<Sphere1D>();
279         ArcsSet set = (ArcsSet)
280         factory.intersection(factory.union(factory.difference(new ArcsSet(1.0, 6.0, 1.0e-10),
281                                                               new ArcsSet(3.0, 5.0, 1.0e-10)),
282                                                               new ArcsSet(0.5, 2.0, 1.0e-10)),
283                                                               new ArcsSet(0.0, 5.5, 1.0e-10));
284         Assert.assertEquals(3.0, set.getSize(), 1.0e-10);
285         Assert.assertEquals(Region.Location.OUTSIDE,  set.checkPoint(new S1Point(0.0)));
286         Assert.assertEquals(Region.Location.OUTSIDE,  set.checkPoint(new S1Point(4.0)));
287         Assert.assertEquals(Region.Location.OUTSIDE,  set.checkPoint(new S1Point(6.0)));
288         Assert.assertEquals(Region.Location.INSIDE,   set.checkPoint(new S1Point(1.2)));
289         Assert.assertEquals(Region.Location.INSIDE,   set.checkPoint(new S1Point(5.25)));
290         Assert.assertEquals(Region.Location.BOUNDARY, set.checkPoint(new S1Point(0.5)));
291         Assert.assertEquals(Region.Location.BOUNDARY, set.checkPoint(new S1Point(3.0)));
292         Assert.assertEquals(Region.Location.BOUNDARY, set.checkPoint(new S1Point(5.0)));
293         Assert.assertEquals(Region.Location.BOUNDARY, set.checkPoint(new S1Point(5.5)));
294 
295         List<Arc> list = set.asList();
296         Assert.assertEquals(2, list.size());
297         Assert.assertEquals( 0.5, list.get(0).getInf(), 1.0e-10);
298         Assert.assertEquals( 3.0, list.get(0).getSup(), 1.0e-10);
299         Assert.assertEquals( 5.0, list.get(1).getInf(), 1.0e-10);
300         Assert.assertEquals( 5.5, list.get(1).getSup(), 1.0e-10);
301 
302     }
303 
304     @Test
305     public void testSinglePoint() {
306         ArcsSet set = new ArcsSet(1.0, FastMath.nextAfter(1.0, Double.POSITIVE_INFINITY), 1.0e-10);
307         Assert.assertEquals(2 * Precision.EPSILON, set.getSize(), Precision.SAFE_MIN);
308     }
309 
310     @Test
311     public void testIteration() {
312         ArcsSet set = (ArcsSet) new RegionFactory<Sphere1D>().difference(new ArcsSet(1.0, 6.0, 1.0e-10),
313                                                                          new ArcsSet(3.0, 5.0, 1.0e-10));
314         Iterator<double[]> iterator = set.iterator();
315         try {
316             iterator.remove();
317             Assert.fail("an exception should have been thrown");
318         } catch (UnsupportedOperationException uoe) {
319             // expected
320         }
321 
322         Assert.assertTrue(iterator.hasNext());
323         double[] a0 = iterator.next();
324         Assert.assertEquals(2, a0.length);
325         Assert.assertEquals(1.0, a0[0], 1.0e-10);
326         Assert.assertEquals(3.0, a0[1], 1.0e-10);
327 
328         Assert.assertTrue(iterator.hasNext());
329         double[] a1 = iterator.next();
330         Assert.assertEquals(2, a1.length);
331         Assert.assertEquals(5.0, a1[0], 1.0e-10);
332         Assert.assertEquals(6.0, a1[1], 1.0e-10);
333 
334         Assert.assertFalse(iterator.hasNext());
335         try {
336             iterator.next();
337             Assert.fail("an exception should have been thrown");
338         } catch (NoSuchElementException nsee) {
339             // expected
340         }
341 
342     }
343 
344     @Test
345     public void testEmptyTree() {
346         Assert.assertEquals(MathUtils.TWO_PI, new ArcsSet(new BSPTree<Sphere1D>(Boolean.TRUE), 1.0e-10).getSize(), 1.0e-10);
347     }
348 
349     @Test
350     public void testShiftedAngles() {
351         for (int k = -2; k < 3; ++k) {
352             SubLimitAngle l1  = new LimitAngle(new S1Point(1.0 + k * MathUtils.TWO_PI), false, 1.0e-10).wholeHyperplane();
353             SubLimitAngle l2  = new LimitAngle(new S1Point(1.5 + k * MathUtils.TWO_PI), true,  1.0e-10).wholeHyperplane();
354             ArcsSet set = new ArcsSet(new BSPTree<Sphere1D>(l1,
355                                                             new BSPTree<Sphere1D>(Boolean.FALSE),
356                                                             new BSPTree<Sphere1D>(l2,
357                                                                                   new BSPTree<Sphere1D>(Boolean.FALSE),
358                                                                                   new BSPTree<Sphere1D>(Boolean.TRUE),
359                                                                                   null),
360                                                             null),
361                                       1.0e-10);
362             for (double alpha = 1.0e-6; alpha < MathUtils.TWO_PI; alpha += 0.001) {
363                 if (alpha < 1 || alpha > 1.5) {
364                     Assert.assertEquals(Location.OUTSIDE, set.checkPoint(new S1Point(alpha)));
365                 } else {
366                     Assert.assertEquals(Location.INSIDE,  set.checkPoint(new S1Point(alpha)));
367                 }
368             }
369         }
370 
371     }
372 
373     @Test(expected=ArcsSet.InconsistentStateAt2PiWrapping.class)
374     public void testInconsistentState() {
375         SubLimitAngle l1 = new LimitAngle(new S1Point(1.0), false, 1.0e-10).wholeHyperplane();
376         SubLimitAngle l2 = new LimitAngle(new S1Point(2.0), true,  1.0e-10).wholeHyperplane();
377         SubLimitAngle l3 = new LimitAngle(new S1Point(3.0), false, 1.0e-10).wholeHyperplane();
378         new ArcsSet(new BSPTree<Sphere1D>(l1,
379                                           new BSPTree<Sphere1D>(Boolean.FALSE),
380                                           new BSPTree<Sphere1D>(l2,
381                                                                 new BSPTree<Sphere1D>(l3,
382                                                                                       new BSPTree<Sphere1D>(Boolean.FALSE),
383                                                                                       new BSPTree<Sphere1D>(Boolean.TRUE),
384                                                                                       null),
385                                                                 new BSPTree<Sphere1D>(Boolean.TRUE),
386                                                                 null),
387                                           null),
388                                           1.0e-10);
389     }
390 
391     @Test
392     public void testSide() {
393         ArcsSet set = (ArcsSet) new RegionFactory<Sphere1D>().difference(new ArcsSet(1.0, 6.0, 1.0e-10),
394                                                                          new ArcsSet(3.0, 5.0, 1.0e-10));
395         for (int k = -2; k < 3; ++k) {
396             Assert.assertEquals(Side.MINUS, set.split(new Arc(0.5 + k * MathUtils.TWO_PI,
397                                                               6.1 + k * MathUtils.TWO_PI,
398                                                               set.getTolerance())).getSide());
399             Assert.assertEquals(Side.PLUS,  set.split(new Arc(0.5 + k * MathUtils.TWO_PI,
400                                                               0.8 + k * MathUtils.TWO_PI,
401                                                               set.getTolerance())).getSide());
402             Assert.assertEquals(Side.PLUS,  set.split(new Arc(6.2 + k * MathUtils.TWO_PI,
403                                                               6.3 + k * MathUtils.TWO_PI,
404                                                               set.getTolerance())).getSide());
405             Assert.assertEquals(Side.PLUS,  set.split(new Arc(3.5 + k * MathUtils.TWO_PI,
406                                                               4.5 + k * MathUtils.TWO_PI,
407                                                               set.getTolerance())).getSide());
408             Assert.assertEquals(Side.BOTH,  set.split(new Arc(2.9 + k * MathUtils.TWO_PI,
409                                                               4.5 + k * MathUtils.TWO_PI,
410                                                               set.getTolerance())).getSide());
411             Assert.assertEquals(Side.BOTH,  set.split(new Arc(0.5 + k * MathUtils.TWO_PI,
412                                                               1.2 + k * MathUtils.TWO_PI,
413                                                               set.getTolerance())).getSide());
414             Assert.assertEquals(Side.BOTH,  set.split(new Arc(0.5 + k * MathUtils.TWO_PI,
415                                                               5.9 + k * MathUtils.TWO_PI,
416                                                               set.getTolerance())).getSide());
417         }
418     }
419 
420     @Test
421     public void testSideEmbedded() {
422 
423         ArcsSet s35 = new ArcsSet(3.0, 5.0, 1.0e-10);
424         ArcsSet s16 = new ArcsSet(1.0, 6.0, 1.0e-10);
425 
426         Assert.assertEquals(Side.BOTH,  s16.split(new Arc(3.0, 5.0, 1.0e-10)).getSide());
427         Assert.assertEquals(Side.BOTH,  s16.split(new Arc(5.0, 3.0 + MathUtils.TWO_PI, 1.0e-10)).getSide());
428         Assert.assertEquals(Side.MINUS, s35.split(new Arc(1.0, 6.0, 1.0e-10)).getSide());
429         Assert.assertEquals(Side.PLUS,  s35.split(new Arc(6.0, 1.0 + MathUtils.TWO_PI, 1.0e-10)).getSide());
430 
431     }
432 
433     @Test
434     public void testSideOverlapping() {
435         ArcsSet s35 = new ArcsSet(3.0, 5.0, 1.0e-10);
436         ArcsSet s46 = new ArcsSet(4.0, 6.0, 1.0e-10);
437 
438         Assert.assertEquals(Side.BOTH,  s46.split(new Arc(3.0, 5.0, 1.0e-10)).getSide());
439         Assert.assertEquals(Side.BOTH,  s46.split(new Arc(5.0, 3.0 + MathUtils.TWO_PI, 1.0e-10)).getSide());
440         Assert.assertEquals(Side.BOTH, s35.split(new Arc(4.0, 6.0, 1.0e-10)).getSide());
441         Assert.assertEquals(Side.BOTH,  s35.split(new Arc(6.0, 4.0 + MathUtils.TWO_PI, 1.0e-10)).getSide());
442     }
443 
444     @Test
445     public void testSideHyper() {
446         ArcsSet sub = (ArcsSet) new RegionFactory<Sphere1D>().getComplement(new ArcsSet(1.0e-10));
447         Assert.assertTrue(sub.isEmpty());
448         Assert.assertEquals(Side.HYPER,  sub.split(new Arc(2.0, 3.0, 1.0e-10)).getSide());
449     }
450 
451     @Test
452     public void testSplitEmbedded() {
453 
454         ArcsSet s35 = new ArcsSet(3.0, 5.0, 1.0e-10);
455         ArcsSet s16 = new ArcsSet(1.0, 6.0, 1.0e-10);
456 
457         ArcsSet.Split split1 = s16.split(new Arc(3.0, 5.0, 1.0e-10));
458         ArcsSet split1Plus  = split1.getPlus();
459         ArcsSet split1Minus = split1.getMinus();
460         Assert.assertEquals(3.0, split1Plus.getSize(), 1.0e-10);
461         Assert.assertEquals(2,   split1Plus.asList().size());
462         Assert.assertEquals(1.0, split1Plus.asList().get(0).getInf(), 1.0e-10);
463         Assert.assertEquals(3.0, split1Plus.asList().get(0).getSup(), 1.0e-10);
464         Assert.assertEquals(5.0, split1Plus.asList().get(1).getInf(), 1.0e-10);
465         Assert.assertEquals(6.0, split1Plus.asList().get(1).getSup(), 1.0e-10);
466         Assert.assertEquals(2.0, split1Minus.getSize(), 1.0e-10);
467         Assert.assertEquals(1,   split1Minus.asList().size());
468         Assert.assertEquals(3.0, split1Minus.asList().get(0).getInf(), 1.0e-10);
469         Assert.assertEquals(5.0, split1Minus.asList().get(0).getSup(), 1.0e-10);
470 
471         ArcsSet.Split split2 = s16.split(new Arc(5.0, 3.0 + MathUtils.TWO_PI, 1.0e-10));
472         ArcsSet split2Plus  = split2.getPlus();
473         ArcsSet split2Minus = split2.getMinus();
474         Assert.assertEquals(2.0, split2Plus.getSize(), 1.0e-10);
475         Assert.assertEquals(1,   split2Plus.asList().size());
476         Assert.assertEquals(3.0, split2Plus.asList().get(0).getInf(), 1.0e-10);
477         Assert.assertEquals(5.0, split2Plus.asList().get(0).getSup(), 1.0e-10);
478         Assert.assertEquals(3.0, split2Minus.getSize(), 1.0e-10);
479         Assert.assertEquals(2,   split2Minus.asList().size());
480         Assert.assertEquals(1.0, split2Minus.asList().get(0).getInf(), 1.0e-10);
481         Assert.assertEquals(3.0, split2Minus.asList().get(0).getSup(), 1.0e-10);
482         Assert.assertEquals(5.0, split2Minus.asList().get(1).getInf(), 1.0e-10);
483         Assert.assertEquals(6.0, split2Minus.asList().get(1).getSup(), 1.0e-10);
484 
485         ArcsSet.Split split3 = s35.split(new Arc(1.0, 6.0, 1.0e-10));
486         ArcsSet split3Plus  = split3.getPlus();
487         ArcsSet split3Minus = split3.getMinus();
488         Assert.assertNull(split3Plus);
489         Assert.assertEquals(2.0, split3Minus.getSize(), 1.0e-10);
490         Assert.assertEquals(1,   split3Minus.asList().size());
491         Assert.assertEquals(3.0, split3Minus.asList().get(0).getInf(), 1.0e-10);
492         Assert.assertEquals(5.0, split3Minus.asList().get(0).getSup(), 1.0e-10);
493 
494         ArcsSet.Split split4 = s35.split(new Arc(6.0, 1.0 + MathUtils.TWO_PI, 1.0e-10));
495         ArcsSet split4Plus  = split4.getPlus();
496         ArcsSet split4Minus = split4.getMinus();
497         Assert.assertEquals(2.0, split4Plus.getSize(), 1.0e-10);
498         Assert.assertEquals(1,   split4Plus.asList().size());
499         Assert.assertEquals(3.0, split4Plus.asList().get(0).getInf(), 1.0e-10);
500         Assert.assertEquals(5.0, split4Plus.asList().get(0).getSup(), 1.0e-10);
501         Assert.assertNull(split4Minus);
502 
503     }
504 
505     @Test
506     public void testSplitOverlapping() {
507 
508         ArcsSet s35 = new ArcsSet(3.0, 5.0, 1.0e-10);
509         ArcsSet s46 = new ArcsSet(4.0, 6.0, 1.0e-10);
510 
511         ArcsSet.Split split1 = s46.split(new Arc(3.0, 5.0, 1.0e-10));
512         ArcsSet split1Plus  = split1.getPlus();
513         ArcsSet split1Minus = split1.getMinus();
514         Assert.assertEquals(1.0, split1Plus.getSize(), 1.0e-10);
515         Assert.assertEquals(1,   split1Plus.asList().size());
516         Assert.assertEquals(5.0, split1Plus.asList().get(0).getInf(), 1.0e-10);
517         Assert.assertEquals(6.0, split1Plus.asList().get(0).getSup(), 1.0e-10);
518         Assert.assertEquals(1.0, split1Minus.getSize(), 1.0e-10);
519         Assert.assertEquals(1,   split1Minus.asList().size());
520         Assert.assertEquals(4.0, split1Minus.asList().get(0).getInf(), 1.0e-10);
521         Assert.assertEquals(5.0, split1Minus.asList().get(0).getSup(), 1.0e-10);
522 
523         ArcsSet.Split split2 = s46.split(new Arc(5.0, 3.0 + MathUtils.TWO_PI, 1.0e-10));
524         ArcsSet split2Plus  = split2.getPlus();
525         ArcsSet split2Minus = split2.getMinus();
526         Assert.assertEquals(1.0, split2Plus.getSize(), 1.0e-10);
527         Assert.assertEquals(1,   split2Plus.asList().size());
528         Assert.assertEquals(4.0, split2Plus.asList().get(0).getInf(), 1.0e-10);
529         Assert.assertEquals(5.0, split2Plus.asList().get(0).getSup(), 1.0e-10);
530         Assert.assertEquals(1.0, split2Minus.getSize(), 1.0e-10);
531         Assert.assertEquals(1,   split2Minus.asList().size());
532         Assert.assertEquals(5.0, split2Minus.asList().get(0).getInf(), 1.0e-10);
533         Assert.assertEquals(6.0, split2Minus.asList().get(0).getSup(), 1.0e-10);
534 
535         ArcsSet.Split split3 = s35.split(new Arc(4.0, 6.0, 1.0e-10));
536         ArcsSet split3Plus  = split3.getPlus();
537         ArcsSet split3Minus = split3.getMinus();
538         Assert.assertEquals(1.0, split3Plus.getSize(), 1.0e-10);
539         Assert.assertEquals(1,   split3Plus.asList().size());
540         Assert.assertEquals(3.0, split3Plus.asList().get(0).getInf(), 1.0e-10);
541         Assert.assertEquals(4.0, split3Plus.asList().get(0).getSup(), 1.0e-10);
542         Assert.assertEquals(1.0, split3Minus.getSize(), 1.0e-10);
543         Assert.assertEquals(1,   split3Minus.asList().size());
544         Assert.assertEquals(4.0, split3Minus.asList().get(0).getInf(), 1.0e-10);
545         Assert.assertEquals(5.0, split3Minus.asList().get(0).getSup(), 1.0e-10);
546 
547         ArcsSet.Split split4 = s35.split(new Arc(6.0, 4.0 + MathUtils.TWO_PI, 1.0e-10));
548         ArcsSet split4Plus  = split4.getPlus();
549         ArcsSet split4Minus = split4.getMinus();
550         Assert.assertEquals(1.0, split4Plus.getSize(), 1.0e-10);
551         Assert.assertEquals(1,   split4Plus.asList().size());
552         Assert.assertEquals(4.0, split4Plus.asList().get(0).getInf(), 1.0e-10);
553         Assert.assertEquals(5.0, split4Plus.asList().get(0).getSup(), 1.0e-10);
554         Assert.assertEquals(1.0, split4Minus.getSize(), 1.0e-10);
555         Assert.assertEquals(1,   split4Minus.asList().size());
556         Assert.assertEquals(3.0, split4Minus.asList().get(0).getInf(), 1.0e-10);
557         Assert.assertEquals(4.0, split4Minus.asList().get(0).getSup(), 1.0e-10);
558 
559     }
560 
561     @Test
562     public void testFarSplit() {
563         ArcsSet set = new ArcsSet(FastMath.PI, 2.5 * FastMath.PI, 1.0e-10);
564         ArcsSet.Split split = set.split(new Arc(0.5 * FastMath.PI, 1.5 * FastMath.PI, 1.0e-10));
565         ArcsSet splitPlus  = split.getPlus();
566         ArcsSet splitMinus = split.getMinus();
567         Assert.assertEquals(1,   splitMinus.asList().size());
568         Assert.assertEquals(1.0 * FastMath.PI, splitMinus.asList().get(0).getInf(), 1.0e-10);
569         Assert.assertEquals(1.5 * FastMath.PI, splitMinus.asList().get(0).getSup(), 1.0e-10);
570         Assert.assertEquals(0.5 * FastMath.PI, splitMinus.getSize(), 1.0e-10);
571         Assert.assertEquals(1,   splitPlus.asList().size());
572         Assert.assertEquals(1.5 * FastMath.PI, splitPlus.asList().get(0).getInf(), 1.0e-10);
573         Assert.assertEquals(2.5 * FastMath.PI, splitPlus.asList().get(0).getSup(), 1.0e-10);
574         Assert.assertEquals(1.0 * FastMath.PI, splitPlus.getSize(), 1.0e-10);
575 
576     }
577 
578     @Test
579     public void testSplitWithinEpsilon() {
580         double epsilon = 1.0e-10;
581         double a = 6.25;
582         double b = a - 0.5 * epsilon;
583         ArcsSet set = new ArcsSet(a - 1, a, epsilon);
584         Arc arc = new Arc(b, b + FastMath.PI, epsilon);
585         ArcsSet.Split split = set.split(arc);
586         Assert.assertEquals(set.getSize(), split.getPlus().getSize(),  epsilon);
587         Assert.assertNull(split.getMinus());
588     }
589 
590     @Test
591     public void testSideSplitConsistency() {
592         double  epsilon = 1.0e-6;
593         double  a       = 4.725;
594         ArcsSet set     = new ArcsSet(a, a + 0.5, epsilon);
595         Arc     arc     = new Arc(a + 0.5 * epsilon, a + 1, epsilon);
596         ArcsSet.Split split = set.split(arc);
597         Assert.assertNotNull(split.getMinus());
598         Assert.assertNull(split.getPlus());
599         Assert.assertEquals(Side.MINUS, set.split(arc).getSide());
600     }
601 
602     @Test
603     public void testShuffledTreeNonRepresentable() {
604         doTestShuffledTree(FastMath.toRadians( 85.0), FastMath.toRadians( 95.0),
605                            FastMath.toRadians(265.0), FastMath.toRadians(275.0),
606                            1.0e-10);
607     }
608 
609     @Test
610     public void testShuffledTreeRepresentable() {
611         doTestShuffledTree(1.0, 2.0,
612                            4.0, 5.0,
613                            1.0e-10);
614     }
615 
616     private void doTestShuffledTree(final double a0, final double a1,
617                                     final double a2, final double a3,
618                                     final double tol) {
619 
620 
621         // intervals set [ a0 ; a1 ] U [ a2 ; a3 ]
622         final ArcsSet setA =
623                         new ArcsSet(new BSPTree<>(new LimitAngle(new S1Point(a0), false, tol).wholeHyperplane(),
624                                                        new BSPTree<>(Boolean.FALSE),
625                                                        new BSPTree<>(new LimitAngle(new S1Point(a1), true, tol).wholeHyperplane(),
626                                                                      new BSPTree<>(new LimitAngle(new S1Point(a2), false, tol).wholeHyperplane(),
627                                                                                    new BSPTree<>(Boolean.FALSE),
628                                                                                    new BSPTree<>(new LimitAngle(new S1Point(a3), true, tol).wholeHyperplane(),
629                                                                                                  new BSPTree<>(Boolean.FALSE),
630                                                                                                  new BSPTree<>(Boolean.TRUE),
631                                                                                                  null),
632                                                                                    null),
633                                                                      new BSPTree<>(Boolean.TRUE),
634                                                                      null),
635                                                        null),
636                                          1.0e-10);
637         Assert.assertEquals((a1 - a0) + (a3 - a2), setA.getSize(), 1.0e-10);
638         Assert.assertEquals(2, setA.asList().size());
639         Assert.assertEquals(a0, setA.asList().get(0).getInf(), 1.0e-15);
640         Assert.assertEquals(a1, setA.asList().get(0).getSup(), 1.0e-15);
641         Assert.assertEquals(a2, setA.asList().get(1).getInf(), 1.0e-15);
642         Assert.assertEquals(a3, setA.asList().get(1).getSup(), 1.0e-15);
643 
644         // same intervals set [ a0 ; a1 ] U [ a2 ; a3 ], but with a different tree organization
645         final ArcsSet setB =
646                         new ArcsSet(new BSPTree<>(new LimitAngle(new S1Point(a2), false, tol).wholeHyperplane(),
647                                                        new BSPTree<>(new LimitAngle(new S1Point(a0), false, tol).wholeHyperplane(),
648                                                                      new BSPTree<>(Boolean.FALSE),
649                                                                      new BSPTree<>(new LimitAngle(new S1Point(a1), true, tol).wholeHyperplane(),
650                                                                                    new BSPTree<>(Boolean.FALSE),
651                                                                                    new BSPTree<>(Boolean.TRUE),
652                                                                                    null),
653                                                                      null),
654                                                        new BSPTree<>(new LimitAngle(new S1Point(a3), true, tol).wholeHyperplane(),
655                                                                      new BSPTree<>(Boolean.FALSE),
656                                                                      new BSPTree<>(Boolean.TRUE),
657                                                                      null),
658                                                        null),
659                                          1.0e-10);
660         Assert.assertEquals((a1 - a0) + (a3 - a2), setB.getSize(), 1.0e-10);
661         Assert.assertEquals(2, setB.asList().size());
662         Assert.assertEquals(a0, setB.asList().get(0).getInf(), 1.0e-15);
663         Assert.assertEquals(a1, setB.asList().get(0).getSup(), 1.0e-15);
664         Assert.assertEquals(a2, setB.asList().get(1).getInf(), 1.0e-15);
665         Assert.assertEquals(a3, setB.asList().get(1).getSup(), 1.0e-15);
666 
667         final ArcsSet intersection = (ArcsSet) new RegionFactory<Sphere1D>().intersection(setA, setB);
668         Assert.assertEquals((a1 - a0) + (a3 - a2), intersection.getSize(), 1.0e-10);
669         Assert.assertEquals(2, intersection.asList().size());
670         Assert.assertEquals(a0, intersection.asList().get(0).getInf(), 1.0e-15);
671         Assert.assertEquals(a1, intersection.asList().get(0).getSup(), 1.0e-15);
672         Assert.assertEquals(a2, intersection.asList().get(1).getInf(), 1.0e-15);
673         Assert.assertEquals(a3, intersection.asList().get(1).getSup(), 1.0e-15);
674 
675     }
676 
677 }