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)

Rank to TopRank to BottomBulk Copy AttachmentsBulk Move AttachmentsVotersWatch issueWatchersConvert to sub-taskLinkCloneUpdate Comment AuthorReplace String in CommentUpdate Comment VisibilityDelete Comments
    XMLWordPrintableJSON

Details

    • Bug
    • Status: Closed
    • Minor
    • Resolution: Fixed
    • 3.3
    • 3.4
    • None

    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

          This comment will be Viewable by All Users Viewable by All Users
          Cancel

          People

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

            Dates

              Created:
              Updated:
              Resolved:

              Slack

                Issue deployment