[
https://issues.apache.org/jira/browse/MATH-749?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Thomas Neidhart resolved MATH-749.
----------------------------------
Resolution: Fixed
In r1568752 I did the following changes:
* removed GrahamScan and GiftWrap as they are not robust wrt collinear points
* add ConvergenceException in case the convex hull generator can not find a
convex hull with the given tolerance value
* ConvexHull2D ctor is public now and throws an IllegalArgumentException if
the provided vertices do not form a convex hull
* Improved robustness of MonotoneChain wrt collinear points
* Improved GeometryExample in userguide examples
I am now confident that the MonotoneChain algorithm is really robust for all
kinds of input.
> Convex Hull algorithm
> ---------------------
>
> Key: MATH-749
> URL: https://issues.apache.org/jira/browse/MATH-749
> Project: Commons Math
> Issue Type: Sub-task
> Reporter: Thomas Neidhart
> Assignee: Thomas Neidhart
> Priority: Minor
> Labels: 2d, geometric
> Fix For: 3.3
>
> Attachments: MATH-749.tar.gz
>
>
> It would be nice to have convex hull implementations for 2D/3D space. There
> are several known algorithms
> [http://en.wikipedia.org/wiki/Convex_hull_algorithms]:
> * Graham scan: O(n log n)
> * Incremental: O(n log n)
> * Divide and Conquer: O(n log n)
> * Kirkpatrick-Seidel: O(n log h)
> * Chan: O(n log h)
> The preference would be on an algorithm that is easily extensible for higher
> dimensions, so *Incremental* and *Divide and Conquer* would be prefered.
--
This message was sent by Atlassian JIRA
(v6.1.5#6160)
