commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject 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/
Date Thu, 06 Feb 2014 21:27:20 GMT
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) {



Mime
View raw message