An Isomorphic New Algorithm for Finding Convex Hull with a Maximum Pitch of the Dynamical Base Line Guided by Apexes Distributing Characteristics

Abstract

In this paper, a representative algorithm convex hull with half-dividing and recurrence is commented; and according to the isomorphic fundamental theorem of the convex hull construction, and guided by the isomorphic distributing characteristics of a convex hull’s the apexes, a more efficient new algorithm to find a convex hull based on the dynamical base line with a maximum pitch of the dynamical base line is given. The general characters of the new algorithm are: 1) find out the outside-most poles which are the leftmost, rightmost, topmost and bottommost points of the given 2D point set, i.e. the four initial poles which have the maximum or the minimum coordinate value of the X or Y axis among all the points in the given 2D point set; 2) divide the original distributed domain into four subdomains with the initial poles; 3) in every sub-domain, construct a current pole with a maximum pitch to its base line based on the last pole got just dynamically and sequentially, and draw the rims of this convex polygon with these poles for intelligent approximating for a convex hull of the given 2D point set step by step.