diff options
Diffstat (limited to 'src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull')
6 files changed, 684 insertions, 0 deletions
diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AbstractConvexHullGenerator2D.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AbstractConvexHullGenerator2D.java new file mode 100644 index 0000000..b234ad5 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AbstractConvexHullGenerator2D.java @@ -0,0 +1,116 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math3.geometry.euclidean.twod.hull; + +import java.util.Collection; + +import org.apache.commons.math3.exception.ConvergenceException; +import org.apache.commons.math3.exception.MathIllegalArgumentException; +import org.apache.commons.math3.exception.NullArgumentException; +import org.apache.commons.math3.geometry.euclidean.twod.Vector2D; +import org.apache.commons.math3.util.MathUtils; + +/** + * Abstract base class for convex hull generators in the two-dimensional euclidean space. + * + * @since 3.3 + */ +abstract class AbstractConvexHullGenerator2D implements ConvexHullGenerator2D { + + /** Default value for tolerance. */ + private static final double DEFAULT_TOLERANCE = 1e-10; + + /** Tolerance below which points are considered identical. */ + private final double tolerance; + + /** + * Indicates if collinear points on the hull shall be present in the output. + * If {@code false}, only the extreme points are added to the hull. + */ + private final boolean includeCollinearPoints; + + /** + * Simple constructor. + * <p> + * The default tolerance (1e-10) will be used to determine identical points. + * + * @param includeCollinearPoints indicates if collinear points on the hull shall be + * added as hull vertices + */ + protected AbstractConvexHullGenerator2D(final boolean includeCollinearPoints) { + this(includeCollinearPoints, DEFAULT_TOLERANCE); + } + + /** + * Simple constructor. + * + * @param includeCollinearPoints indicates if collinear points on the hull shall be + * added as hull vertices + * @param tolerance tolerance below which points are considered identical + */ + protected AbstractConvexHullGenerator2D(final boolean includeCollinearPoints, final double tolerance) { + this.includeCollinearPoints = includeCollinearPoints; + this.tolerance = tolerance; + } + + /** + * Get the tolerance below which points are considered identical. + * @return the tolerance below which points are considered identical + */ + public double getTolerance() { + return tolerance; + } + + /** + * Returns if collinear points on the hull will be added as hull vertices. + * @return {@code true} if collinear points are added as hull vertices, or {@code false} + * if only extreme points are present. + */ + public boolean isIncludeCollinearPoints() { + return includeCollinearPoints; + } + + /** {@inheritDoc} */ + public ConvexHull2D generate(final Collection<Vector2D> points) + throws NullArgumentException, ConvergenceException { + // check for null points + MathUtils.checkNotNull(points); + + Collection<Vector2D> hullVertices = null; + if (points.size() < 2) { + hullVertices = points; + } else { + hullVertices = findHullVertices(points); + } + + try { + return new ConvexHull2D(hullVertices.toArray(new Vector2D[hullVertices.size()]), + tolerance); + } catch (MathIllegalArgumentException e) { + // the hull vertices may not form a convex hull if the tolerance value is to large + throw new ConvergenceException(); + } + } + + /** + * Find the convex hull vertices from the set of input points. + * @param points the set of input points + * @return the convex hull vertices in CCW winding + */ + protected abstract Collection<Vector2D> findHullVertices(Collection<Vector2D> points); + +} diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AklToussaintHeuristic.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AklToussaintHeuristic.java new file mode 100644 index 0000000..f5d1b84 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AklToussaintHeuristic.java @@ -0,0 +1,153 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math3.geometry.euclidean.twod.hull; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.List; + +import org.apache.commons.math3.geometry.euclidean.twod.Vector2D; + +/** + * A simple heuristic to improve the performance of convex hull algorithms. + * <p> + * The heuristic is based on the idea of a convex quadrilateral, which is formed by + * four points with the lowest and highest x / y coordinates. Any point that lies inside + * this quadrilateral can not be part of the convex hull and can thus be safely discarded + * before generating the convex hull itself. + * <p> + * The complexity of the operation is O(n), and may greatly improve the time it takes to + * construct the convex hull afterwards, depending on the point distribution. + * + * @see <a href="http://en.wikipedia.org/wiki/Convex_hull_algorithms#Akl-Toussaint_heuristic"> + * Akl-Toussaint heuristic (Wikipedia)</a> + * @since 3.3 + */ +public final class AklToussaintHeuristic { + + /** Hide utility constructor. */ + private AklToussaintHeuristic() { + } + + /** + * Returns a point set that is reduced by all points for which it is safe to assume + * that they are not part of the convex hull. + * + * @param points the original point set + * @return a reduced point set, useful as input for convex hull algorithms + */ + public static Collection<Vector2D> reducePoints(final Collection<Vector2D> points) { + + // find the leftmost point + int size = 0; + Vector2D minX = null; + Vector2D maxX = null; + Vector2D minY = null; + Vector2D maxY = null; + for (Vector2D p : points) { + if (minX == null || p.getX() < minX.getX()) { + minX = p; + } + if (maxX == null || p.getX() > maxX.getX()) { + maxX = p; + } + if (minY == null || p.getY() < minY.getY()) { + minY = p; + } + if (maxY == null || p.getY() > maxY.getY()) { + maxY = p; + } + size++; + } + + if (size < 4) { + return points; + } + + final List<Vector2D> quadrilateral = buildQuadrilateral(minY, maxX, maxY, minX); + // if the quadrilateral is not well formed, e.g. only 2 points, do not attempt to reduce + if (quadrilateral.size() < 3) { + return points; + } + + final List<Vector2D> reducedPoints = new ArrayList<Vector2D>(quadrilateral); + for (final Vector2D p : points) { + // check all points if they are within the quadrilateral + // in which case they can not be part of the convex hull + if (!insideQuadrilateral(p, quadrilateral)) { + reducedPoints.add(p); + } + } + + return reducedPoints; + } + + /** + * Build the convex quadrilateral with the found corner points (with min/max x/y coordinates). + * + * @param points the respective points with min/max x/y coordinate + * @return the quadrilateral + */ + private static List<Vector2D> buildQuadrilateral(final Vector2D... points) { + List<Vector2D> quadrilateral = new ArrayList<Vector2D>(); + for (Vector2D p : points) { + if (!quadrilateral.contains(p)) { + quadrilateral.add(p); + } + } + return quadrilateral; + } + + /** + * Checks if the given point is located within the convex quadrilateral. + * @param point the point to check + * @param quadrilateralPoints the convex quadrilateral, represented by 4 points + * @return {@code true} if the point is inside the quadrilateral, {@code false} otherwise + */ + private static boolean insideQuadrilateral(final Vector2D point, + final List<Vector2D> quadrilateralPoints) { + + Vector2D p1 = quadrilateralPoints.get(0); + Vector2D p2 = quadrilateralPoints.get(1); + + if (point.equals(p1) || point.equals(p2)) { + return true; + } + + // get the location of the point relative to the first two vertices + final double last = point.crossProduct(p1, p2); + final int size = quadrilateralPoints.size(); + // loop through the rest of the vertices + for (int i = 1; i < size; i++) { + p1 = p2; + p2 = quadrilateralPoints.get((i + 1) == size ? 0 : i + 1); + + if (point.equals(p1) || point.equals(p2)) { + return true; + } + + // do side of line test: multiply the last location with this location + // if they are the same sign then the operation will yield a positive result + // -x * -y = +xy, x * y = +xy, -x * y = -xy, x * -y = -xy + if (last * point.crossProduct(p1, p2) < 0) { + return false; + } + } + return true; + } + +} diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHull2D.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHull2D.java new file mode 100644 index 0000000..5d9734b --- /dev/null +++ b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHull2D.java @@ -0,0 +1,172 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math3.geometry.euclidean.twod.hull; + +import java.io.Serializable; + +import org.apache.commons.math3.exception.InsufficientDataException; +import org.apache.commons.math3.exception.MathIllegalArgumentException; +import org.apache.commons.math3.exception.util.LocalizedFormats; +import org.apache.commons.math3.geometry.euclidean.twod.Euclidean2D; +import org.apache.commons.math3.geometry.euclidean.twod.Line; +import org.apache.commons.math3.geometry.euclidean.twod.Segment; +import org.apache.commons.math3.geometry.euclidean.twod.Vector2D; +import org.apache.commons.math3.geometry.hull.ConvexHull; +import org.apache.commons.math3.geometry.partitioning.Region; +import org.apache.commons.math3.geometry.partitioning.RegionFactory; +import org.apache.commons.math3.util.MathArrays; +import org.apache.commons.math3.util.Precision; + +/** + * This class represents a convex hull in an two-dimensional euclidean space. + * + * @since 3.3 + */ +public class ConvexHull2D implements ConvexHull<Euclidean2D, Vector2D>, Serializable { + + /** Serializable UID. */ + private static final long serialVersionUID = 20140129L; + + /** Vertices of the hull. */ + private final Vector2D[] vertices; + + /** Tolerance threshold used during creation of the hull vertices. */ + private final double tolerance; + + /** + * Line segments of the hull. + * The array is not serialized and will be created from the vertices on first access. + */ + private transient Segment[] lineSegments; + + /** + * Simple constructor. + * @param vertices the vertices of the convex hull, must be ordered + * @param tolerance tolerance below which points are considered identical + * @throws MathIllegalArgumentException if the vertices do not form a convex hull + */ + public ConvexHull2D(final Vector2D[] vertices, final double tolerance) + throws MathIllegalArgumentException { + + // assign tolerance as it will be used by the isConvex method + this.tolerance = tolerance; + + if (!isConvex(vertices)) { + throw new MathIllegalArgumentException(LocalizedFormats.NOT_CONVEX); + } + + this.vertices = vertices.clone(); + } + + /** + * Checks whether the given hull vertices form a convex hull. + * @param hullVertices the hull vertices + * @return {@code true} if the vertices form a convex hull, {@code false} otherwise + */ + private boolean isConvex(final Vector2D[] hullVertices) { + if (hullVertices.length < 3) { + return true; + } + + int sign = 0; + for (int i = 0; i < hullVertices.length; i++) { + final Vector2D p1 = hullVertices[i == 0 ? hullVertices.length - 1 : i - 1]; + final Vector2D p2 = hullVertices[i]; + final Vector2D p3 = hullVertices[i == hullVertices.length - 1 ? 0 : i + 1]; + + final Vector2D d1 = p2.subtract(p1); + final Vector2D d2 = p3.subtract(p2); + + final double crossProduct = MathArrays.linearCombination(d1.getX(), d2.getY(), -d1.getY(), d2.getX()); + final int cmp = Precision.compareTo(crossProduct, 0.0, tolerance); + // in case of collinear points the cross product will be zero + if (cmp != 0.0) { + if (sign != 0.0 && cmp != sign) { + return false; + } + sign = cmp; + } + } + + return true; + } + + /** {@inheritDoc} */ + public Vector2D[] getVertices() { + return vertices.clone(); + } + + /** + * Get the line segments of the convex hull, ordered. + * @return the line segments of the convex hull + */ + public Segment[] getLineSegments() { + return retrieveLineSegments().clone(); + } + + /** + * Retrieve the line segments from the cached array or create them if needed. + * + * @return the array of line segments + */ + private Segment[] retrieveLineSegments() { + if (lineSegments == null) { + // construct the line segments - handle special cases of 1 or 2 points + final int size = vertices.length; + if (size <= 1) { + this.lineSegments = new Segment[0]; + } else if (size == 2) { + this.lineSegments = new Segment[1]; + final Vector2D p1 = vertices[0]; + final Vector2D p2 = vertices[1]; + this.lineSegments[0] = new Segment(p1, p2, new Line(p1, p2, tolerance)); + } else { + this.lineSegments = new Segment[size]; + Vector2D firstPoint = null; + Vector2D lastPoint = null; + int index = 0; + for (Vector2D point : vertices) { + if (lastPoint == null) { + firstPoint = point; + lastPoint = point; + } else { + this.lineSegments[index++] = + new Segment(lastPoint, point, new Line(lastPoint, point, tolerance)); + lastPoint = point; + } + } + this.lineSegments[index] = + new Segment(lastPoint, firstPoint, new Line(lastPoint, firstPoint, tolerance)); + } + } + return lineSegments; + } + + /** {@inheritDoc} */ + public Region<Euclidean2D> createRegion() throws InsufficientDataException { + if (vertices.length < 3) { + throw new InsufficientDataException(); + } + final RegionFactory<Euclidean2D> factory = new RegionFactory<Euclidean2D>(); + final Segment[] segments = retrieveLineSegments(); + final Line[] lineArray = new Line[segments.length]; + for (int i = 0; i < segments.length; i++) { + lineArray[i] = segments[i].getLine(); + } + return factory.buildConvex(lineArray); + } +} diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2D.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2D.java new file mode 100644 index 0000000..3e13e1a --- /dev/null +++ b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2D.java @@ -0,0 +1,37 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math3.geometry.euclidean.twod.hull; + +import java.util.Collection; + +import org.apache.commons.math3.exception.ConvergenceException; +import org.apache.commons.math3.exception.NullArgumentException; +import org.apache.commons.math3.geometry.euclidean.twod.Euclidean2D; +import org.apache.commons.math3.geometry.euclidean.twod.Vector2D; +import org.apache.commons.math3.geometry.hull.ConvexHullGenerator; + +/** + * Interface for convex hull generators in the two-dimensional euclidean space. + * + * @since 3.3 + */ +public interface ConvexHullGenerator2D extends ConvexHullGenerator<Euclidean2D, Vector2D> { + + /** {@inheritDoc} */ + ConvexHull2D generate(Collection<Vector2D> points) throws NullArgumentException, ConvergenceException; + +} diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java new file mode 100644 index 0000000..4421344 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java @@ -0,0 +1,181 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.commons.math3.geometry.euclidean.twod.hull; + +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.Comparator; +import java.util.List; + +import org.apache.commons.math3.geometry.euclidean.twod.Line; +import org.apache.commons.math3.geometry.euclidean.twod.Vector2D; +import org.apache.commons.math3.util.FastMath; +import org.apache.commons.math3.util.Precision; + +/** + * Implements Andrew's monotone chain method to generate the convex hull of a finite set of + * points in the two-dimensional euclidean space. + * <p> + * The runtime complexity is O(n log n), with n being the number of input points. If the + * point set is already sorted (by x-coordinate), the runtime complexity is O(n). + * <p> + * The implementation is not sensitive to collinear points on the hull. The parameter + * {@code includeCollinearPoints} allows to control the behavior with regard to collinear points. + * If {@code true}, all points on the boundary of the hull will be added to the hull vertices, + * otherwise only the extreme points will be present. By default, collinear points are not added + * as hull vertices. + * <p> + * The {@code tolerance} parameter (default: 1e-10) is used as epsilon criteria to determine + * identical and collinear points. + * + * @see <a href="http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain"> + * Andrew's monotone chain algorithm (Wikibooks)</a> + * @since 3.3 + */ +public class MonotoneChain extends AbstractConvexHullGenerator2D { + + /** + * Create a new MonotoneChain instance. + */ + public MonotoneChain() { + this(false); + } + + /** + * Create a new MonotoneChain instance. + * @param includeCollinearPoints whether collinear points shall be added as hull vertices + */ + public MonotoneChain(final boolean includeCollinearPoints) { + super(includeCollinearPoints); + } + + /** + * Create a new MonotoneChain instance. + * @param includeCollinearPoints whether collinear points shall be added as hull vertices + * @param tolerance tolerance below which points are considered identical + */ + public MonotoneChain(final boolean includeCollinearPoints, final double tolerance) { + super(includeCollinearPoints, tolerance); + } + + /** {@inheritDoc} */ + @Override + public Collection<Vector2D> findHullVertices(final Collection<Vector2D> points) { + + final List<Vector2D> pointsSortedByXAxis = new ArrayList<Vector2D>(points); + + // sort the points in increasing order on the x-axis + Collections.sort(pointsSortedByXAxis, new Comparator<Vector2D>() { + /** {@inheritDoc} */ + public int compare(final Vector2D o1, final Vector2D o2) { + final double tolerance = getTolerance(); + // need to take the tolerance value into account, otherwise collinear points + // will not be handled correctly when building the upper/lower hull + final int diff = Precision.compareTo(o1.getX(), o2.getX(), tolerance); + if (diff == 0) { + return Precision.compareTo(o1.getY(), o2.getY(), tolerance); + } else { + return diff; + } + } + }); + + // build lower hull + final List<Vector2D> lowerHull = new ArrayList<Vector2D>(); + for (Vector2D p : pointsSortedByXAxis) { + updateHull(p, lowerHull); + } + + // build upper hull + final List<Vector2D> upperHull = new ArrayList<Vector2D>(); + for (int idx = pointsSortedByXAxis.size() - 1; idx >= 0; idx--) { + final Vector2D p = pointsSortedByXAxis.get(idx); + updateHull(p, upperHull); + } + + // concatenate the lower and upper hulls + // the last point of each list is omitted as it is repeated at the beginning of the other list + final List<Vector2D> hullVertices = new ArrayList<Vector2D>(lowerHull.size() + upperHull.size() - 2); + for (int idx = 0; idx < lowerHull.size() - 1; idx++) { + hullVertices.add(lowerHull.get(idx)); + } + for (int idx = 0; idx < upperHull.size() - 1; idx++) { + hullVertices.add(upperHull.get(idx)); + } + + // special case: if the lower and upper hull may contain only 1 point if all are identical + if (hullVertices.isEmpty() && ! lowerHull.isEmpty()) { + hullVertices.add(lowerHull.get(0)); + } + + return hullVertices; + } + + /** + * Update the partial hull with the current point. + * + * @param point the current point + * @param hull the partial hull + */ + private void updateHull(final Vector2D point, final List<Vector2D> hull) { + final double tolerance = getTolerance(); + + if (hull.size() == 1) { + // ensure that we do not add an identical point + final Vector2D p1 = hull.get(0); + if (p1.distance(point) < tolerance) { + return; + } + } + + while (hull.size() >= 2) { + final int size = hull.size(); + final Vector2D p1 = hull.get(size - 2); + final Vector2D p2 = hull.get(size - 1); + + final double offset = new Line(p1, p2, tolerance).getOffset(point); + if (FastMath.abs(offset) < tolerance) { + // the point is collinear to the line (p1, p2) + + final double distanceToCurrent = p1.distance(point); + if (distanceToCurrent < tolerance || p2.distance(point) < tolerance) { + // the point is assumed to be identical to either p1 or p2 + return; + } + + final double distanceToLast = p1.distance(p2); + if (isIncludeCollinearPoints()) { + final int index = distanceToCurrent < distanceToLast ? size - 1 : size; + hull.add(index, point); + } else { + if (distanceToCurrent > distanceToLast) { + hull.remove(size - 1); + hull.add(point); + } + } + return; + } else if (offset > 0) { + hull.remove(size - 1); + } else { + break; + } + } + hull.add(point); + } + +} diff --git a/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/package-info.java b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/package-info.java new file mode 100644 index 0000000..d0469a4 --- /dev/null +++ b/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/package-info.java @@ -0,0 +1,25 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** + * + * <p> + * This package provides algorithms to generate the convex hull + * for a set of points in an two-dimensional euclidean space. + * </p> + * + */ +package org.apache.commons.math3.geometry.euclidean.twod.hull; |