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/09/29 18:26:24 UTC
git commit: [MATH-1148] Fix MonotoneChain with collinear points as
input: take tolerance factor into account when initially sorting the input
points. Thanks to Guillaume Marceau for the report.
Repository: commons-math
Updated Branches:
refs/heads/master 5918daf87 -> 4080feff6
[MATH-1148] Fix MonotoneChain with collinear points as input: take tolerance factor into account when initially sorting the input points. Thanks to Guillaume Marceau for the report.
Project: http://git-wip-us.apache.org/repos/asf/commons-math/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-math/commit/4080feff
Tree: http://git-wip-us.apache.org/repos/asf/commons-math/tree/4080feff
Diff: http://git-wip-us.apache.org/repos/asf/commons-math/diff/4080feff
Branch: refs/heads/master
Commit: 4080feff61e8dc1cd4af2361990c33c9f1014147
Parents: 5918daf
Author: Thomas Neidhart <th...@gmail.com>
Authored: Mon Sep 29 18:25:54 2014 +0200
Committer: Thomas Neidhart <th...@gmail.com>
Committed: Mon Sep 29 18:25:54 2014 +0200
----------------------------------------------------------------------
src/changes/changes.xml | 5 ++
.../euclidean/twod/hull/ConvexHull2D.java | 18 +++---
.../euclidean/twod/hull/MonotoneChain.java | 8 ++-
.../hull/ConvexHullGenerator2DAbstractTest.java | 63 +++++++++++++++++---
.../euclidean/twod/hull/MonotoneChainTest.java | 2 +-
5 files changed, 78 insertions(+), 18 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-math/blob/4080feff/src/changes/changes.xml
----------------------------------------------------------------------
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index e25f90e..c64fb58 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -73,6 +73,11 @@ Users are encouraged to upgrade to this version as this release not
2. A few methods in the FastMath class are in fact slower that their
counterpart in either Math or StrictMath (cf. MATH-740 and MATH-901).
">
+ <action dev="tn" type="fix" issue="MATH-1148" due-to="Guillaume Marceau">
+ "MonotoneChain" did not take the tolerance factor into account when
+ sorting the input points. In case of collinear points this could result
+ in a "ConvergenceException" when computing the hull.
+ </action>
<action dev="erans" type="fix" issue="MATH-1151">
Interface "ValueAndJacobianFunction" is a precondition for lazy
evaluation (in "o.a.c.m.fitting.leastsquares").
http://git-wip-us.apache.org/repos/asf/commons-math/blob/4080feff/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHull2D.java
----------------------------------------------------------------------
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
index 1e0eec3..5d9734b 100644
--- 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
@@ -28,8 +28,8 @@ 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.FastMath;
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.
@@ -62,12 +62,14 @@ public class ConvexHull2D implements ConvexHull<Euclidean2D, Vector2D>, Serializ
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();
- this.tolerance = tolerance;
}
/**
@@ -80,7 +82,7 @@ public class ConvexHull2D implements ConvexHull<Euclidean2D, Vector2D>, Serializ
return true;
}
- double sign = 0.0;
+ 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];
@@ -89,14 +91,14 @@ public class ConvexHull2D implements ConvexHull<Euclidean2D, Vector2D>, Serializ
final Vector2D d1 = p2.subtract(p1);
final Vector2D d2 = p3.subtract(p2);
- final double cross = FastMath.signum(MathArrays.linearCombination( d1.getX(), d2.getY(),
- -d1.getY(), d2.getX()));
+ 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 (cross != 0.0) {
- if (sign != 0.0 && cross != sign) {
+ if (cmp != 0.0) {
+ if (sign != 0.0 && cmp != sign) {
return false;
}
- sign = cross;
+ sign = cmp;
}
}
http://git-wip-us.apache.org/repos/asf/commons-math/blob/4080feff/src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java
----------------------------------------------------------------------
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
index 6e56fc6..a811dda 100644
--- 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
@@ -25,6 +25,7 @@ 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
@@ -80,9 +81,12 @@ public class MonotoneChain extends AbstractConvexHullGenerator2D {
// sort the points in increasing order on the x-axis
Collections.sort(pointsSortedByXAxis, new Comparator<Vector2D>() {
public int compare(final Vector2D o1, final Vector2D o2) {
- final int diff = (int) FastMath.signum(o1.getX() - o2.getX());
+ 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 (int) FastMath.signum(o1.getY() - o2.getY());
+ return Precision.compareTo(o1.getY(), o2.getY(), tolerance);
} else {
return diff;
}
http://git-wip-us.apache.org/repos/asf/commons-math/blob/4080feff/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java b/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java
index 3e1552d..0c52550 100644
--- a/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java
+++ b/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java
@@ -30,6 +30,8 @@ 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.apache.commons.math3.util.MathArrays;
+import org.apache.commons.math3.util.Precision;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;
@@ -224,6 +226,46 @@ public abstract class ConvexHullGenerator2DAbstractTest {
}
@Test
+ public void testCollinearPointsInAnyOrder() {
+ // MATH-1148: collinear points on the hull might be in any order
+ // make sure that they are processed in the proper order
+ // for each algorithm.
+
+ List<Vector2D> points = new ArrayList<Vector2D>();
+
+ // first case: 3 points are collinear
+ points.add(new Vector2D(16.078200000000184, -36.52519999989808));
+ points.add(new Vector2D(19.164300000000186, -36.52519999989808));
+ points.add(new Vector2D(19.1643, -25.28136477910407));
+ points.add(new Vector2D(19.1643, -17.678400000004157));
+
+ ConvexHull2D hull = createConvexHullGenerator(false).generate(points);
+ checkConvexHull(points, hull);
+
+ hull = createConvexHullGenerator(true).generate(points);
+ checkConvexHull(points, hull, true);
+
+ points.clear();
+
+ // second case: multiple points are collinear
+ points.add(new Vector2D(0, -29.959696875));
+ points.add(new Vector2D(0, -31.621809375));
+ points.add(new Vector2D(0, -28.435696875));
+ points.add(new Vector2D(0, -33.145809375));
+ points.add(new Vector2D(3.048, -33.145809375));
+ points.add(new Vector2D(3.048, -31.621809375));
+ points.add(new Vector2D(3.048, -29.959696875));
+ points.add(new Vector2D(4.572, -33.145809375));
+ points.add(new Vector2D(4.572, -28.435696875));
+
+ hull = createConvexHullGenerator(false).generate(points);
+ checkConvexHull(points, hull);
+
+ hull = createConvexHullGenerator(true).generate(points);
+ checkConvexHull(points, hull, true);
+ }
+
+ @Test
public void testIssue1123() {
List<Vector2D> points = new ArrayList<Vector2D>();
@@ -337,16 +379,22 @@ public abstract class ConvexHullGenerator2DAbstractTest {
protected final void checkConvexHull(final Collection<Vector2D> points, final ConvexHull2D hull,
final boolean includesCollinearPoints) {
+ checkConvexHull(points, hull, includesCollinearPoints, 1e-10);
+ }
+
+ protected final void checkConvexHull(final Collection<Vector2D> points, final ConvexHull2D hull,
+ final boolean includesCollinearPoints, final double tolerance) {
Assert.assertNotNull(hull);
- Assert.assertTrue(isConvex(hull, includesCollinearPoints));
+ Assert.assertTrue(isConvex(hull, includesCollinearPoints, tolerance));
checkPointsInsideHullRegion(points, hull, includesCollinearPoints);
}
// verify that the constructed hull is really convex
- protected final boolean isConvex(final ConvexHull2D hull, final boolean includesCollinearPoints) {
- double sign = 0.0;
+ protected final boolean isConvex(final ConvexHull2D hull, final boolean includesCollinearPoints,
+ final double tolerance) {
final Vector2D[] points = hull.getVertices();
+ int sign = 0;
for (int i = 0; i < points.length; i++) {
Vector2D p1 = points[i == 0 ? points.length - 1 : i - 1];
@@ -359,17 +407,18 @@ public abstract class ConvexHullGenerator2DAbstractTest {
Assert.assertTrue(d1.getNorm() > 1e-10);
Assert.assertTrue(d2.getNorm() > 1e-10);
- double cross = FastMath.signum(d1.getX() * d2.getY() - d1.getY() * d2.getX());
+ final double cross = MathArrays.linearCombination(d1.getX(), d2.getY(), -d1.getY(), d2.getX());
+ final int cmp = Precision.compareTo(cross, 0.0, tolerance);
- if (sign != 0.0 && cross != sign) {
- if (includesCollinearPoints && cross == 0.0) {
+ if (sign != 0 && cmp != sign) {
+ if (includesCollinearPoints && cmp == 0) {
// in case of collinear points the cross product will be zero
} else {
return false;
}
}
- sign = cross;
+ sign = cmp;
}
return true;
http://git-wip-us.apache.org/repos/asf/commons-math/blob/4080feff/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChainTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChainTest.java b/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChainTest.java
index d39ed4a..fb85f53 100644
--- a/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChainTest.java
+++ b/src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChainTest.java
@@ -49,7 +49,7 @@ public class MonotoneChainTest extends ConvexHullGenerator2DAbstractTest {
points.add(new Vector2D(40, 1));
@SuppressWarnings("unused")
- final ConvexHull2D hull = new MonotoneChain(true, 1).generate(points);
+ final ConvexHull2D hull = new MonotoneChain(true, 2).generate(points);
}
}