[ https://issues.apache.org/jira/browse/MATH-749?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Thomas Neidhart reopened MATH-749: ---------------------------------- Discovered problems with collinear points when testing the graphical test program. GiftWrap and GrahamScan make problems when there are multiple points e.g. with the smallest x-coordinate. > 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)