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}