Proved quick convex hull algorithm for scattered points
Linna Huang, Guangzhong Liu · 2012
On the basis of the concept of right-shell-tree and left-shell-tree, a fast convex hull algorithm for scattered points based on a binary tree is put forward. It can dynamically reduce the scale of scattered point rapidly by removing a number of non-convex hull vertexes while finding each convex hull vertex. Normally, it can achieve linear time complexity. The algorithm obviates the judging process of the convex hull vertices' connected relation. It is applicable to any complex scattered points, and simple and easy to achieve.