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.io.Serializable;
20  
21  import org.hipparchus.exception.LocalizedCoreFormats;
22  import org.hipparchus.exception.MathIllegalArgumentException;
23  import org.hipparchus.geometry.LocalizedGeometryFormats;
24  import org.hipparchus.geometry.euclidean.twod.Euclidean2D;
25  import org.hipparchus.geometry.euclidean.twod.Line;
26  import org.hipparchus.geometry.euclidean.twod.Segment;
27  import org.hipparchus.geometry.euclidean.twod.Vector2D;
28  import org.hipparchus.geometry.hull.ConvexHull;
29  import org.hipparchus.geometry.partitioning.Region;
30  import org.hipparchus.geometry.partitioning.RegionFactory;
31  import org.hipparchus.util.MathArrays;
32  import org.hipparchus.util.Precision;
33  
34  /**
35   * This class represents a convex hull in an two-dimensional euclidean space.
36   *
37   */
38  public class ConvexHull2D implements ConvexHull<Euclidean2D, Vector2D>, Serializable {
39  
40      /** Serializable UID. */
41      private static final long serialVersionUID = 20140129L;
42  
43      /** Vertices of the hull. */
44      private final Vector2D[] vertices;
45  
46      /** Tolerance threshold used during creation of the hull vertices. */
47      private final double tolerance;
48  
49      /**
50       * Line segments of the hull.
51       * The array is not serialized and will be created from the vertices on first access.
52       */
53      private transient Segment[] lineSegments;
54  
55      /**
56       * Simple constructor.
57       * @param vertices the vertices of the convex hull, must be ordered
58       * @param tolerance tolerance below which points are considered identical
59       * @throws MathIllegalArgumentException if the vertices do not form a convex hull
60       */
61      public ConvexHull2D(final Vector2D[] vertices, final double tolerance)
62          throws MathIllegalArgumentException {
63  
64          // assign tolerance as it will be used by the isConvex method
65          this.tolerance = tolerance;
66  
67          if (!isConvex(vertices)) {
68              throw new MathIllegalArgumentException(LocalizedGeometryFormats.NOT_CONVEX);
69          }
70  
71          this.vertices = vertices.clone();
72      }
73  
74      /**
75       * Checks whether the given hull vertices form a convex hull.
76       * @param hullVertices the hull vertices
77       * @return {@code true} if the vertices form a convex hull, {@code false} otherwise
78       */
79      private boolean isConvex(final Vector2D[] hullVertices) {
80          if (hullVertices.length < 3) {
81              return true;
82          }
83  
84          int sign = 0;
85          for (int i = 0; i < hullVertices.length; i++) {
86              final Vector2D p1 = hullVertices[i == 0 ? hullVertices.length - 1 : i - 1];
87              final Vector2D p2 = hullVertices[i];
88              final Vector2D p3 = hullVertices[i == hullVertices.length - 1 ? 0 : i + 1];
89  
90              final Vector2D d1 = p2.subtract(p1);
91              final Vector2D d2 = p3.subtract(p2);
92  
93              final double crossProduct = MathArrays.linearCombination(d1.getX(), d2.getY(), -d1.getY(), d2.getX());
94              final int cmp = Precision.compareTo(crossProduct, 0.0, tolerance);
95              // in case of collinear points the cross product will be zero
96              if (cmp != 0.0) {
97                  if (sign != 0.0 && cmp != sign) {
98                      return false;
99                  }
100                 sign = cmp;
101             }
102         }
103 
104         return true;
105     }
106 
107     /** {@inheritDoc} */
108     @Override
109     public Vector2D[] getVertices() {
110         return vertices.clone();
111     }
112 
113     /**
114      * Get the line segments of the convex hull, ordered.
115      * @return the line segments of the convex hull
116      */
117     public Segment[] getLineSegments() {
118         return retrieveLineSegments().clone();
119     }
120 
121     /**
122      * Retrieve the line segments from the cached array or create them if needed.
123      *
124      * @return the array of line segments
125      */
126     private Segment[] retrieveLineSegments() {
127         if (lineSegments == null) {
128             // construct the line segments - handle special cases of 1 or 2 points
129             final int size = vertices.length;
130             if (size <= 1) {
131                 this.lineSegments = new Segment[0];
132             } else if (size == 2) {
133                 this.lineSegments = new Segment[1];
134                 final Vector2D p1 = vertices[0];
135                 final Vector2D p2 = vertices[1];
136                 this.lineSegments[0] = new Segment(p1, p2, new Line(p1, p2, tolerance));
137             } else {
138                 this.lineSegments = new Segment[size];
139                 Vector2D firstPoint = null;
140                 Vector2D lastPoint = null;
141                 int index = 0;
142                 for (Vector2D point : vertices) {
143                     if (lastPoint == null) {
144                         firstPoint = point;
145                         lastPoint = point;
146                     } else {
147                         this.lineSegments[index++] =
148                                 new Segment(lastPoint, point, new Line(lastPoint, point, tolerance));
149                         lastPoint = point;
150                     }
151                 }
152                 this.lineSegments[index] =
153                         new Segment(lastPoint, firstPoint, new Line(lastPoint, firstPoint, tolerance));
154             }
155         }
156         return lineSegments;
157     }
158 
159     /** {@inheritDoc} */
160     @Override
161     public Region<Euclidean2D> createRegion() throws MathIllegalArgumentException {
162         if (vertices.length < 3) {
163             throw new MathIllegalArgumentException(LocalizedCoreFormats.INSUFFICIENT_DATA);
164         }
165         final RegionFactory<Euclidean2D> factory = new RegionFactory<>();
166         final Segment[] segments = retrieveLineSegments();
167         final Line[] lineArray = new Line[segments.length];
168         for (int i = 0; i < segments.length; i++) {
169             lineArray[i] = segments[i].getLine();
170         }
171         return factory.buildConvex(lineArray);
172     }
173 }