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/07/10 23:39:53 UTC
svn commit: r1609577 - in /commons/proper/math/trunk/src: changes/
main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/
test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/
Author: tn
Date: Thu Jul 10 21:39:53 2014
New Revision: 1609577
URL: http://svn.apache.org/r1609577
Log:
[MATH-1135] Fix MonotoneChain algorithm in case of collinear hull points. Thanks to Guillaume Marceau.
Modified:
commons/proper/math/trunk/src/changes/changes.xml
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/changes/changes.xml
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/changes/changes.xml?rev=1609577&r1=1609576&r2=1609577&view=diff
==============================================================================
--- commons/proper/math/trunk/src/changes/changes.xml (original)
+++ commons/proper/math/trunk/src/changes/changes.xml Thu Jul 10 21:39:53 2014
@@ -73,6 +73,11 @@ Users are encouraged to upgrade to this
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-1135" due-to="Guillaume Marceau">
+ "MonotoneChain" failed to generate a convex hull if only a minimal hull
+ shall be created (includeCollinearPoints=false) and collinear hull points
+ were present in the input.
+ </action>
<action dev="tn" type="fix" issue="MATH-1131" due-to="Schalk W. Cronjé">
Improve performance of "KolmogorovSmirnovTest#kolmogorovSmirnovTest(...)" for
large samples.
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=1609577&r1=1609576&r2=1609577&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 Jul 10 21:39:53 2014
@@ -160,8 +160,8 @@ public class MonotoneChain extends Abstr
} else {
if (distanceToCurrent > distanceToLast) {
hull.remove(size - 1);
+ hull.add(point);
}
- hull.add(point);
}
return;
} else if (offset > 0) {
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=1609577&r1=1609576&r2=1609577&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 Jul 10 21:39:53 2014
@@ -53,6 +53,7 @@ public abstract class ConvexHullGenerato
@Before
public void setUp() {
+ // by default, do not include collinear points
generator = createConvexHullGenerator(false);
random = new MersenneTwister(10);
}
@@ -204,6 +205,26 @@ public abstract class ConvexHullGenerato
}
@Test
+ public void testCollinearPointOnExistingBoundary() {
+ // MATH-1135: check that collinear points on the hull are handled correctly
+ // when only a minimal hull shall be constructed
+ final Collection<Vector2D> points = new ArrayList<Vector2D>();
+ points.add(new Vector2D(7.3152, 34.7472));
+ points.add(new Vector2D(6.400799999999997, 34.747199999999985));
+ points.add(new Vector2D(5.486399999999997, 34.7472));
+ points.add(new Vector2D(4.876799999999999, 34.7472));
+ points.add(new Vector2D(4.876799999999999, 34.1376));
+ points.add(new Vector2D(4.876799999999999, 30.48));
+ points.add(new Vector2D(6.0959999999999965, 30.48));
+ points.add(new Vector2D(6.0959999999999965, 34.1376));
+ points.add(new Vector2D(7.315199999999996, 34.1376));
+ points.add(new Vector2D(7.3152, 30.48));
+
+ final ConvexHull2D hull = createConvexHullGenerator(false).generate(points);
+ checkConvexHull(points, hull);
+ }
+
+ @Test
public void testIssue1123() {
List<Vector2D> points = new ArrayList<Vector2D>();