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 }