A Grid-based Algorithm for Determining Convex Hull of a Planar Set
Yushu Liu · Microcomputer Development · 2004
In this paper, a new algorithm is presented for determining the convex hull of a planar set. The computing method uses a grid array to divide the planar point set into lots of subsets so that the convex hull can be determined by a part of subsets which are at the edge of the planar point set, and then a simple polygon which contains all points of the planar point set is gained by some processes operating on those subsets in the anti-clockwise sequence, after that the convex hull is gotten by deleting the concave points from the simple polygon. The efficiency of the calculation is greatly improved owing to the operation kept in the points that are at the edge of the planar point set.The time complication of the algorithm in the worst condition is O(NlogN).