001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.math3.geometry.euclidean.twod.hull;
018
019import java.io.Serializable;
020
021import org.apache.commons.math3.exception.InsufficientDataException;
022import org.apache.commons.math3.exception.MathIllegalArgumentException;
023import org.apache.commons.math3.exception.util.LocalizedFormats;
024import org.apache.commons.math3.geometry.euclidean.twod.Euclidean2D;
025import org.apache.commons.math3.geometry.euclidean.twod.Line;
026import org.apache.commons.math3.geometry.euclidean.twod.Segment;
027import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
028import org.apache.commons.math3.geometry.hull.ConvexHull;
029import org.apache.commons.math3.geometry.partitioning.Region;
030import org.apache.commons.math3.geometry.partitioning.RegionFactory;
031import org.apache.commons.math3.util.MathArrays;
032import org.apache.commons.math3.util.Precision;
033
034/**
035 * This class represents a convex hull in an two-dimensional euclidean space.
036 *
037 * @since 3.3
038 */
039public class ConvexHull2D implements ConvexHull<Euclidean2D, Vector2D>, Serializable {
040
041    /** Serializable UID. */
042    private static final long serialVersionUID = 20140129L;
043
044    /** Vertices of the hull. */
045    private final Vector2D[] vertices;
046
047    /** Tolerance threshold used during creation of the hull vertices. */
048    private final double tolerance;
049
050    /**
051     * Line segments of the hull.
052     * The array is not serialized and will be created from the vertices on first access.
053     */
054    private transient Segment[] lineSegments;
055
056    /**
057     * Simple constructor.
058     * @param vertices the vertices of the convex hull, must be ordered
059     * @param tolerance tolerance below which points are considered identical
060     * @throws MathIllegalArgumentException if the vertices do not form a convex hull
061     */
062    public ConvexHull2D(final Vector2D[] vertices, final double tolerance)
063        throws MathIllegalArgumentException {
064
065        // assign tolerance as it will be used by the isConvex method
066        this.tolerance = tolerance;
067
068        if (!isConvex(vertices)) {
069            throw new MathIllegalArgumentException(LocalizedFormats.NOT_CONVEX);
070        }
071
072        this.vertices = vertices.clone();
073    }
074
075    /**
076     * Checks whether the given hull vertices form a convex hull.
077     * @param hullVertices the hull vertices
078     * @return {@code true} if the vertices form a convex hull, {@code false} otherwise
079     */
080    private boolean isConvex(final Vector2D[] hullVertices) {
081        if (hullVertices.length < 3) {
082            return true;
083        }
084
085        int sign = 0;
086        for (int i = 0; i < hullVertices.length; i++) {
087            final Vector2D p1 = hullVertices[i == 0 ? hullVertices.length - 1 : i - 1];
088            final Vector2D p2 = hullVertices[i];
089            final Vector2D p3 = hullVertices[i == hullVertices.length - 1 ? 0 : i + 1];
090
091            final Vector2D d1 = p2.subtract(p1);
092            final Vector2D d2 = p3.subtract(p2);
093
094            final double crossProduct = MathArrays.linearCombination(d1.getX(), d2.getY(), -d1.getY(), d2.getX());
095            final int cmp = Precision.compareTo(crossProduct, 0.0, tolerance);
096            // in case of collinear points the cross product will be zero
097            if (cmp != 0.0) {
098                if (sign != 0.0 && cmp != sign) {
099                    return false;
100                }
101                sign = cmp;
102            }
103        }
104
105        return true;
106    }
107
108    /** {@inheritDoc} */
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    public Region<Euclidean2D> createRegion() throws InsufficientDataException {
161        if (vertices.length < 3) {
162            throw new InsufficientDataException();
163        }
164        final RegionFactory<Euclidean2D> factory = new RegionFactory<Euclidean2D>();
165        final Segment[] segments = retrieveLineSegments();
166        final Line[] lineArray = new Line[segments.length];
167        for (int i = 0; i < segments.length; i++) {
168            lineArray[i] = segments[i].getLine();
169        }
170        return factory.buildConvex(lineArray);
171    }
172}