A FAST CONVEX HULL ALGORITHM OF PLANAR POINT SET BASED ON SORTED SIMPLE POLYGON

Convex hull problem is one of the fundamental problems in computational geometry, and used in many fields. The traditional convex hull algorithms of planar point set and those of simple polygon were developed in parallel, without any combination-In this paper, a new algorithm is proposed by combining improved convex hull algorithm of simple polygon to solve the problem of planar pointset. The algorithm firstly eliminates those points which are obviously not on the hull, then sorts the points that remain, and then links the points into a sorted simple polygon according to the definite order. Finally it searches the convex hull of the polygon using forward-backward method, and thereby obtains the convex hullof the point set. The algorithm not only reaches the theoretical lower bound ofO(nlogn),but also is very simple and easy to be realized. The presented algorithm has been applied in plant design system PDSOFT. The results obtained by the method are remarkable.