You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by tn...@apache.org on 2014/02/06 22:27:20 UTC
svn commit: r1565444 - in /commons/proper/math/trunk/src:
main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/
test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/
Author: tn
Date: Thu Feb 6 21:27:20 2014
New Revision: 1565444
URL: http://svn.apache.org/r1565444
Log:
[MATH-749] Rename method, add/improve javadoc, better handle degenerate cases, improve unit tests.
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AbstractConvexHullGenerator2D.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GiftWrap.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScan.java
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java
commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AbstractConvexHullGenerator2D.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AbstractConvexHullGenerator2D.java?rev=1565444&r1=1565443&r2=1565444&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AbstractConvexHullGenerator2D.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AbstractConvexHullGenerator2D.java Thu Feb 6 21:27:20 2014
@@ -16,9 +16,7 @@
*/
package org.apache.commons.math3.geometry.euclidean.twod.hull;
-import java.util.Arrays;
import java.util.Collection;
-import java.util.Iterator;
import org.apache.commons.math3.exception.NullArgumentException;
import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
@@ -47,16 +45,6 @@ public abstract class AbstractConvexHull
/**
* Simple constructor.
* <p>
- * Collinear points on the hull will not be added to the hull vertices and
- * {@code 1e-10} will be used as tolerance criteria for identical points.
- */
- protected AbstractConvexHullGenerator2D() {
- this(false, DEFAULT_TOLERANCE);
- }
-
- /**
- * 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
@@ -100,30 +88,19 @@ public abstract class AbstractConvexHull
// check for null points
MathUtils.checkNotNull(points);
- final int size = points.size();
- if (size == 2) {
- // special case: check that the two points are not identical
- final Iterator<Vector2D> it = points.iterator();
- final Vector2D firstPoint = it.next();
- final Vector2D secondPoint = it.next();
- if (firstPoint.distance(secondPoint) > tolerance) {
- return new ConvexHull2D(points, tolerance);
- } else {
- return new ConvexHull2D(Arrays.asList(firstPoint), tolerance);
- }
- } else if (size < 2) {
+ if (points.size() < 2) {
return new ConvexHull2D(points, tolerance);
}
- final Collection<Vector2D> hullVertices = generateHull(points);
+ final Collection<Vector2D> hullVertices = findHullVertices(points);
return new ConvexHull2D(hullVertices, tolerance);
}
/**
- * Compute the convex hull vertices from the set of input points.
+ * 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> generateHull(Collection<Vector2D> points);
+ protected abstract Collection<Vector2D> findHullVertices(Collection<Vector2D> points);
}
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GiftWrap.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GiftWrap.java?rev=1565444&r1=1565443&r2=1565444&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GiftWrap.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GiftWrap.java Thu Feb 6 21:27:20 2014
@@ -28,8 +28,17 @@ import org.apache.commons.math3.util.Fas
* Implements the Gift wrapping algorithm to generate the convex hull of a finite set of
* points in the two-dimensional euclidean space.
* <p>
- * The implementation is not sensitive to collinear points. The runtime complexity is O(nh),
- * with n being the number of input points and h the number of points on the convex hull.
+ * The runtime complexity is O(nh), with n being the number of input points and h the number
+ * of points on the convex hull.
+ * <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.wikipedia.org/wiki/Gift_wrapping_algorithm">Gift wrapping algorithm (Wikipedia)</a>
* @since 3.3
@@ -39,21 +48,14 @@ public class GiftWrap extends AbstractCo
/**
* Create a new GiftWrap instance.
- * <p>
- * Collinear points on the hull will not be added to the hull vertices and
- * {@code 1e-10} will be used as tolerance criteria for identical points.
*/
public GiftWrap() {
- super();
+ this(false);
}
/**
* Create a new GiftWrap instance.
- * <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
+ * @param includeCollinearPoints whether collinear points shall be added as hull vertices
*/
public GiftWrap(final boolean includeCollinearPoints) {
super(includeCollinearPoints);
@@ -61,9 +63,7 @@ public class GiftWrap extends AbstractCo
/**
* Create a new GiftWrap instance.
- *
- * @param includeCollinearPoints indicates if collinear points on the hull shall be
- * added as hull vertices
+ * @param includeCollinearPoints whether collinear points shall be added as hull vertices
* @param tolerance tolerance below which points are considered identical
*/
public GiftWrap(final boolean includeCollinearPoints, final double tolerance) {
@@ -71,7 +71,7 @@ public class GiftWrap extends AbstractCo
}
@Override
- public Collection<Vector2D> generateHull(final Collection<Vector2D> points) {
+ public Collection<Vector2D> findHullVertices(final Collection<Vector2D> points) {
final double tolerance = getTolerance();
final List<Vector2D> hullVertices = new ArrayList<Vector2D>();
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScan.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScan.java?rev=1565444&r1=1565443&r2=1565444&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScan.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScan.java Thu Feb 6 21:27:20 2014
@@ -30,8 +30,16 @@ import org.apache.commons.math3.util.Fas
* Implements Graham's scan method to generate the convex hull of a finite set of
* points in the two-dimensional euclidean space.
* <p>
- * The implementation is not sensitive to collinear points. The runtime complexity
- * is O(n log n), with n being the number of input points.
+ * The runtime complexity is O(n log h), with n being the number of input points.
+ * <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.wikipedia.org/wiki/Graham_scan">Graham's scan algorithm (Wikipedia)</a>
* @since 3.3
@@ -44,21 +52,14 @@ public class GrahamScan extends Abstract
/**
* Create a new GrahamScan instance.
- * <p>
- * Collinear points on the hull will not be added to the hull vertices and
- * {@code 1e-10} will be used as tolerance criteria for identical points.
*/
public GrahamScan() {
- super();
+ this(false);
}
/**
* Create a new GrahamScan instance.
- * <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
+ * @param includeCollinearPoints whether collinear points shall be added as hull vertices
*/
public GrahamScan(final boolean includeCollinearPoints) {
super(includeCollinearPoints);
@@ -66,9 +67,7 @@ public class GrahamScan extends Abstract
/**
* Create a new GrahamScan instance.
- *
- * @param includeCollinearPoints indicates if collinear points on the hull shall be
- * added as hull vertices
+ * @param includeCollinearPoints whether collinear points shall be added as hull vertices
* @param tolerance tolerance below which points are considered identical
*/
public GrahamScan(final boolean includeCollinearPoints, final double tolerance) {
@@ -76,7 +75,7 @@ public class GrahamScan extends Abstract
}
@Override
- protected Collection<Vector2D> generateHull(final Collection<Vector2D> points) {
+ protected Collection<Vector2D> findHullVertices(final Collection<Vector2D> points) {
final Vector2D referencePoint = getReferencePoint(points);
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java?rev=1565444&r1=1565443&r2=1565444&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java Thu Feb 6 21:27:20 2014
@@ -29,9 +29,17 @@ import org.apache.commons.math3.util.Fas
* 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 implementation is not sensitive to collinear points. 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).
+ * 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>
@@ -42,21 +50,14 @@ public class MonotoneChain extends Abstr
/**
* Create a new MonotoneChain instance.
- * <p>
- * Collinear points on the hull will not be added to the hull vertices and
- * {@code 1e-10} will be used as tolerance criteria for identical points.
*/
public MonotoneChain() {
- super();
+ this(false);
}
/**
* Create a new MonotoneChain instance.
- * <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
+ * @param includeCollinearPoints whether collinear points shall be added as hull vertices
*/
public MonotoneChain(final boolean includeCollinearPoints) {
super(includeCollinearPoints);
@@ -64,9 +65,7 @@ public class MonotoneChain extends Abstr
/**
* Create a new MonotoneChain instance.
- *
- * @param includeCollinearPoints indicates if collinear points on the hull shall be
- * added as hull vertices
+ * @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) {
@@ -74,7 +73,7 @@ public class MonotoneChain extends Abstr
}
@Override
- public Collection<Vector2D> generateHull(final Collection<Vector2D> points) {
+ public Collection<Vector2D> findHullVertices(final Collection<Vector2D> points) {
final List<Vector2D> pointsSortedByXAxis = new ArrayList<Vector2D>(points);
@@ -113,6 +112,11 @@ public class MonotoneChain extends Abstr
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;
}
Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java?rev=1565444&r1=1565443&r2=1565444&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java Thu Feb 6 21:27:20 2014
@@ -96,7 +96,7 @@ public abstract class ConvexHullGenerato
points.add(new Vector2D(1, 1));
final ConvexHull2D hull = generator.generate(points);
- checkConvexHull(points, hull);
+ Assert.assertTrue(hull.getVertices().length == 1);
}
@Test
@@ -231,9 +231,9 @@ public abstract class ConvexHullGenerato
double sign = 0.0;
final Vector2D[] points = hull.getVertices();
- if (points.length < 3) {
- return true;
- }
+// if (points.length < 3) {
+// return true;
+// }
for (int i = 0; i < points.length; i++) {
Vector2D p1 = points[i == 0 ? points.length - 1 : i - 1];
@@ -268,9 +268,9 @@ public abstract class ConvexHullGenerato
final boolean includesCollinearPoints) {
final Collection<Vector2D> hullVertices = Arrays.asList(hull.getVertices());
- if (hullVertices.size() < 3) {
- return;
- }
+// if (hullVertices.size() < 3) {
+// return;
+// }
final Region<Euclidean2D> region = hull.createRegion();
for (final Vector2D p : points) {