[MATH-1148] MonotoneChain handling of collinear points drops low points in a near-column

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 3.3
• Fix Version/s: 3.4
• Assignee: Unassigned
• Reporter: Guillaume Marceau
• Created: 20/Aug/14 16:17
• Updated: 26/Dec/14 19:50
• Resolved: 29/Sep/14 16:28

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.