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.twod;
    18
    19  import java.util.ArrayList;
    20  import java.util.Arrays;
    21  import java.util.List;
    22
    23  import org.apache.commons.geometry.core.GeometryTestUtils;
    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.EuclideanTestUtils;
    28  import org.apache.commons.geometry.euclidean.twod.Vector2D;
    29  import org.apache.commons.rng.UniformRandomProvider;
    30  import org.apache.commons.rng.simple.RandomSource;
    31  import org.junit.Assert;
    32  import org.junit.Test;
    33
    34  public class WelzlEncloser2DTest {
    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 WelzlEncloser2D encloser = new WelzlEncloser2D(TEST_PRECISION);
    42
    43      @Test
    44      public void testNoPoints() {
    45          // arrange
    46          final String msg = "Unable to generate enclosing ball: no points given";
    47
    48          // act/assert
    49          GeometryTestUtils.assertThrows(() -> {
    50              encloser.enclose(null);
    51          }, IllegalArgumentException.class, msg);
    52
    53          GeometryTestUtils.assertThrows(() -> {
    54              encloser.enclose(new ArrayList<Vector2D>());
    55          }, IllegalArgumentException.class, msg);
    56      }
    57
    58      @Test
    59      public void testRegularPoints() {
    60          // arrange
    61          final List<Vector2D> list = buildList(22, 26, 30, 38, 64, 28,  8, 54, 11, 15);
    62
    63          // act/assert
    64          checkDisk(list, Arrays.asList(list.get(2), list.get(3), list.get(4)));
    65      }
    66
    67      @Test
    68      public void testSolutionOnDiameter() {
    69          // arrange
    70          final List<Vector2D> list = buildList(22, 26, 30, 38, 64, 28,  8, 54);
    71
    72          // act/assert
    73          checkDisk(list, Arrays.asList(list.get(2), list.get(3)));
    74      }
    75
    76      @Test
    77      public void testReducingBall1() {
    78          // arrange
    79          final List<Vector2D> list = buildList(0.05380958511396061, 0.57332359658700000,
    80                                          0.99348810731127870, 0.02056421361521466,
    81                                          0.01203950647796437, 0.99779675042261860,
    82                                          0.00810189987706078, 0.00589246003827815,
    83                                          0.00465180821202149, 0.99219972923046940);
    84
    85          // act/assert
    86          checkDisk(list, Arrays.asList(list.get(1), list.get(3), list.get(4)));
    87      }
    88
    89      @Test
    90      public void testReducingBall2() {
    91          // arrange
    92          final List<Vector2D> list = buildList(0.016930586154703, 0.333955448537779,
    93                                          0.987189104892331, 0.969778855274507,
    94                                          0.983696889599935, 0.012904580013266,
    95                                          0.013114499572905, 0.034740156356895);
    96
    97          // act/assert
    98          checkDisk(list, Arrays.asList(list.get(1), list.get(2), list.get(3)));
    99      }
    100
    101     @Test
    102     public void testLargeSamples() {
    103         // arrange
    104         final UniformRandomProvider random = RandomSource.create(RandomSource.WELL_1024_A, 0xa2a63cad12c01fb2L);
    105         for (int k = 0; k < 100; ++k) {
    106             final int nbPoints = random.nextInt(10000);
    107             final List<Vector2D> points = new ArrayList<>();
    108             for (int i = 0; i < nbPoints; ++i) {
    109                 final double x = random.nextDouble();
    110                 final double y = random.nextDouble();
    111                 points.add(Vector2D.of(x, y));
    112             }
    113
    114             // act/assert
    115             checkDisk(points);
    116         }
    117     }
    118
    119     @Test
    120     public void testEnclosingWithPrecision() {
    121         // arrange
    122         final List<Vector2D> points = Arrays.asList(
    123                 Vector2D.of(271.59, 57.282),
    124                 Vector2D.of(269.145, 57.063),
    125                 Vector2D.of(309.117, 77.187),
    126                 Vector2D.of(316.989, 34.835),
    127                 Vector2D.of(323.101, 53.972)
    128         );
    129         final double precision = 1;
    130         final DoublePrecisionContext precisionContext = new EpsilonDoublePrecisionContext(precision);
    131         final WelzlEncloser2D customPrecisionEncloser = new WelzlEncloser2D(precisionContext);
    132
    133         // act
    134         final EnclosingBall<Vector2D> result = customPrecisionEncloser.enclose(points);
    135
    136         // assert
    137         Assert.assertEquals(27.099954200964234, result.getRadius(), TEST_EPS);
    138         EuclideanTestUtils.assertCoordinatesEqual(Vector2D.of(296.0056977503686, 53.469890753441945),
    139                 result.getCenter(), TEST_EPS);
    140     }
    141
    142     private List<Vector2D> buildList(final double... coordinates) {
    143         final List<Vector2D> list = new ArrayList<>(coordinates.length / 2);
    144         for (int i = 0; i < coordinates.length; i += 2) {
    145             list.add(Vector2D.of(coordinates[i], coordinates[i + 1]));
    146         }
    147         return list;
    148     }
    149
    150     private void checkDisk(final List<Vector2D> points, final List<Vector2D> refSupport) {
    151
    152         final EnclosingBall<Vector2D> disk = checkDisk(points);
    153
    154         // compare computed disk with expected disk
    155         final EnclosingBall<Vector2D> expected = new DiskGenerator().ballOnSupport(refSupport);
    156         Assert.assertEquals(refSupport.size(), disk.getSupportSize());
    157         Assert.assertEquals(expected.getRadius(),        disk.getRadius(),        1.0e-10);
    158         Assert.assertEquals(expected.getCenter().getX(), disk.getCenter().getX(), 1.0e-10);
    159         Assert.assertEquals(expected.getCenter().getY(), disk.getCenter().getY(), 1.0e-10);
    160
    161         for (final Vector2D s : disk.getSupport()) {
    162             boolean found = false;
    163             for (final Vector2D rs : refSupport) {
    164                 if (s == rs) {
    165                     found = true;
    166                     break;
    167                 }
    168             }
    169             Assert.assertTrue(found);
    170         }
    171
    172         // check removing any point of the support disk fails to enclose the point
    173         for (int i = 0; i < disk.getSupportSize(); ++i) {
    174             final List<Vector2D> reducedSupport = new ArrayList<>();
    175             int count = 0;
    176             for (final Vector2D s : disk.getSupport()) {
    177                 if (count++ != i) {
    178                     reducedSupport.add(s);
    179                 }
    180             }
    181             final EnclosingBall<Vector2D> reducedDisk = new DiskGenerator().ballOnSupport(reducedSupport);
    182             boolean foundOutside = false;
    183             for (int j = 0; j < points.size() && !foundOutside; ++j) {
    184                 if (!reducedDisk.contains(points.get(j), TEST_PRECISION)) {
    185                     foundOutside = true;
    186                 }
    187             }
    188             Assert.assertTrue(foundOutside);
    189         }
    190     }
    191
    192     private EnclosingBall<Vector2D> checkDisk(final List<Vector2D> points) {
    193
    194         final EnclosingBall<Vector2D> disk = encloser.enclose(points);
    195
    196         // all points are enclosed
    197         for (final Vector2D v : points) {
    198             Assert.assertTrue(disk.contains(v, TEST_PRECISION));
    199         }
    200
    201         // all support points are on the boundary
    202         final Vector2D center = disk.getCenter();
    203         final double radius = disk.getRadius();
    204
    205         for (final Vector2D s : disk.getSupport()) {
    206             Assert.assertTrue(TEST_PRECISION.eqZero(center.distance(s) - radius));
    207         }
    208
    209         return disk;
    210     }
    211 }