AN OPTIMAL REAL TIME ALGORITHM FOR DETERMINING THE CONVEX HULL OF A SET OF POINTS IN A PLANE
Zhi Wang · Chinese Journal of Computers · 1998
Based on the properties of star polygon and the convex polygon is a special kind of starpolygon, let the star point be the center and these two lines respectively parallel to the x-axis andyaxis as coordinate axis, a relative coordinate system is built and the planar area is divided into fourareas. Based on the new equation of relationship of point to orientation line, so inner point andexternal point of polygon is quickly separated, the embraced point (tangent point) of external point israpidly found. An optimal real time algorithm for computing the convex hull of a set of points in aplane is presented. Its time complexity is O(n). It can also be used for determining the convex hullof polygon and has the same time complexity. It also has the advantage of controlling the orientationof the result convex hull, which only to do is adjusting the initial triangle and need not modify theother parts of the algorithm. This algorithm has the properties of efficiency, stabilization such etc.It provides the practical possibility of finding the linear sorting algorithm along with the Cul Guohuaetc's theory. At the conclusion part of this paper the processing time comparison of this algorithmwith the classical Graham Scan Algorithm and the Heap Sorting Algorithm and the comparison ofper formance of several typical algorithm are given.