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/01/30 22:28:06 UTC
svn commit: r1562975 - 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 Jan 30 21:28:05 2014
New Revision: 1562975
URL: http://svn.apache.org/r1562975
Log:
[MATH-749] Fix GrahamScan2D for colinear points, improve tests.
Modified:
commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScan2D.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/GrahamScan2DTest.java
Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScan2D.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScan2D.java?rev=1562975&r1=1562974&r2=1562975&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScan2D.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScan2D.java Thu Jan 30 21:28:05 2014
@@ -28,11 +28,13 @@ import org.apache.commons.math3.geometry
import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
import org.apache.commons.math3.util.FastMath;
import org.apache.commons.math3.util.MathUtils;
-import org.apache.commons.math3.util.Precision;
/**
* 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 colinear points. The runtime complexity
+ * is O(n log n), with n being the number of input points.
*
* @see <a href="http://en.wikipedia.org/wiki/Graham_scan">Graham's scan algorithm (Wikipedia)</a>
* @since 3.3
@@ -91,30 +93,26 @@ public class GrahamScan2D implements Con
});
// list containing the vertices of the hull in ccw direction
- final List<Vector2D> hull = new ArrayList<Vector2D>(points.size());
+ final List<Vector2D> hullVertices = new ArrayList<Vector2D>(points.size());
// push the first two points on the stack
final Iterator<Vertex> it = pointsSortedByAngle.iterator();
- hull.add(it.next().point);
- hull.add(it.next().point);
+ hullVertices.add(it.next().point);
+ hullVertices.add(it.next().point);
Vector2D currentPoint = null;
while (it.hasNext() || currentPoint != null) {
- // if only one point is on the stack, push the current point to form a line segment
- final int size = hull.size();
+ // push the current point to form a line segment if there is only one element
+ final int size = hullVertices.size();
if (size == 1) {
- if (it.hasNext()) {
- hull.add(it.next().point);
- } else {
- hull.add(currentPoint);
- currentPoint = null;
- }
+ hullVertices.add(currentPoint != null ? currentPoint : it.next().point);
+ currentPoint = null;
continue;
}
// get the last line segment of the current convex hull
- final Vector2D p1 = hull.get(size - 2);
- final Vector2D p2 = hull.get(size - 1);
+ 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) {
@@ -125,21 +123,17 @@ public class GrahamScan2D implements Con
final double offset = line.getOffset(currentPoint);
if (offset < 0.0) {
- hull.add(currentPoint);
+ // the current point forms a convex section
+ hullVertices.add(currentPoint);
currentPoint = null;
} else {
- // in case the new point is on the line segment, discard it
- if (Precision.equals(offset, 0.0, tolerance)) {
- currentPoint = null;
- } else {
- // otherwise, we need to discard the last point of the current
- // hull, as the current point would create a concave section.
- hull.remove(size - 1);
- }
+ // otherwise, the point is either colinear or will create
+ // a concave section, thus we need to remove the last point.
+ hullVertices.remove(size - 1);
}
}
- return new ConvexHull2D(hull, tolerance);
+ return new ConvexHull2D(hullVertices, tolerance);
}
/**
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=1562975&r1=1562974&r2=1562975&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 Jan 30 21:28:05 2014
@@ -26,6 +26,8 @@ import org.apache.commons.math3.geometry
import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
import org.apache.commons.math3.geometry.partitioning.Region;
import org.apache.commons.math3.geometry.partitioning.Region.Location;
+import org.apache.commons.math3.random.MersenneTwister;
+import org.apache.commons.math3.random.RandomGenerator;
import org.apache.commons.math3.util.FastMath;
import org.junit.Assert;
import org.junit.Before;
@@ -39,12 +41,14 @@ import org.junit.Test;
public abstract class ConvexHullGenerator2DAbstractTest {
protected ConvexHullGenerator2D generator;
+ protected RandomGenerator random;
protected abstract ConvexHullGenerator2D createConvexHullGenerator();
@Before
public void setUp() {
generator = createConvexHullGenerator();
+ random = new MersenneTwister(10);
}
// ------------------------------------------------------------------------------
@@ -79,16 +83,15 @@ public abstract class ConvexHullGenerato
@Test
public void testConvexHull() {
- // randomize the size from 4 to 100
- int size = (int) FastMath.floor(FastMath.random() * 96.0 + 4.0);
-
- List<Vector2D> points = createRandomPoints(size);
-
- ConvexHull2D hull = generator.generate(points);
-
- Assert.assertNotNull(hull);
- Assert.assertTrue(isConvex(hull));
- checkPointsInsideHullRegion(points, hull);
+ // execute 100 random variations
+ for (int i = 0; i < 100; i++) {
+ // randomize the size from 4 to 100
+ int size = (int) FastMath.floor(random.nextDouble() * 96.0 + 4.0);
+
+ List<Vector2D> points = createRandomPoints(size);
+ ConvexHull2D hull = generator.generate(points);
+ checkConvexHull(points, hull);
+ }
}
// ------------------------------------------------------------------------------
@@ -98,11 +101,17 @@ public abstract class ConvexHullGenerato
List<Vector2D> points = new ArrayList<Vector2D>(size);
// fill the cloud with a random distribution of points
for (int i = 0; i < size; i++) {
- points.add(new Vector2D(FastMath.random() * 2.0 - 1.0, FastMath.random() * 2.0 - 1.0));
+ points.add(new Vector2D(random.nextDouble() * 2.0 - 1.0, random.nextDouble() * 2.0 - 1.0));
}
return points;
}
+ protected final void checkConvexHull(final Collection<Vector2D> points, final ConvexHull2D hull) {
+ Assert.assertNotNull(hull);
+ Assert.assertTrue(isConvex(hull));
+ checkPointsInsideHullRegion(points, hull);
+ }
+
// verify that the constructed hull is really convex
protected final boolean isConvex(final ConvexHull2D hull) {
double sign = 0.0;
Modified: commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScan2DTest.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScan2DTest.java?rev=1562975&r1=1562974&r2=1562975&view=diff
==============================================================================
--- commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScan2DTest.java (original)
+++ commons/proper/math/trunk/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/GrahamScan2DTest.java Thu Jan 30 21:28:05 2014
@@ -19,13 +19,9 @@ package org.apache.commons.math3.geometr
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
-import java.util.StringTokenizer;
import org.apache.commons.math3.geometry.euclidean.twod.Vector2D;
-import org.apache.commons.math3.geometry.euclidean.twod.Vector2DFormat;
import org.apache.commons.math3.geometry.euclidean.twod.hull.GrahamScan2D;
-import org.junit.Assert;
-import org.junit.Ignore;
import org.junit.Test;
/**
@@ -41,43 +37,43 @@ public class GrahamScan2DTest extends Co
// ------------------------------------------------------------------------------
@Test
- @Ignore // need to fix the case of points on a line
- public void testMultiplePointsWithSameYCoordinate() {
- Collection<Vector2D> points = new ArrayList<Vector2D>();
+ public void testColinearPoints() {
+ 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));
- ConvexHull2D hull = generator.generate(points);
- Assert.assertTrue(isConvex(hull));
- checkPointsInsideHullRegion(points, hull);
+ final ConvexHull2D hull = generator.generate(points);
+ checkConvexHull(points, hull);
}
@Test
- public void testBug() {
-
- String input = "{0.7886552422; 0.8629523066}{-0.477657659; -0.818633147}{-0.9778256822; 0.4459975439}" +
- "{0.9967680357; -0.7956341096}{-0.6644522529; 0.5722968681}{-0.9769155504; 0.2676854695}" +
- "{0.2378256814; -0.0546758337}{-0.3094786038; -0.4877828777}{0.4700714363; 0.2338673804}" +
- "{0.1172690966; -0.5931228134}{-0.8863820898; 0.630175898}{0.9967680357; -0.7956341096}" +
- "{0.5974682835; 0.5581237347}{0.0670101247; 0.523515029}{-0.0534546034; -0.608353757}" +
- "{-0.3527909285; 0.4330755698}{0.6524149298; -0.6353437037}{-0.7189115058; -0.3074849638}";
-
+ public void testIdenticalPoints() {
final List<Vector2D> points = new ArrayList<Vector2D>();
- final StringTokenizer st = new StringTokenizer(input, "{", false);
- while (st.hasMoreTokens()) {
- String token = st.nextToken();
- Vector2D point = Vector2DFormat.getInstance().parse("{" + token);
- points.add(point);
- }
-
- GrahamScan2D generator = new GrahamScan2D();
- ConvexHull2D hull = generator.generate(points);
- Assert.assertTrue(isConvex(hull));
- checkPointsInsideHullRegion(points, hull);
+ points.add(new Vector2D(0.7886552422, 0.8629523066));
+ points.add(new Vector2D(-0.477657659, -0.818633147));
+ points.add(new Vector2D(-0.9778256822, 0.4459975439));
+ points.add(new Vector2D(0.9967680357, -0.7956341096));
+ points.add(new Vector2D(-0.6644522529, 0.5722968681));
+ points.add(new Vector2D(-0.9769155504, 0.2676854695));
+ points.add(new Vector2D(0.2378256814, -0.0546758337));
+ points.add(new Vector2D(-0.3094786038, -0.4877828777));
+ points.add(new Vector2D(0.4700714363, 0.2338673804));
+ points.add(new Vector2D(0.1172690966, -0.5931228134));
+ points.add(new Vector2D(-0.8863820898, 0.630175898));
+ points.add(new Vector2D(0.9967680357, -0.7956341096));
+ points.add(new Vector2D(0.5974682835, 0.5581237347));
+ points.add(new Vector2D(0.0670101247, 0.523515029));
+ points.add(new Vector2D(-0.0534546034, -0.608353757));
+ points.add(new Vector2D(-0.3527909285, 0.4330755698));
+ points.add(new Vector2D(0.6524149298, -0.6353437037));
+ points.add(new Vector2D(-0.7189115058, -0.3074849638));
+
+ final ConvexHull2D hull = generator.generate(points);
+ checkConvexHull(points, hull);
}
}