commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Guillaume Marceau (JIRA)" <j...@apache.org>
Subject [jira] [Updated] (MATH-1135) Bug in MonotoneChain: a collinear point landing on the existing boundary should be dropped (patch)
Date Thu, 10 Jul 2014 18:12:05 GMT

     [ 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.

{code:java}
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>();
{code}

  was:
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>();



> 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.
> {code:java}
> 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>();
> {code}



--
This message was sent by Atlassian JIRA
(v6.2#6252)

Mime
View raw message