commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Thomas Neidhart (JIRA)" <j...@apache.org>
Subject [jira] [Resolved] (MATH-1148) MonotoneChain handling of collinear points drops low points in a near-column
Date Mon, 29 Sep 2014 16:29:34 GMT

     [ https://issues.apache.org/jira/browse/MATH-1148?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

Thomas Neidhart resolved MATH-1148.
-----------------------------------
       Resolution: Fixed
    Fix Version/s: 3.4

Fixed in commit 4080feff61e8dc1cd4af2361990c33c9f1014147.

The problem could be solved by taking the tolerance factor for collinear points into account
when sorting the input which is the first necessary step for the Monotone chain algorithm.

Then the construction of the upper/lower hull works correctly.

I also improved the isConvex method in ConvexHull2D which actually did not work reliable in
the presence of collinear points.

Thanks for the report, please let us know if you encounter any other problems.

> MonotoneChain handling of collinear points drops low points in a near-column
> ----------------------------------------------------------------------------
>
>                 Key: MATH-1148
>                 URL: https://issues.apache.org/jira/browse/MATH-1148
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 3.3
>            Reporter: Guillaume Marceau
>             Fix For: 3.4
>
>
> This code
> {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)
> {code}
> results in the exception:
> {code}
> 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)
> {code}
> 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.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message