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