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.enclosing.euclidean.threed;
    18
    19  import java.util.ArrayList;
    20  import java.util.Arrays;
    21  import java.util.Collections;
    22  import java.util.List;
    23
    24  import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
    25  import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
    26  import org.apache.commons.geometry.enclosing.EnclosingBall;
    27  import org.apache.commons.geometry.euclidean.threed.Vector3D;
    28  import org.apache.commons.rng.UniformRandomProvider;
    29  import org.apache.commons.rng.sampling.UnitSphereSampler;
    30  import org.apache.commons.rng.simple.RandomSource;
    31  import org.junit.Assert;
    32  import org.junit.Test;
    33
    34  public class SphereGeneratorTest {
    35
    36      private static final double TEST_EPS = 1e-10;
    37
    38      private static final DoublePrecisionContext TEST_PRECISION =
    39              new EpsilonDoublePrecisionContext(TEST_EPS);
    40
    41      private final SphereGenerator generator = new SphereGenerator(TEST_PRECISION);
    42
    43      @Test
    44      public void testSupport0Point() {
    45          // arrange
    46          final List<Vector3D> support = Collections.emptyList();
    47
    48          // act
    49          final EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
    50
    51          // assert
    52          Assert.assertTrue(sphere.getRadius() < 0);
    53          Assert.assertEquals(0, sphere.getSupportSize());
    54          Assert.assertEquals(0, sphere.getSupport().size());
    55      }
    56
    57      @Test
    58      public void testSupport1Point() {
    59          // arrange
    60          final DoublePrecisionContext lowPrecision = new EpsilonDoublePrecisionContext(0.5);
    61          final DoublePrecisionContext highPrecision = new EpsilonDoublePrecisionContext(0.001);
    62          final List<Vector3D> support = Collections.singletonList(Vector3D.of(1, 2, 3));
    63
    64          // act
    65          final EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
    66
    67          // assert
    68          Assert.assertEquals(0.0, sphere.getRadius(), TEST_EPS);
    69
    70          Assert.assertTrue(sphere.contains(support.get(0)));
    71          Assert.assertTrue(sphere.contains(support.get(0), lowPrecision));
    72          Assert.assertFalse(sphere.contains(Vector3D.of(support.get(0).getX() + 0.1,
    73                                                          support.get(0).getY() + 0.1,
    74                                                          support.get(0).getZ() + 0.1),
    75                                              highPrecision));
    76          Assert.assertTrue(sphere.contains(Vector3D.of(support.get(0).getX() + 0.1,
    77                                                         support.get(0).getY() + 0.1,
    78                                                         support.get(0).getZ() + 0.1),
    79                                              lowPrecision));
    80
    81          Assert.assertEquals(0, support.get(0).distance(sphere.getCenter()), 1.0e-10);
    82          Assert.assertEquals(1, sphere.getSupportSize());
    83          Assert.assertEquals(support.get(0), sphere.getSupport().get(0));
    84      }
    85
    86      @Test
    87      public void testSupport2Points() {
    88          // arrange
    89          final List<Vector3D> support = Arrays.asList(Vector3D.of(1, 0, 0),
    90                                                 Vector3D.of(3, 0, 0));
    91
    92          // act
    93          final EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
    94
    95          // assert
    96          Assert.assertEquals(1.0, sphere.getRadius(), TEST_EPS);
    97
    98          int i = 0;
    99          for (final Vector3D v : support) {
    100             Assert.assertTrue(sphere.contains(v));
    101             Assert.assertEquals(1.0, v.distance(sphere.getCenter()), TEST_EPS);
    102             Assert.assertSame(v, sphere.getSupport().get(i++));
    103         }
    104
    105         Assert.assertTrue(sphere.contains(Vector3D.of(2, 0.9, 0)));
    106         Assert.assertFalse(sphere.contains(Vector3D.ZERO));
    107         Assert.assertEquals(0.0, Vector3D.of(2, 0, 0).distance(sphere.getCenter()), TEST_EPS);
    108         Assert.assertEquals(2, sphere.getSupportSize());
    109     }
    110
    111     @Test
    112     public void testSupport3Points() {
    113         // arrange
    114         final List<Vector3D> support = Arrays.asList(Vector3D.of(1, 0, 0),
    115                                                Vector3D.of(3, 0, 0),
    116                                                Vector3D.of(2, 2, 0));
    117
    118         // act
    119         final EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
    120
    121         // assert
    122         Assert.assertEquals(5.0 / 4.0, sphere.getRadius(), TEST_EPS);
    123
    124         int i = 0;
    125         for (final Vector3D v : support) {
    126             Assert.assertTrue(sphere.contains(v));
    127             Assert.assertEquals(5.0 / 4.0, v.distance(sphere.getCenter()), TEST_EPS);
    128             Assert.assertEquals(v, sphere.getSupport().get(i++));
    129         }
    130
    131         Assert.assertTrue(sphere.contains(Vector3D.of(2, 0.9, 0)));
    132         Assert.assertFalse(sphere.contains(Vector3D.of(0.9, 0, 0)));
    133         Assert.assertFalse(sphere.contains(Vector3D.of(3.1, 0, 0)));
    134         Assert.assertTrue(sphere.contains(Vector3D.of(2.0, -0.499, 0)));
    135         Assert.assertFalse(sphere.contains(Vector3D.of(2.0, -0.501, 0)));
    136         Assert.assertTrue(sphere.contains(Vector3D.of(2.0, 3.0 / 4.0, -1.249)));
    137         Assert.assertFalse(sphere.contains(Vector3D.of(2.0, 3.0 / 4.0, -1.251)));
    138         Assert.assertEquals(0.0, Vector3D.of(2.0, 3.0 / 4.0, 0).distance(sphere.getCenter()), TEST_EPS);
    139         Assert.assertEquals(3, sphere.getSupportSize());
    140     }
    141
    142     @Test
    143     public void testSupport4Points() {
    144         // arrange
    145         final List<Vector3D> support = Arrays.asList(Vector3D.of(17, 14, 18),
    146                                                Vector3D.of(11, 14, 22),
    147                                                Vector3D.of(2, 22, 17),
    148                                                Vector3D.of(22, 11, -10));
    149
    150         // act
    151         final EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
    152
    153         // assert
    154         Assert.assertEquals(25.0, sphere.getRadius(), TEST_EPS);
    155
    156         int i = 0;
    157         for (final Vector3D v : support) {
    158             Assert.assertTrue(sphere.contains(v));
    159             Assert.assertEquals(25.0, v.distance(sphere.getCenter()), 1.0e-10);
    160             Assert.assertEquals(v, sphere.getSupport().get(i++));
    161         }
    162
    163         Assert.assertTrue(sphere.contains(Vector3D.of(-22.999, 2, 2)));
    164         Assert.assertFalse(sphere.contains(Vector3D.of(-23.001, 2, 2)));
    165         Assert.assertTrue(sphere.contains(Vector3D.of(26.999, 2, 2)));
    166         Assert.assertFalse(sphere.contains(Vector3D.of(27.001, 2, 2)));
    167         Assert.assertTrue(sphere.contains(Vector3D.of(2, -22.999, 2)));
    168         Assert.assertFalse(sphere.contains(Vector3D.of(2, -23.001, 2)));
    169         Assert.assertTrue(sphere.contains(Vector3D.of(2, 26.999, 2)));
    170         Assert.assertFalse(sphere.contains(Vector3D.of(2, 27.001, 2)));
    171         Assert.assertTrue(sphere.contains(Vector3D.of(2, 2, -22.999)));
    172         Assert.assertFalse(sphere.contains(Vector3D.of(2, 2, -23.001)));
    173         Assert.assertTrue(sphere.contains(Vector3D.of(2, 2, 26.999)));
    174         Assert.assertFalse(sphere.contains(Vector3D.of(2, 2, 27.001)));
    175         Assert.assertEquals(0.0, Vector3D.of(2.0, 2.0, 2.0).distance(sphere.getCenter()), TEST_EPS);
    176         Assert.assertEquals(4, sphere.getSupportSize());
    177     }
    178
    179     @Test
    180     public void testRandom() {
    181         // arrange
    182         final UniformRandomProvider random = RandomSource.create(RandomSource.WELL_1024_A,
    183                                                                  0xd015982e9f31ee04L);
    184         final UnitSphereSampler sr = new UnitSphereSampler(3, random);
    185         for (int i = 0; i < 100; ++i) {
    186             final double d = 25 * random.nextDouble();
    187             final double refRadius = 10 * random.nextDouble();
    188             final Vector3D refCenter = Vector3D.linearCombination(d, Vector3D.of(sr.nextVector()));
    189             final List<Vector3D> support = new ArrayList<>();
    190             for (int j = 0; j < 5; ++j) {
    191                 support.add(Vector3D.linearCombination(1.0, refCenter, refRadius, Vector3D.of(sr.nextVector())));
    192             }
    193
    194             // act
    195             final EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
    196
    197             // assert
    198             Assert.assertEquals(0.0, refCenter.distance(sphere.getCenter()), 4e-7 * refRadius);
    199             Assert.assertEquals(refRadius, sphere.getRadius(), 1e-7 * refRadius);
    200         }
    201     }
    202
    203     @Test
    204     public void testDegeneratedCase() {
    205         // --- arrange
    206         final List<Vector3D> support =
    207                Arrays.asList(Vector3D.of(Math.scalb(-8039905610797991.0, -50),   //   -7.140870659936730
    208                                           Math.scalb(-4663475464714142.0, -48),   //  -16.567993074240455
    209                                           Math.scalb(6592658872616184.0, -49)),  //   11.710914678204503
    210                              Vector3D.of(Math.scalb(-8036658568968473.0, -50),   //   -7.137986707455888
    211                                           Math.scalb(-4664256346424880.0, -48),   //  -16.570767323375720
    212                                           Math.scalb(6591357011730307.0, -49)),  //  11.708602108715928)
    213                              Vector3D.of(Math.scalb(-8037820142977230.0, -50),   //   -7.139018392423351
    214                                           Math.scalb(-4665280434237813.0, -48),   //  -16.574405614157020
    215                                           Math.scalb(6592435966112099.0, -49)),  //   11.710518716711425
    216                              Vector3D.of(Math.scalb(-8038007803611611.0, -50),   //   -7.139185068549035
    217                                           Math.scalb(-4664291215918380.0, -48),   //  -16.570891204702250
    218                                           Math.scalb(6595270610894208.0, -49))); //   11.715554057357394
    219
    220         // --- act
    221         final EnclosingBall<Vector3D> sphere = generator.ballOnSupport(support);
    222
    223         // --- assert
    224         // the following values have been computed using Emacs calc with exact arithmetic from the
    225         // rational representation corresponding to the scalb calls (i.e. -8039905610797991/2^50, ...)
    226         // The results were converted to decimal representation rounded to 1.0e-30 when writing the reference
    227         // values in this test
    228         final double eps = 1e-20;
    229         Assert.assertEquals(0.003616820213530053297575846168, sphere.getRadius(), eps);
    230         Assert.assertEquals(-7.139325643360503322823511839511, sphere.getCenter().getX(), eps);
    231         Assert.assertEquals(-16.571096474251747245361467833760, sphere.getCenter().getY(), eps);
    232         Assert.assertEquals(11.711945804096960876521111630800, sphere.getCenter().getZ(), eps);
    233
    234         final DoublePrecisionContext supportPrecision = new EpsilonDoublePrecisionContext(1e-14);
    235         for (final Vector3D v : support) {
    236             Assert.assertTrue(sphere.contains(v, supportPrecision));
    237         }
    238     }
    239 }