[MATH-749] Convex Hull algorithm

• Type: Sub-task
• Status: Closed
• Priority: Minor
• Resolution: Fixed
• Fix Version/s: 3.3
• Labels: 2d geometric
• Assignee: Thomas Neidhart
• Reporter: Thomas Neidhart
• Created: 18/Feb/12 18:44
• Updated: 19/May/14 15:13
• Resolved: 16/Feb/14 12:24

Description

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.

Issue Links

• relates to: MATH-1095 implement algorithms finding smallest enclosing ball of a collection of points