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

MonotoneChain handling of collinear points drops low points in a near-column

    Details

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

      Description

      This code

      val points = List(
        new Vector2D(
          16.078200000000184,
          -36.52519999989808
        ),
        new Vector2D(
          19.164300000000186,
          -36.52519999989808
        ),
        new Vector2D(
          19.1643,
          -25.28136477910407
        ),
        new Vector2D(
          19.1643,
          -17.678400000004157
        )
      )
      new hull.MonotoneChain().generate(points.asJava)
      

      results in the exception:

      org.apache.commons.math3.exception.ConvergenceException: illegal state: convergence failed
      	at org.apache.commons.math3.geometry.euclidean.twod.hull.AbstractConvexHullGenerator2D.generate(AbstractConvexHullGenerator2D.java:106)
      	at org.apache.commons.math3.geometry.euclidean.twod.hull.MonotoneChain.generate(MonotoneChain.java:50)
      	at .<init>(<console>:13)
      	at .<clinit>(<console>)
      	at .<init>(<console>:11)
      	at .<clinit>(<console>)
      	at $print(<console>)
      	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
      	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
      	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
      	at java.lang.reflect.Method.invoke(Method.java:597)
      	at scala.tools.nsc.interpreter.IMain$ReadEvalPrint.call(IMain.scala:704)
      	at scala.tools.nsc.interpreter.IMain$Request$$anonfun$14.apply(IMain.scala:920)
      	at scala.tools.nsc.interpreter.Line$$anonfun$1.apply$mcV$sp(Line.scala:43)
      	at scala.tools.nsc.io.package$$anon$2.run(package.scala:25)
      	at java.lang.Thread.run(Thread.java:662)
      

      This will be tricky to fix. Not only is the point (19.164300000000186, -36.52519999989808) is being dropped incorrectly, but any point dropped in one hull risks creating a kink when combined with the other hull.

        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: