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