Uploaded image for project: 'Commons Math'
  1. Commons Math
  2. MATH-1135

Bug in MonotoneChain: a collinear point landing on the existing boundary should be dropped (patch)

    XMLWordPrintableJSON

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Minor
    • Resolution: Fixed
    • Affects Version/s: 3.3
    • Fix Version/s: 3.4
    • Labels:

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

        Attachments

          Activity

            People

            • Assignee:
              Unassigned
              Reporter:
              gmarceau Guillaume Marceau
            • Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: