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.util.ArrayList;
020import java.util.Collection;
021import java.util.Collections;
022import java.util.Comparator;
023import java.util.List;
024
025import org.apache.commons.math3.geometry.euclidean.twod.Line;
026import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
027import org.apache.commons.math3.util.FastMath;
028import org.apache.commons.math3.util.Precision;
029
030/**
031 * Implements Andrew's monotone chain method to generate the convex hull of a finite set of
032 * points in the two-dimensional euclidean space.
033 * <p>
034 * The runtime complexity is O(n log n), with n being the number of input points. If the
035 * point set is already sorted (by x-coordinate), the runtime complexity is O(n).
036 * <p>
037 * The implementation is not sensitive to collinear points on the hull. The parameter
038 * {@code includeCollinearPoints} allows to control the behavior with regard to collinear points.
039 * If {@code true}, all points on the boundary of the hull will be added to the hull vertices,
040 * otherwise only the extreme points will be present. By default, collinear points are not added
041 * as hull vertices.
042 * <p>
043 * The {@code tolerance} parameter (default: 1e-10) is used as epsilon criteria to determine
044 * identical and collinear points.
045 *
046 * @see <a href="http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain">
047 * Andrew's monotone chain algorithm (Wikibooks)</a>
048 * @since 3.3
049 */
050public class MonotoneChain extends AbstractConvexHullGenerator2D {
051
052    /**
053     * Create a new MonotoneChain instance.
054     */
055    public MonotoneChain() {
056        this(false);
057    }
058
059    /**
060     * Create a new MonotoneChain instance.
061     * @param includeCollinearPoints whether collinear points shall be added as hull vertices
062     */
063    public MonotoneChain(final boolean includeCollinearPoints) {
064        super(includeCollinearPoints);
065    }
066
067    /**
068     * Create a new MonotoneChain instance.
069     * @param includeCollinearPoints whether collinear points shall be added as hull vertices
070     * @param tolerance tolerance below which points are considered identical
071     */
072    public MonotoneChain(final boolean includeCollinearPoints, final double tolerance) {
073        super(includeCollinearPoints, tolerance);
074    }
075
076    /** {@inheritDoc} */
077    @Override
078    public Collection<Vector2D> findHullVertices(final Collection<Vector2D> points) {
079
080        final List<Vector2D> pointsSortedByXAxis = new ArrayList<Vector2D>(points);
081
082        // sort the points in increasing order on the x-axis
083        Collections.sort(pointsSortedByXAxis, new Comparator<Vector2D>() {
084            /** {@inheritDoc} */
085            public int compare(final Vector2D o1, final Vector2D o2) {
086                final double tolerance = getTolerance();
087                // need to take the tolerance value into account, otherwise collinear points
088                // will not be handled correctly when building the upper/lower hull
089                final int diff = Precision.compareTo(o1.getX(), o2.getX(), tolerance);
090                if (diff == 0) {
091                    return Precision.compareTo(o1.getY(), o2.getY(), tolerance);
092                } else {
093                    return diff;
094                }
095            }
096        });
097
098        // build lower hull
099        final List<Vector2D> lowerHull = new ArrayList<Vector2D>();
100        for (Vector2D p : pointsSortedByXAxis) {
101            updateHull(p, lowerHull);
102        }
103
104        // build upper hull
105        final List<Vector2D> upperHull = new ArrayList<Vector2D>();
106        for (int idx = pointsSortedByXAxis.size() - 1; idx >= 0; idx--) {
107            final Vector2D p = pointsSortedByXAxis.get(idx);
108            updateHull(p, upperHull);
109        }
110
111        // concatenate the lower and upper hulls
112        // the last point of each list is omitted as it is repeated at the beginning of the other list
113        final List<Vector2D> hullVertices = new ArrayList<Vector2D>(lowerHull.size() + upperHull.size() - 2);
114        for (int idx = 0; idx < lowerHull.size() - 1; idx++) {
115            hullVertices.add(lowerHull.get(idx));
116        }
117        for (int idx = 0; idx < upperHull.size() - 1; idx++) {
118            hullVertices.add(upperHull.get(idx));
119        }
120
121        // special case: if the lower and upper hull may contain only 1 point if all are identical
122        if (hullVertices.isEmpty() && ! lowerHull.isEmpty()) {
123            hullVertices.add(lowerHull.get(0));
124        }
125
126        return hullVertices;
127    }
128
129    /**
130     * Update the partial hull with the current point.
131     *
132     * @param point the current point
133     * @param hull the partial hull
134     */
135    private void updateHull(final Vector2D point, final List<Vector2D> hull) {
136        final double tolerance = getTolerance();
137
138        if (hull.size() == 1) {
139            // ensure that we do not add an identical point
140            final Vector2D p1 = hull.get(0);
141            if (p1.distance(point) < tolerance) {
142                return;
143            }
144        }
145
146        while (hull.size() >= 2) {
147            final int size = hull.size();
148            final Vector2D p1 = hull.get(size - 2);
149            final Vector2D p2 = hull.get(size - 1);
150
151            final double offset = new Line(p1, p2, tolerance).getOffset(point);
152            if (FastMath.abs(offset) < tolerance) {
153                // the point is collinear to the line (p1, p2)
154
155                final double distanceToCurrent = p1.distance(point);
156                if (distanceToCurrent < tolerance || p2.distance(point) < tolerance) {
157                    // the point is assumed to be identical to either p1 or p2
158                    return;
159                }
160
161                final double distanceToLast = p1.distance(p2);
162                if (isIncludeCollinearPoints()) {
163                    final int index = distanceToCurrent < distanceToLast ? size - 1 : size;
164                    hull.add(index, point);
165                } else {
166                    if (distanceToCurrent > distanceToLast) {
167                        hull.remove(size - 1);
168                        hull.add(point);
169                    }
170                }
171                return;
172            } else if (offset > 0) {
173                hull.remove(size - 1);
174            } else {
175                break;
176            }
177        }
178        hull.add(point);
179    }
180
181}