An algorithm for computing the convex hull of scattered plane point set through the extreme points on the boundary of plane is proposed. According to the extreme points, the plane point set is divided into five zones. The four zones on the boundary contain all convex vertexes. By computing extreme points of subsets in the four marginal zones, a polygon that contains all convex vertexes is obtained. After eliminating the concave vertexes, it is the convex hull of plane point set. The algorithm is simple and clear, contains less Arithmetic, therefore it reduces the time complexity and computational complexity of the algorithm.
展开▼
