Details
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)
 KirkpatrickSeidel: 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

MATH1095 implement algorithms finding smallest enclosing ball of a collection of points
 Closed
Activity
Luc Maisonobe
made changes 
Status  Resolved [ 5 ]  Closed [ 6 ] 
Thomas Neidhart
made changes 
Status  Reopened [ 4 ]  Resolved [ 5 ] 
Resolution  Fixed [ 1 ] 
Thomas Neidhart
made changes 
Resolution  Fixed [ 1 ]  
Status  Resolved [ 5 ]  Reopened [ 4 ] 
Thomas Neidhart
made changes 
Status  Open [ 1 ]  Resolved [ 5 ] 
Resolution  Fixed [ 1 ] 
Thomas Neidhart
made changes 
Fix Version/s  3.3 [ 12324600 ] 
Luc Maisonobe
made changes 
Thomas Neidhart
made changes 
Attachment  MATH749.tar.gz [ 12625289 ] 
Thomas Neidhart
made changes 
Assignee  Thomas Neidhart [ tn ] 
Thomas Neidhart
made changes 
Fix Version/s  3.2 [ 12322545 ] 
Thomas Neidhart
made changes 
Fix Version/s  3.2 [ 12322545 ]  
Fix Version/s  3.1 [ 12317576 ] 
Thomas Neidhart
made changes 
Parent 


Issue Type  New Feature [ 2 ]  Subtask [ 7 ] 
Thomas Neidhart
made changes 
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) * KirkpatrickSeidel: O(n log h) * Chan: O(n log h) The preference would be on an algorithm that is easily extensible for higher dimensions, TBD. 
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) * KirkpatrickSeidel: 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. 
Thomas Neidhart
made changes 
Description  It would be nice to have an implementation of Graham's scan algorithm to compute the convex hull of a set of points in a plane. 
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) * KirkpatrickSeidel: O(n log h) * Chan: O(n log h) The preference would be on an algorithm that is easily extensible for higher dimensions, TBD. 
Thomas Neidhart
made changes 
Field  Original Value  New Value 

Priority  Major [ 3 ]  Minor [ 4 ] 
Thomas Neidhart
created issue 
Closing all resolved issue now available in released 3.3 version.