Simple Fast Convex Hull Algorithm of Planar Point Set
Cad La · Beijing Hangkong Hangtian Daxue xuebao · 1999
Convex hull problem is one of the fundamental problems incomputational geometry,and used in many fields. The traditional convex hull algorithms of point set and that of simple polygons have parallelly developed without any combination. In this paper, a new algorithm is proposed based on combining the convex hull algorithms of simple polygons into solving the problem of point set. The algorithms in this paper not only reaches the lower bound of O( n log n ),but also is very simple and easy to be realized. The presented algorithms has been applied in plantdesign system of PDSOFT.The results obtained by the method areremarkable.