基于最大基线倾角智能逼近的凸壳新算法

A New Algorithm for Finding Convex Hull Based on Intelligent Approximating with a Maximum Pitch of Base Lines

本文评述了有代表性的折半分治递归凸壳算法,并利用同构化凸壳基本定理提出效率更高的最大倾角智能逼近凸壳新算法。本新算法的同构化特点是:1)找出给定二雏点集最外点(指最左、最右、最高、最低点),即其X轴、Y轴坐标值最大、最小的四个初始极点;2)用该初始极点,把原二维点集分布域划分为四个子分布域;3)分别在这四个子分布域中,各基于自身最新所得极点依次动态构造其基线倾角最大的当前极点,并用这些极点作凸边,来逐步智能逼近和最终生成该给定二维点集的凸壳。

In this paper, comment on a representative algorithm convex hull with half-dividing and recurrenc; and a more efficient new algorithm to find a convex hull based on intelligent approximating with a maximum pitch is given by the isomorphic fundamental theorem of the convex hull. The isomorphic characters of the new algorithm are： 1） find out the outside-most poles which are the leftmost, rightmost, topmost and bottommost points on the convex hull, 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 given 2D point set; 2） divides the original distributed domain into four sub-domain with the initial poles; 3） in every sub-domain, constructs a current pole with a maximum pitch to its base line based on its 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.