Mailing-List: contact commits-help@commons.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@commons.apache.org
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: svn commit: r1564934 - 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: Wed, 05 Feb 2014 21:21:32 -0000
To: commits@commons.apache.org
From: tn@apache.org
Message-Id: <20140205212132.9A8BF2388993@eris.apache.org>

Author: tn
Date: Wed Feb  5 21:21:31 2014
New Revision: 1564934

URL: http://svn.apache.org/r1564934
Log:
[MATH-749] Improve robustness for convex hull algorithms in case of identical / collinear points, added flag whether to include only extreme points or all points on the hull, improve unit tests.

Added:
    commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AbstractConvexHullGenerator2D.java   (with props)
Modified:
    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/AklToussaintHeuristicTest.java
    commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java
    commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScanTest.java
    commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChainTest.java

Added: 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=1564934&view=auto
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AbstractConvexHullGenerator2D.java (added)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AbstractConvexHullGenerator2D.java Wed Feb  5 21:21:31 2014
@@ -0,0 +1,129 @@
+/*
+ * 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.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;
+import org.apache.commons.math3.util.MathUtils;
+
+/**
+ * Abstract base class for convex hull generators in the two-dimensional euclidean space.
+ *
+ * @since 3.3
+ * @version $Id$
+ */
+public 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>
+     * 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
+     * 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 {
+        // 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) {
+            return new ConvexHull2D(points, tolerance);
+        }
+
+        final Collection<Vector2D> hullVertices = generateHull(points);
+        return new ConvexHull2D(hullVertices, tolerance);
+    }
+
+    /**
+     * Compute 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);
+
+}

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AbstractConvexHullGenerator2D.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AbstractConvexHullGenerator2D.java
------------------------------------------------------------------------------
    svn:keywords = Id Revision HeadURL

Propchange: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AbstractConvexHullGenerator2D.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

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=1564934&r1=1564933&r2=1564934&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 Wed Feb  5 21:21:31 2014
@@ -23,11 +23,8 @@ import java.util.Comparator;
 import java.util.Iterator;
 import java.util.List;
 
-import org.apache.commons.math3.exception.NullArgumentException;
-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.MathUtils;
 
 /**
  * Implements Graham's scan method to generate the convex hull of a finite set of
@@ -40,47 +37,50 @@ import org.apache.commons.math3.util.Mat
  * @since 3.3
  * @version $Id$
  */
