[
https://issues.apache.org/jira/browse/MATH-1148?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14104545#comment-14104545
]
Thomas Neidhart commented on MATH-1148:
---------------------------------------
We do not yet check if a collinear point leads to a concave section of the
lower/upper hull.
So far the assumption was that a collinear sequence of points will be like
this: A - B - C, thus never creating a concave section.
In your example it is like this (A and B currently part of the hull): C - A -
B, thus the next point is collinear in the other direction.
This case is indeed tricky to handle. The best way would be to check if the
point C is in the same direction as B, if not, we need to backtrack (i.e.
remove points) on the hull until it is convex again.
> 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
>
> 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.2#6252)
