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.Collection;
20  
21  import org.hipparchus.exception.LocalizedCoreFormats;
22  import org.hipparchus.exception.MathIllegalArgumentException;
23  import org.hipparchus.exception.MathIllegalStateException;
24  import org.hipparchus.geometry.euclidean.twod.Vector2D;
25  import org.hipparchus.util.MathUtils;
26  
27  /**
28   * Abstract base class for convex hull generators in the two-dimensional euclidean space.
29   *
30   */
31  abstract class AbstractConvexHullGenerator2D implements ConvexHullGenerator2D {
32  
33      /** Default value for tolerance. */
34      private static final double DEFAULT_TOLERANCE = 1e-10;
35  
36      /** Tolerance below which points are considered identical. */
37      private final double tolerance;
38  
39      /**
40       * Indicates if collinear points on the hull shall be present in the output.
41       * If {@code false}, only the extreme points are added to the hull.
42       */
43      private final boolean includeCollinearPoints;
44  
45      /**
46       * Simple constructor.
47       * <p>
48       * The default tolerance (1e-10) will be used to determine identical points.
49       *
50       * @param includeCollinearPoints indicates if collinear points on the hull shall be
51       * added as hull vertices
52       */
53      protected AbstractConvexHullGenerator2D(final boolean includeCollinearPoints) {
54          this(includeCollinearPoints, DEFAULT_TOLERANCE);
55      }
56  
57      /**
58       * Simple constructor.
59       *
60       * @param includeCollinearPoints indicates if collinear points on the hull shall be
61       * added as hull vertices
62       * @param tolerance tolerance below which points are considered identical
63       */
64      protected AbstractConvexHullGenerator2D(final boolean includeCollinearPoints, final double tolerance) {
65          this.includeCollinearPoints = includeCollinearPoints;
66          this.tolerance = tolerance;
67      }
68  
69      /**
70       * Get the tolerance below which points are considered identical.
71       * @return the tolerance below which points are considered identical
72       */
73      public double getTolerance() {
74          return tolerance;
75      }
76  
77      /**
78       * Returns if collinear points on the hull will be added as hull vertices.
79       * @return {@code true} if collinear points are added as hull vertices, or {@code false}
80       * if only extreme points are present.
81       */
82      public boolean isIncludeCollinearPoints() {
83          return includeCollinearPoints;
84      }
85  
86      /** {@inheritDoc} */
87      @Override
88      public ConvexHull2D generate(final Collection<Vector2D> points)
89              throws MathIllegalStateException {
90          // check for null points
91          MathUtils.checkNotNull(points);
92  
93          final Collection<Vector2D> hullVertices;
94          if (points.size() < 2) {
95              hullVertices = points;
96          } else {
97              hullVertices = findHullVertices(points);
98          }
99  
100         try {
101             return new ConvexHull2D(hullVertices.toArray(new Vector2D[0]), tolerance);
102         } catch (MathIllegalArgumentException e) {
103             // the hull vertices may not form a convex hull if the tolerance value is to large
104             throw new MathIllegalStateException(e, LocalizedCoreFormats.CONVERGENCE_FAILED);
105         }
106     }
107 
108     /**
109      * Find the convex hull vertices from the set of input points.
110      * @param points the set of input points
111      * @return the convex hull vertices in CCW winding
112      */
113     protected abstract Collection<Vector2D> findHullVertices(Collection<Vector2D> points);
114 
115 }