[
https://issues.apache.org/jira/browse/MATH-1135?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Guillaume Marceau updated MATH-1135:
------------------------------------
Description:
The is a bug on the code in MonotoneChain.java that attempts to handle the case
of a point on the line formed by the previous last points and the last point of
the chain being constructed. When `includeCollinearPoints` is false, the point
should be dropped entirely. In common-math 3,3, the point is added, which in
some cases can cause a `ConvergenceException` to be thrown.
In the patch below, the data points are from a case that showed up in testing
before we went to production.
Index:
src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java
===================================================================
---
src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java
(revision 1609491)
+++
src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java
(working copy)
@@ -160,8 +160,8 @@
} else {
if (distanceToCurrent > distanceToLast) {
hull.remove(size - 1);
+ hull.add(point);
}
- hull.add(point);
}
return;
} else if (offset > 0) {
Index:
src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java
===================================================================
---
src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java
(revision 1609491)
+++
src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java
(working copy)
@@ -204,6 +204,24 @@
}
@Test
+ public void testCollinnearPointOnExistingBoundary() {
+ 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 = generator.generate(points);
+ checkConvexHull(points, hull);
+ }
+
+ @Test
public void testIssue1123() {
List<Vector2D> points = new ArrayList<Vector2D>();
was:
MonotoneChain.java attempts to handle the case when a point appears that is
prolonging the line formed by the previous last points and the last point on
the chain being constructed. It code should replace the last point with the new
point.
The data points in the test are from a case that showed up before we went to
production.
Index:
src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java
===================================================================
---
src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java
(revision 1609491)
+++
src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java
(working copy)
@@ -160,8 +160,8 @@
} else {
if (distanceToCurrent > distanceToLast) {
hull.remove(size - 1);
+ hull.add(point);
}
- hull.add(point);
}
return;
} else if (offset > 0) {
Index:
src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java
===================================================================
---
src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java
(revision 1609491)
+++
src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java
(working copy)
@@ -204,6 +204,24 @@
}
@Test
+ public void testCollinnearPointOnExistingBoundary() {
+ 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 = generator.generate(points);
+ checkConvexHull(points, hull);
+ }
+
+ @Test
public void testIssue1123() {
List<Vector2D> points = new ArrayList<Vector2D>();
> Bug in MonotoneChain: a collinear point landing on the existing boundary
> should be dropped (patch)
> --------------------------------------------------------------------------------------------------
>
> Key: MATH-1135
> URL: https://issues.apache.org/jira/browse/MATH-1135
> Project: Commons Math
> Issue Type: Bug
> Affects Versions: 3.3
> Reporter: Guillaume Marceau
> Priority: Minor
> Labels: patch
> Attachments: MonotoneChain_testCollinnearPointOnExistingBoundary.patch
>
>
> The is a bug on the code in MonotoneChain.java that attempts to handle the
> case of a point on the line formed by the previous last points and the last
> point of the chain being constructed. When `includeCollinearPoints` is false,
> the point should be dropped entirely. In common-math 3,3, the point is added,
> which in some cases can cause a `ConvergenceException` to be thrown.
> In the patch below, the data points are from a case that showed up in testing
> before we went to production.
> Index:
> src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java
> ===================================================================
> ---
> src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java
> (revision 1609491)
> +++
> src/main/java/org/apache/commons/math3/geometry/euclidean/twod/hull/MonotoneChain.java
> (working copy)
> @@ -160,8 +160,8 @@
> } else {
> if (distanceToCurrent > distanceToLast) {
> hull.remove(size - 1);
> + hull.add(point);
> }
> - hull.add(point);
> }
> return;
> } else if (offset > 0) {
> Index:
> src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java
> ===================================================================
> ---
> src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java
> (revision 1609491)
> +++
> src/test/java/org/apache/commons/math3/geometry/euclidean/twod/hull/ConvexHullGenerator2DAbstractTest.java
> (working copy)
> @@ -204,6 +204,24 @@
> }
>
> @Test
> + public void testCollinnearPointOnExistingBoundary() {
> + 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 = generator.generate(points);
> + checkConvexHull(points, hull);
> + }
> +
> + @Test
> public void testIssue1123() {
>
> List<Vector2D> points = new ArrayList<Vector2D>();
--
This message was sent by Atlassian JIRA
(v6.2#6252)