-public class GrahamScan implements ConvexHullGenerator2D {
-
-    /** Default value for tolerance. */
-    private static final double DEFAULT_TOLERANCE = 1e-10;
+public class GrahamScan extends AbstractConvexHullGenerator2D {
 
     /** Vector representing the x-axis. */
     private static final Vector2D X_AXIS = new Vector2D(1.0, 0.0);
 
-    /** Tolerance below which points are considered identical. */
-    private final double tolerance;
+    /**
+     * 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();
+    }
 
     /**
-     * Creates a new instance.
+     * 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
      */
-    public GrahamScan() {
-        this(DEFAULT_TOLERANCE);
+    public GrahamScan(final boolean includeCollinearPoints) {
+        super(includeCollinearPoints);
     }
 
     /**
-     * Creates a new instance with the given tolerance for determining identical points.
+     * Create a new GrahamScan instance.
+     *
+     * @param includeCollinearPoints indicates if collinear points on the hull shall be
+     * added as hull vertices
      * @param tolerance tolerance below which points are considered identical
      */
-    public GrahamScan(final double tolerance) {
-        this.tolerance = tolerance;
+    public GrahamScan(final boolean includeCollinearPoints, final double tolerance) {
+        super(includeCollinearPoints, tolerance);
     }
 
-    /** {@inheritDoc} */
-    public ConvexHull2D generate(final Collection<Vector2D> points) throws NullArgumentException {
-
-        // check for null points
-        MathUtils.checkNotNull(points);
-
-        if (points.size() < 3) {
-            return new ConvexHull2D(points, tolerance);
-        }
+    @Override
+    protected Collection<Vector2D> generateHull(final Collection<Vector2D> points) {
 
         final Vector2D referencePoint = getReferencePoint(points);
 
-        final List<Vertex> pointsSortedByAngle = new ArrayList<Vertex>();
+        final List<Vertex> pointsSortedByAngle = new ArrayList<Vertex>(points.size());
         for (final Vector2D p : points) {
             pointsSortedByAngle.add(new Vertex(p, getAngleBetweenPoints(p, referencePoint)));
         }
@@ -92,13 +92,22 @@ public class GrahamScan implements Conve
             }
         });
 
-        // list containing the vertices of the hull in ccw direction
-        final List<Vector2D> hullVertices = new ArrayList<Vector2D>(points.size());
+        // list containing the vertices of the hull in CCW direction
+        final List<Vector2D> hullVertices = new ArrayList<Vector2D>();
 
         // push the first two points on the stack
         final Iterator<Vertex> it = pointsSortedByAngle.iterator();
-        hullVertices.add(it.next().point);
-        hullVertices.add(it.next().point);
+        final Vector2D firstPoint = it.next().point;
+        hullVertices.add(firstPoint);
+
+        final double tolerance = getTolerance();
+        // ensure that we do not add an identical point
+        while(hullVertices.size() < 2 && it.hasNext()) {
+            final Vector2D p = it.next().point;
+            if (firstPoint.distance(p) >= tolerance) {
+                hullVertices.add(p);
+            }
+        }
 
         Vector2D currentPoint = null;
         while (it.hasNext() || currentPoint != null) {
@@ -113,27 +122,47 @@ public class GrahamScan implements Conve
             // get the last line segment of the current convex hull
             final Vector2D p1 = hullVertices.get(size - 2);
             final Vector2D p2 = hullVertices.get(size - 1);
-            final Line line = new Line(p1, p2, tolerance);
 
             if (currentPoint == null) {
                 currentPoint = it.next().point;
             }
 
             // test if the current point is to the left of the line
-            final double offset = line.getOffset(currentPoint);
+            final double offset = currentPoint.crossProduct(p1, p2);
+
+            if (FastMath.abs(offset) < tolerance) {
+                // the point is collinear to the line (p1, p2)
 
-            if (offset < 0.0) {
-                // the current point forms a convex section
+                final double distanceToCurrent = p1.distance(currentPoint);
+                if (distanceToCurrent < tolerance || p2.distance(currentPoint) < tolerance) {
+                    // the point is assumed to be identical to either p1 or p2
+                    currentPoint = null;
+                    continue;
+                }
+
+                final double distanceToLast = p1.distance(p2);
+                if (isIncludeCollinearPoints()) {
+                    final int index = distanceToCurrent < distanceToLast ? size - 1 : size;
+                    hullVertices.add(index, currentPoint);
+                    currentPoint = null;
+                } else {
+                    if (distanceToCurrent > distanceToLast) {
+                        hullVertices.remove(size - 1);
+                    } else {
+                        currentPoint = null;
+                    }
+                }
+            } else if (offset > 0.0) {
+                // the current point forms a convex polygon
                 hullVertices.add(currentPoint);
                 currentPoint = null;
             } else {
-                // otherwise, the point is either collinear or will create
-                // a concave section, thus we need to remove the last point.
+                // the current point creates a concave polygon, remove the last point
                 hullVertices.remove(size - 1);
             }
         }
 
-        return new ConvexHull2D(hullVertices, tolerance);
+        return hullVertices;
     }
 
     /**
@@ -145,7 +174,7 @@ public class GrahamScan implements Conve
      * @param points the point set
      * @return the point with the lowest y-coordinate
      */
-    private Vector2D getReferencePoint(final Collection<Vector2D> points) {
+    private Vector2D getReferencePoint(final Iterable<Vector2D> points) {
         Vector2D minY = null;
         for (final Vector2D p : points) {
             if (minY == null) {

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=1564934&r1=1564933&r2=1564934&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 Wed Feb  5 21:21:31 2014
@@ -22,10 +22,8 @@ import java.util.Collections;
 import java.util.Comparator;
 import java.util.List;
 
-import org.apache.commons.math3.exception.NullArgumentException;
 import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
 import org.apache.commons.math3.util.FastMath;
-import org.apache.commons.math3.util.MathUtils;
 
 /**
  * Implements Andrew's monotone chain method to generate the convex hull of a finite set of
@@ -40,40 +38,43 @@ import org.apache.commons.math3.util.Mat
  * @since 3.3
  * @version $Id$
  */
-public class MonotoneChain implements ConvexHullGenerator2D {
+public class MonotoneChain extends AbstractConvexHullGenerator2D {
 
-    /** Default value for tolerance. */
-    private static final double DEFAULT_TOLERANCE = 1e-10;
-
-    /** Tolerance below which points are considered identical. */
-    private final double tolerance;
+    /**
+     * 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();
+    }
 
     /**
-     * Creates a new instance.
+     * 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
      */
-    public MonotoneChain() {
-        this(DEFAULT_TOLERANCE);
+    public MonotoneChain(final boolean includeCollinearPoints) {
+        super(includeCollinearPoints);
     }
 
     /**
-     * Creates a new instance with the given tolerance for determining identical points.
+     * Create a new MonotoneChain instance.
+     *
+     * @param includeCollinearPoints indicates if collinear points on the hull shall be
+     * added as hull vertices
      * @param tolerance tolerance below which points are considered identical
      */
-    public MonotoneChain(final double tolerance) {
-        this.tolerance = tolerance;
+    public MonotoneChain(final boolean includeCollinearPoints, final double tolerance) {
+        super(includeCollinearPoints, tolerance);
     }
 
-    /** {@inheritDoc} */
-    public ConvexHull2D generate(final Collection<Vector2D> points) throws NullArgumentException {
-
-        // check for null points
-        MathUtils.checkNotNull(points);
-
-        if (points.size() < 3) {
-            return new ConvexHull2D(points, tolerance);
-        }
+    @Override
+    public Collection<Vector2D> generateHull(final Collection<Vector2D> points) {
 
         final List<Vector2D> pointsSortedByXAxis = new ArrayList<Vector2D>(points);
 
@@ -92,41 +93,19 @@ public class MonotoneChain implements Co
         // build lower hull
         final List<Vector2D> lowerHull = new ArrayList<Vector2D>();
         for (Vector2D p : pointsSortedByXAxis) {
-            while (lowerHull.size() >= 2) {
-                final int size = lowerHull.size();
-                final Vector2D p1 = lowerHull.get(size - 2);
-                final Vector2D p2 = lowerHull.get(size - 1);
-
-                if (p.crossProduct(p1, p2) <= 0) {
-                    lowerHull.remove(size - 1);
-                } else {
-                    break;
-                }
-            }
-            lowerHull.add(p);
+            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);
-            while (upperHull.size() >= 2) {
-                final int size = upperHull.size();
-                final Vector2D p1 = upperHull.get(size - 2);
-                final Vector2D p2 = upperHull.get(size - 1);
-
-                if (p.crossProduct(p1, p2) <= 0) {
-                    upperHull.remove(size - 1);
-                } else {
-                    break;
-                }
-            }
-            upperHull.add(p);
+            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
-        List<Vector2D> hullVertices = new ArrayList<Vector2D>(lowerHull.size() + upperHull.size() - 2);
+        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));
         }
@@ -134,7 +113,60 @@ public class MonotoneChain implements Co
             hullVertices.add(upperHull.get(idx));
         }
 
-        return new ConvexHull2D(hullVertices, tolerance);
+        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 = point.crossProduct(p1, p2);
+
+            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);
     }
 
 }

Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AklToussaintHeuristicTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AklToussaintHeuristicTest.java?rev=1564934&r1=1564933&r2=1564934&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AklToussaintHeuristicTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/AklToussaintHeuristicTest.java Wed Feb  5 21:21:31 2014
@@ -27,8 +27,8 @@ import org.apache.commons.math3.geometry
 public class AklToussaintHeuristicTest extends ConvexHullGenerator2DAbstractTest {
 
     @Override
-    protected ConvexHullGenerator2D createConvexHullGenerator() {
-        return new GrahamScan();
+    protected ConvexHullGenerator2D createConvexHullGenerator(boolean includeCollinearPoints) {
+        return new GrahamScan(includeCollinearPoints);
     }
 
     @Override

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=1564934&r1=1564933&r2=1564934&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 Wed Feb  5 21:21:31 2014
@@ -17,6 +17,7 @@
 package org.apache.commons.math3.geometry.euclidean.twod.hull;
 
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
@@ -43,7 +44,7 @@ public abstract class ConvexHullGenerato
     protected ConvexHullGenerator2D generator;
     protected RandomGenerator random;
 
-    protected abstract ConvexHullGenerator2D createConvexHullGenerator();
+    protected abstract ConvexHullGenerator2D createConvexHullGenerator(boolean includeCollinearPoints);
 
     protected Collection<Vector2D> reducePoints(Collection<Vector2D> points) {
         // do nothing by default, may be overridden by other tests
@@ -52,7 +53,7 @@ public abstract class ConvexHullGenerato
 
     @Before
     public void setUp() {
-        generator = createConvexHullGenerator();
+        generator = createConvexHullGenerator(false);
         random = new MersenneTwister(10);
     }
 
@@ -100,7 +101,7 @@ public abstract class ConvexHullGenerato
     }
 
     @Test
-    public void testColinearPoints() {
+    public void testCollinearPoints() {
         final Collection<Vector2D> points = new ArrayList<Vector2D>();
         points.add(new Vector2D(1, 1));
         points.add(new Vector2D(2, 2));
@@ -112,6 +113,84 @@ public abstract class ConvexHullGenerato
         checkConvexHull(points, hull);
     }
 
+    @Test
+    public void testCollinearPointsReverse() {
+        final Collection<Vector2D> points = new ArrayList<Vector2D>();
+        points.add(new Vector2D(1, 1));
+        points.add(new Vector2D(2, 2));
+        points.add(new Vector2D(2, 4));
+        points.add(new Vector2D(10, 1));
+        points.add(new Vector2D(4, 1));
+
+        final ConvexHull2D hull = generator.generate(points);
+        checkConvexHull(points, hull);
+    }
+
+    @Test
+    public void testCollinearPointsIncluded() {
+        final Collection<Vector2D> points = new ArrayList<Vector2D>();
+        points.add(new Vector2D(1, 1));
+        points.add(new Vector2D(2, 2));
+        points.add(new Vector2D(2, 4));
+        points.add(new Vector2D(4, 1));
+        points.add(new Vector2D(10, 1));
+
+        final ConvexHull2D hull = createConvexHullGenerator(true).generate(points);
+        checkConvexHull(points, hull, true);
+    }
+
+    @Test
+    public void testCollinearPointsIncludedReverse() {
+        final Collection<Vector2D> points = new ArrayList<Vector2D>();
+        points.add(new Vector2D(1, 1));
+        points.add(new Vector2D(2, 2));
+        points.add(new Vector2D(2, 4));
+        points.add(new Vector2D(10, 1));
+        points.add(new Vector2D(4, 1));
+
+        final ConvexHull2D hull = createConvexHullGenerator(true).generate(points);
+        checkConvexHull(points, hull, true);
+    }
+
+    @Test
+    public void testIdenticalPoints() {
+        final Collection<Vector2D> points = new ArrayList<Vector2D>();
+        points.add(new Vector2D(1, 1));
+        points.add(new Vector2D(2, 2));
+        points.add(new Vector2D(2, 4));
+        points.add(new Vector2D(4, 1));
+        points.add(new Vector2D(1, 1));
+
+        final ConvexHull2D hull = generator.generate(points);
+        checkConvexHull(points, hull);
+    }
+
+    @Test
+    public void testIdenticalPoints2() {
+        final Collection<Vector2D> points = new ArrayList<Vector2D>();
+        points.add(new Vector2D(1, 1));
+        points.add(new Vector2D(2, 2));
+        points.add(new Vector2D(2, 4));
+        points.add(new Vector2D(4, 1));
+        points.add(new Vector2D(1, 1));
+
+        final ConvexHull2D hull = createConvexHullGenerator(true).generate(points);
+        checkConvexHull(points, hull, true);
+    }
+
+    @Test
+    public void testClosePoints() {
+        final Collection<Vector2D> points = new ArrayList<Vector2D>();
+        points.add(new Vector2D(1, 1));
+        points.add(new Vector2D(2, 2));
+        points.add(new Vector2D(2, 4));
+        points.add(new Vector2D(4, 1));
+        points.add(new Vector2D(1.00001, 1));
+
+        final ConvexHull2D hull = generator.generate(points);
+        checkConvexHull(points, hull);
+    }
+
     // ------------------------------------------------------------------------------
     
     protected final List<Vector2D> createRandomPoints(int size) {
@@ -123,15 +202,20 @@ public abstract class ConvexHullGenerato
         }
         return points;
     }
-    
+
     protected final void checkConvexHull(final Collection<Vector2D> points, final ConvexHull2D hull) {
+        checkConvexHull(points, hull, false);
+    }
+
+    protected final void checkConvexHull(final Collection<Vector2D> points, final ConvexHull2D hull,
+                                         final boolean includesCollinearPoints) {
         Assert.assertNotNull(hull);
-        Assert.assertTrue(isConvex(hull));
-        checkPointsInsideHullRegion(points, hull);
+        Assert.assertTrue(isConvex(hull, includesCollinearPoints));
+        checkPointsInsideHullRegion(points, hull, includesCollinearPoints);
     }
 
     // verify that the constructed hull is really convex
-    protected final boolean isConvex(final ConvexHull2D hull) {
+    protected final boolean isConvex(final ConvexHull2D hull, final boolean includesCollinearPoints) {
         double sign = 0.0;
 
         final Vector2D[] points = hull.getVertices();
@@ -142,11 +226,18 @@ public abstract class ConvexHullGenerato
 
             Vector2D d1 = p2.subtract(p1);
             Vector2D d2 = p3.subtract(p2);
-                
+
+            Assert.assertTrue(d1.getNorm() > 1e-10);
+            Assert.assertTrue(d2.getNorm() > 1e-10);
+
             double cross = FastMath.signum(d1.getX() * d2.getY() - d1.getY() * d2.getX());
 
             if (sign != 0.0 && cross != sign) {
-                return false;
+                if (includesCollinearPoints && cross == 0.0) {
+                    // in case of collinear points the cross product will be zero
+                } else {
+                    return false;
+                }
             }
             
             sign = cross;
@@ -157,13 +248,19 @@ public abstract class ConvexHullGenerato
     
     // verify that all points are inside the convex hull region
     protected final void checkPointsInsideHullRegion(final Collection<Vector2D> points,
-                                                     final ConvexHull2D hull) {
+                                                     final ConvexHull2D hull,
+                                                     final boolean includesCollinearPoints) {
 
-        Region<Euclidean2D> region = hull.createRegion();
+        final Collection<Vector2D> hullVertices = Arrays.asList(hull.getVertices());
+        final Region<Euclidean2D> region = hull.createRegion();
 
         for (final Vector2D p : points) {
             Location location = region.checkPoint(p);
             Assert.assertTrue(location != Location.OUTSIDE);
+
+            if (location == Location.BOUNDARY && includesCollinearPoints) {
+                Assert.assertTrue(hullVertices.contains(p));
+            }
         }
     }
 }

Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScanTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScanTest.java?rev=1564934&r1=1564933&r2=1564934&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScanTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScanTest.java Wed Feb  5 21:21:31 2014
@@ -17,6 +17,7 @@
 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;
@@ -30,14 +31,14 @@ import org.junit.Test;
 public class GrahamScanTest extends ConvexHullGenerator2DAbstractTest {
 
     @Override
-    protected ConvexHullGenerator2D createConvexHullGenerator() {
-        return new GrahamScan();
+    protected ConvexHullGenerator2D createConvexHullGenerator(boolean includeCollinearPoints) {
+        return new GrahamScan(includeCollinearPoints);
     }
 
     // ------------------------------------------------------------------------------
 
     @Test
-    public void testIdenticalPoints() {
+    public void testIdenticalPointsRandom() {
         final List<Vector2D> points = new ArrayList<Vector2D>();
 
         points.add(new Vector2D(0.7886552422, 0.8629523066));
@@ -62,5 +63,18 @@ public class GrahamScanTest extends Conv
         final ConvexHull2D hull = generator.generate(points);
         checkConvexHull(points, hull);
     }
-    
+
+    @Test
+    public void testIdenticalPointsAtStart() {
+        final Collection<Vector2D> points = new ArrayList<Vector2D>();
+        points.add(new Vector2D(1, 1));
+        points.add(new Vector2D(2, 2));
+        points.add(new Vector2D(2, 4));
+        points.add(new Vector2D(4, 1.5));
+        points.add(new Vector2D(1, 1));
+
+        final ConvexHull2D hull = createConvexHullGenerator(true).generate(points);
+        checkConvexHull(points, hull, true);
+    }
+
 }

Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChainTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChainTest.java?rev=1564934&r1=1564933&r2=1564934&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChainTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChainTest.java Wed Feb  5 21:21:31 2014
@@ -23,8 +23,8 @@ package org.apache.commons.math3.geometr
 public class MonotoneChainTest extends ConvexHullGenerator2DAbstractTest {
 
     @Override
-    protected ConvexHullGenerator2D createConvexHullGenerator() {
-        return new MonotoneChain();
+    protected ConvexHullGenerator2D createConvexHullGenerator(boolean includeCollinearPoints) {
+        return new MonotoneChain(includeCollinearPoints);
     }
 
     // ------------------------------------------------------------------------------