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.hull.euclidean.twod;
    18
    19  import java.util.ArrayList;
    20  import java.util.Collection;
    21  import java.util.Collections;
    22  import java.util.List;
    23
    24  import org.apache.commons.geometry.core.Region;
    25  import org.apache.commons.geometry.core.RegionLocation;
    26  import org.apache.commons.geometry.core.precision.DoublePrecisionContext;
    27  import org.apache.commons.geometry.core.precision.EpsilonDoublePrecisionContext;
    28  import org.apache.commons.geometry.euclidean.twod.ConvexArea;
    29  import org.apache.commons.geometry.euclidean.twod.Vector2D;
    30  import org.apache.commons.numbers.arrays.LinearCombination;
    31  import org.apache.commons.numbers.core.Precision;
    32  import org.apache.commons.rng.UniformRandomProvider;
    33  import org.apache.commons.rng.simple.RandomSource;
    34  import org.junit.Assert;
    35  import org.junit.Before;
    36  import org.junit.Test;
    37
    38  /**
    39   * Abstract base test class for 2D convex hull generators.
    40   */
    41  public abstract class ConvexHullGenerator2DAbstractTest {
    42
    43      protected static final double TEST_EPS = 1e-10;
    44
    45      protected static final DoublePrecisionContext TEST_PRECISION =
    46              new EpsilonDoublePrecisionContext(TEST_EPS);
    47
    48      protected ConvexHullGenerator2D generator;
    49
    50      protected UniformRandomProvider random;
    51
    52      protected abstract ConvexHullGenerator2D createConvexHullGenerator(boolean includeCollinearPoints);
    53
    54      protected Collection<Vector2D> reducePoints(final Collection<Vector2D> points) {
    55          // do nothing by default, may be overridden by other tests
    56          return points;
    57      }
    58
    59      @Before
    60      public void setUp() {
    61          // by default, do not include collinear points
    62          generator = createConvexHullGenerator(false);
    63          random = RandomSource.create(RandomSource.MT, 10);
    64      }
    65
    66      // ------------------------------------------------------------------------------
    67
    68      @Test
    69      public void testEmpty() {
    70          // act
    71          final ConvexHull2D hull = generator.generate(Collections.emptyList());
    72
    73          // assert
    74          Assert.assertEquals(0, hull.getVertices().size());
    75          Assert.assertEquals(0, hull.getPath().getElements().size());
    76          Assert.assertNull(hull.getRegion());
    77      }
    78
    79      @Test
    80      public void testOnePoint() {
    81          // arrange
    82          final List<Vector2D> points = createRandomPoints(1);
    83
    84          // act
    85          final ConvexHull2D hull = generator.generate(points);
    86
    87          // assert
    88          Assert.assertEquals(1, hull.getVertices().size());
    89          Assert.assertEquals(0, hull.getPath().getElements().size());
    90          Assert.assertNull(hull.getRegion());
    91      }
    92
    93      @Test
    94      public void testTwoPoints() {
    95          // arrange
    96          final List<Vector2D> points = createRandomPoints(2);
    97
    98          // act
    99          final ConvexHull2D hull = generator.generate(points);
    100
    101         // assert
    102         Assert.assertEquals(2, hull.getVertices().size());
    103         Assert.assertEquals(1, hull.getPath().getElements().size());
    104         Assert.assertNull(hull.getRegion());
    105     }
    106
    107     @Test
    108     public void testAllIdentical() {
    109         // arrange
    110         final Collection<Vector2D> points = new ArrayList<>();
    111         points.add(Vector2D.of(1, 1));
    112         points.add(Vector2D.of(1, 1));
    113         points.add(Vector2D.of(1, 1));
    114         points.add(Vector2D.of(1, 1));
    115
    116         // act
    117         final ConvexHull2D hull = generator.generate(points);
    118
    119         // assert
    120         Assert.assertEquals(1, hull.getVertices().size());
    121         Assert.assertEquals(0, hull.getPath().getElements().size());
    122         Assert.assertNull(hull.getRegion());
    123     }
    124
    125     @Test
    126     public void testConvexHull() {
    127         // execute 100 random variations
    128         for (int i = 0; i < 100; i++) {
    129             // randomize the size from 4 to 100
    130             final int size = (int) Math.floor(random.nextDouble() * 96.0 + 4.0);
    131
    132             final List<Vector2D> points = createRandomPoints(size);
    133
    134             // act
    135             final ConvexHull2D hull = generator.generate(reducePoints(points));
    136
    137             // assert
    138             checkConvexHull(points, hull);
    139         }
    140     }
    141
    142     @Test
    143     public void testCollinearPoints() {
    144         // arrange
    145         final Collection<Vector2D> points = new ArrayList<>();
    146         points.add(Vector2D.of(1, 1));
    147         points.add(Vector2D.of(2, 2));
    148         points.add(Vector2D.of(2, 4));
    149         points.add(Vector2D.of(4, 1));
    150         points.add(Vector2D.of(10, 1));
    151
    152         // act
    153         final ConvexHull2D hull = generator.generate(points);
    154
    155         // assert
    156         checkConvexHull(points, hull);
    157     }
    158
    159     @Test
    160     public void testCollinearPointsReverse() {
    161         // arrange
    162         final Collection<Vector2D> points = new ArrayList<>();
    163         points.add(Vector2D.of(1, 1));
    164         points.add(Vector2D.of(2, 2));
    165         points.add(Vector2D.of(2, 4));
    166         points.add(Vector2D.of(10, 1));
    167         points.add(Vector2D.of(4, 1));
    168
    169         // act
    170         final ConvexHull2D hull = generator.generate(points);
    171
    172         // assert
    173         checkConvexHull(points, hull);
    174     }
    175
    176     @Test
    177     public void testCollinearPointsIncluded() {
    178         // arrange
    179         final Collection<Vector2D> points = new ArrayList<>();
    180         points.add(Vector2D.of(1, 1));
    181         points.add(Vector2D.of(2, 2));
    182         points.add(Vector2D.of(2, 4));
    183         points.add(Vector2D.of(4, 1));
    184         points.add(Vector2D.of(10, 1));
    185
    186         // act
    187         final ConvexHull2D hull = createConvexHullGenerator(true).generate(points);
    188
    189         // assert
    190         checkConvexHull(points, hull, true);
    191     }
    192
    193     @Test
    194     public void testCollinearPointsIncludedReverse() {
    195         // arrange
    196         final Collection<Vector2D> points = new ArrayList<>();
    197         points.add(Vector2D.of(1, 1));
    198         points.add(Vector2D.of(2, 2));
    199         points.add(Vector2D.of(2, 4));
    200         points.add(Vector2D.of(10, 1));
    201         points.add(Vector2D.of(4, 1));
    202
    203         // act
    204         final ConvexHull2D hull = createConvexHullGenerator(true).generate(points);
    205
    206         // assert
    207         checkConvexHull(points, hull, true);
    208     }
    209
    210     @Test
    211     public void testIdenticalPoints() {
    212         // arrange
    213         final Collection<Vector2D> points = new ArrayList<>();
    214         points.add(Vector2D.of(1, 1));
    215         points.add(Vector2D.of(2, 2));
    216         points.add(Vector2D.of(2, 4));
    217         points.add(Vector2D.of(4, 1));
    218         points.add(Vector2D.of(1, 1));
    219
    220         // act
    221         final ConvexHull2D hull = generator.generate(points);
    222
    223         // assert
    224         checkConvexHull(points, hull);
    225     }
    226
    227     @Test
    228     public void testIdenticalPoints2() {
    229         // arrange
    230         final Collection<Vector2D> points = new ArrayList<>();
    231         points.add(Vector2D.of(1, 1));
    232         points.add(Vector2D.of(2, 2));
    233         points.add(Vector2D.of(2, 4));
    234         points.add(Vector2D.of(4, 1));
    235         points.add(Vector2D.of(1, 1));
    236
    237         // act
    238         final ConvexHull2D hull = createConvexHullGenerator(true).generate(points);
    239
    240         // assert
    241         checkConvexHull(points, hull, true);
    242     }
    243
    244     @Test
    245     public void testClosePoints() {
    246         // arrange
    247         final Collection<Vector2D> points = new ArrayList<>();
    248         points.add(Vector2D.of(1, 1));
    249         points.add(Vector2D.of(2, 2));
    250         points.add(Vector2D.of(2, 4));
    251         points.add(Vector2D.of(4, 1));
    252         points.add(Vector2D.of(1.00001, 1));
    253
    254         // act
    255         final ConvexHull2D hull = generator.generate(points);
    256
    257         // assert
    258         checkConvexHull(points, hull);
    259     }
    260
    261     @Test
    262     public void testCollinearPointOnExistingBoundary() {
    263         // --- arrange
    264         // MATH-1135: check that collinear points on the hull are handled correctly
    265         //            when only a minimal hull shall be constructed
    266         final Collection<Vector2D> points = new ArrayList<>();
    267         points.add(Vector2D.of(7.3152, 34.7472));
    268         points.add(Vector2D.of(6.400799999999997, 34.747199999999985));
    269         points.add(Vector2D.of(5.486399999999997, 34.7472));
    270         points.add(Vector2D.of(4.876799999999999, 34.7472));
    271         points.add(Vector2D.of(4.876799999999999, 34.1376));
    272         points.add(Vector2D.of(4.876799999999999, 30.48));
    273         points.add(Vector2D.of(6.0959999999999965, 30.48));
    274         points.add(Vector2D.of(6.0959999999999965, 34.1376));
    275         points.add(Vector2D.of(7.315199999999996, 34.1376));
    276         points.add(Vector2D.of(7.3152, 30.48));
    277
    278         // --- act
    279         final ConvexHull2D hull = createConvexHullGenerator(false).generate(points);
    280
    281         // --- assert
    282         checkConvexHull(points, hull);
    283     }
    284
    285     @Test
    286     public void testCollinearPointsInAnyOrder_threeCollinearPoints() {
    287         // --- arrange
    288         // MATH-1148: collinear points on the hull might be in any order
    289         //            make sure that they are processed in the proper order
    290         //            for each algorithm.
    291
    292         final List<Vector2D> points = new ArrayList<>();
    293         points.add(Vector2D.of(16.078200000000184, -36.52519999989808));
    294         points.add(Vector2D.of(19.164300000000186, -36.52519999989808));
    295         points.add(Vector2D.of(19.1643, -25.28136477910407));
    296         points.add(Vector2D.of(19.1643, -17.678400000004157));
    297
    298         // --- act/assert
    299         ConvexHull2D hull = createConvexHullGenerator(false).generate(points);
    300         checkConvexHull(points, hull);
    301
    302         hull = createConvexHullGenerator(true).generate(points);
    303         checkConvexHull(points, hull, true);
    304     }
    305
    306     @Test
    307     public void testCollinearPointsInAnyOrder_multipleCollinearPoints() {
    308         // --- arrange
    309         // MATH-1148: collinear points on the hull might be in any order
    310         //            make sure that they are processed in the proper order
    311         //            for each algorithm.
    312
    313         final List<Vector2D> points = new ArrayList<>();
    314         points.add(Vector2D.of(0, -29.959696875));
    315         points.add(Vector2D.of(0, -31.621809375));
    316         points.add(Vector2D.of(0, -28.435696875));
    317         points.add(Vector2D.of(0, -33.145809375));
    318         points.add(Vector2D.of(3.048, -33.145809375));
    319         points.add(Vector2D.of(3.048, -31.621809375));
    320         points.add(Vector2D.of(3.048, -29.959696875));
    321         points.add(Vector2D.of(4.572, -33.145809375));
    322         points.add(Vector2D.of(4.572, -28.435696875));
    323
    324         // --- act/assert
    325         ConvexHull2D hull = createConvexHullGenerator(false).generate(points);
    326         checkConvexHull(points, hull);
    327
    328         hull = createConvexHullGenerator(true).generate(points);
    329         checkConvexHull(points, hull, true);
    330     }
    331
    332     @Test
    333     public void testIssue1123() {
    334         // arrange
    335         final List<Vector2D> points = new ArrayList<>();
    336
    337         final int[][] data = {
    338                 {-11, -1}, {-11, 0}, {-11, 1},
    339                 {-10, -3}, {-10, -2}, {-10, -1}, {-10, 0}, {-10, 1},
    340                 {-10, 2}, {-10, 3}, {-9, -4}, {-9, -3}, {-9, -2},
    341                 {-9, -1}, {-9, 0}, {-9, 1}, {-9, 2}, {-9, 3},
    342                 {-9, 4}, {-8, -5}, {-8, -4}, {-8, -3}, {-8, -2},
    343                 {-8, -1}, {-8, 0}, {-8, 1}, {-8, 2}, {-8, 3},
    344                 {-8, 4}, {-8, 5}, {-7, -6}, {-7, -5}, {-7, -4},
    345                 {-7, -3}, {-7, -2}, {-7, -1}, {-7, 0}, {-7, 1},
    346                 {-7, 2}, {-7, 3}, {-7, 4}, {-7, 5}, {-7, 6},
    347                 {-6, -7}, {-6, -6}, {-6, -5}, {-6, -4}, {-6, -3},
    348                 {-6, -2}, {-6, -1}, {-6, 0}, {-6, 1}, {-6, 2},
    349                 {-6, 3}, {-6, 4}, {-6, 5}, {-6, 6}, {-6, 7},
    350                 {-5, -7}, {-5, -6}, {-5, -5}, {-5, -4}, {-5, -3},
    351                 {-5, -2}, {-5, 4}, {-5, 5}, {-5, 6}, {-5, 7},
    352                 {-4, -7}, {-4, -6}, {-4, -5}, {-4, -4}, {-4, -3},
    353                 {-4, -2}, {-4, 4}, {-4, 5}, {-4, 6}, {-4, 7},
    354                 {-3, -8}, {-3, -7}, {-3, -6}, {-3, -5}, {-3, -4},
    355                 {-3, -3}, {-3, -2}, {-3, 4}, {-3, 5}, {-3, 6},
    356                 {-3, 7}, {-3, 8}, {-2, -8}, {-2, -7}, {-2, -6},
    357                 {-2, -5}, {-2, -4}, {-2, -3}, {-2, -2}, {-2, 4},
    358                 {-2, 5}, {-2, 6}, {-2, 7}, {-2, 8}, {-1, -8},
    359                 {-1, -7}, {-1, -6}, {-1, -5}, {-1, -4}, {-1, -3},
    360                 {-1, -2}, {-1, 4}, {-1, 5}, {-1, 6}, {-1, 7},
    361                 {-1, 8}, {0, -8}, {0, -7}, {0, -6}, {0, -5},
    362                 {0, -4}, {0, -3}, {0, -2}, {0, 4}, {0, 5}, {0, 6},
    363                 {0, 7}, {0, 8}, {1, -8}, {1, -7}, {1, -6}, {1, -5},
    364                 {1, -4}, {1, -3}, {1, -2}, {1, -1}, {1, 0}, {1, 1},
    365                 {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 7},
    366                 {1, 8}, {2, -8}, {2, -7}, {2, -6}, {2, -5},
    367                 {2, -4}, {2, -3}, {2, -2}, {2, -1}, {2, 0}, {2, 1},
    368                 {2, 2}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {2, 7},
    369                 {2, 8}, {3, -8}, {3, -7}, {3, -6}, {3, -5},
    370                 {3, -4}, {3, -3}, {3, -2}, {3, -1}, {3, 0}, {3, 1},
    371                 {3, 2}, {3, 3}, {3, 4}, {3, 5}, {3, 6}, {3, 7},
    372                 {3, 8}, {4, -7}, {4, -6}, {4, -5}, {4, -4},
    373                 {4, -3}, {4, -2}, {4, -1}, {4, 0}, {4, 1}, {4, 2},
    374                 {4, 3}, {4, 4}, {4, 5}, {4, 6}, {4, 7}, {5, -7},
    375                 {5, -6}, {5, -5}, {5, -4}, {5, -3}, {5, -2},
    376                 {5, -1}, {5, 0}, {5, 1}, {5, 2}, {5, 3}, {5, 4},
    377                 {5, 5}, {5, 6}, {5, 7}, {6, -7}, {6, -6}, {6, -5},
    378                 {6, -4}, {6, -3}, {6, -2}, {6, -1}, {6, 0}, {6, 1},
    379                 {6, 2}, {6, 3}, {6, 4}, {6, 5}, {6, 6}, {6, 7},
    380                 {7, -6}, {7, -5}, {7, -4}, {7, -3}, {7, -2},
    381                 {7, -1}, {7, 0}, {7, 1}, {7, 2}, {7, 3}, {7, 4},
    382                 {7, 5}, {7, 6}, {8, -5}, {8, -4}, {8, -3}, {8, -2},
    383                 {8, -1}, {8, 0}, {8, 1}, {8, 2}, {8, 3}, {8, 4},
    384                 {8, 5}, {9, -4}, {9, -3}, {9, -2}, {9, -1}, {9, 0},
    385                 {9, 1}, {9, 2}, {9, 3}, {9, 4}, {10, -3}, {10, -2},
    386                 {10, -1}, {10, 0}, {10, 1}, {10, 2}, {10, 3},
    387                 {11, -1}, {11, 0}, {11, 1}
    388             };
    389
    390         for (final int[] line : data) {
    391             points.add(Vector2D.of(line[0], line[1]));
    392         }
    393
    394         final Vector2D[] referenceHull = {
    395             Vector2D.of(-11.0, -1.0),
    396             Vector2D.of(-10.0, -3.0),
    397             Vector2D.of(-6.0, -7.0),
    398             Vector2D.of(-3.0, -8.0),
    399             Vector2D.of(3.0, -8.0),
    400             Vector2D.of(6.0, -7.0),
    401             Vector2D.of(10.0, -3.0),
    402             Vector2D.of(11.0, -1.0),
    403             Vector2D.of(11.0, 1.0),
    404             Vector2D.of(10.0, 3.0),
    405             Vector2D.of(6.0, 7.0),
    406             Vector2D.of(3.0, 8.0),
    407             Vector2D.of(-3.0, 8.0),
    408             Vector2D.of(-6.0, 7.0),
    409             Vector2D.of(-10.0, 3.0),
    410             Vector2D.of(-11.0, 1.0),
    411         };
    412
    413         // act
    414         final ConvexHull2D convHull = generator.generate(points);
    415         final Region<Vector2D> hullRegion = convHull.getRegion();
    416
    417         // assert
    418         Assert.assertEquals(274.0, hullRegion.getSize(), 1.0e-12);
    419         double perimeter = 0;
    420         for (int i = 0; i < referenceHull.length; ++i) {
    421             perimeter += referenceHull[i].distance(
    422                                            referenceHull[(i + 1) % referenceHull.length]);
    423         }
    424         Assert.assertEquals(perimeter, hullRegion.getBoundarySize(), 1.0e-12);
    425
    426         for (int i = 0; i < referenceHull.length; ++i) {
    427             Assert.assertEquals(RegionLocation.BOUNDARY, hullRegion.classify(referenceHull[i]));
    428         }
    429
    430     }
    431
    432     // ------------------------------------------------------------------------------
    433
    434     protected final List<Vector2D> createRandomPoints(final int size) {
    435         // create the cloud container
    436         final List<Vector2D> points = new ArrayList<>(size);
    437         // fill the cloud with a random distribution of points
    438         for (int i = 0; i < size; i++) {
    439             points.add(Vector2D.of(random.nextDouble() * 2.0 - 1.0, random.nextDouble() * 2.0 - 1.0));
    440         }
    441         return points;
    442     }
    443
    444     protected final void checkConvexHull(final Collection<Vector2D> points, final ConvexHull2D hull) {
    445         checkConvexHull(points, hull, false);
    446     }
    447
    448     protected final void checkConvexHull(final Collection<Vector2D> points, final ConvexHull2D hull,
    449                                          final boolean includesCollinearPoints) {
    450         Assert.assertNotNull(hull);
    451         Assert.assertTrue(isConvex(hull, includesCollinearPoints));
    452         checkPointsInsideHullRegion(points, hull, includesCollinearPoints);
    453     }
    454
    455     // verify that the constructed hull is really convex
    456     protected final boolean isConvex(final ConvexHull2D hull, final boolean includesCollinearPoints) {
    457
    458         final List<Vector2D> points = hull.getVertices();
    459         int sign = 0;
    460         final int size = points.size();
    461
    462         for (int i = 0; i < size; i++) {
    463             final Vector2D p1 = points.get(i == 0 ? size - 1 : i - 1);
    464             final Vector2D p2 = points.get(i);
    465             final Vector2D p3 = points.get(i == size - 1 ? 0 : i + 1);
    466
    467             final Vector2D d1 = p2.subtract(p1);
    468             final Vector2D d2 = p3.subtract(p2);
    469
    470             Assert.assertTrue(d1.norm() > 1e-10);
    471             Assert.assertTrue(d2.norm() > 1e-10);
    472
    473             final double cross = LinearCombination.value(d1.getX(), d2.getY(), -d1.getY(), d2.getX());
    474             final int cmp = Precision.compareTo(cross, 0.0, TEST_EPS);
    475
    476             if (sign != 0 && cmp != sign) {
    477                 if (!includesCollinearPoints || cmp != 0) {
    478                     // in case of collinear points the cross product will be zero
    479                     return false;
    480                 }
    481             }
    482
    483             sign = cmp;
    484         }
    485
    486         return true;
    487     }
    488
    489     // verify that all points are inside the convex hull region
    490     protected final void checkPointsInsideHullRegion(final Collection<Vector2D> points,
    491                                                      final ConvexHull2D hull,
    492                                                      final boolean includesCollinearPoints) {
    493
    494         final Collection<Vector2D> hullVertices = hull.getVertices();
    495         final ConvexArea region = hull.getRegion();
    496
    497         for (final Vector2D p : points) {
    498             final RegionLocation location = region.classify(p);
    499             Assert.assertNotEquals(RegionLocation.OUTSIDE, location);
    500
    501             if (location == RegionLocation.BOUNDARY && includesCollinearPoints) {
    502                 Assert.assertTrue(hullVertices.contains(p));
    503             }
    504         }
    505     }
    506 }