单域双向水平倾角最小化圈绕凸壳新算法  

A New Algorithm for Finding Convex Hull Based on Coiling with a Minimum Lever Pitch in Single Domain and Double Direction

作　　者：周启海[1] 吴红玉[1] 黄涛[1] 张元新[1] 张乐[1] 

机构地区：[1]西南财经大学经济信息工程学院,成都610074

出　　处：《计算机科学》2007年第8期223-226,共4页Computer Science

基　　金：西南财经大学科研基金项目(No.06K975)

摘　　要：依据同构化凸壳构造基本定理,提出了效率更高的单域双向水平倾角最小化圈绕二维点集凸壳新算法,它实现了对卷包裹凸壳算法、单域单向水平倾角最小化圈绕凸壳算法的改进与创新。本新算法的同构化特点是:1)找出给定二维点集的最低点,即Y轴坐标值最小点(若有多个最小点,则只取最左的最小点),并作为凸壳逆向(即逆时针)圈绕、顺向(即顺时针)圈绕的共同初始顶点(即最低顶点)。2)双向圈绕寻找最新顶点(即凸壳的下一组逆向、顺向最新顶点,而该组最新顶点"初始组必为一个,最末组方可一个,其余组总为一对"):A.过逆向次新顶点作X轴正向射线,并找出当前点集内对该逆向次新顶点正向射线(为始边的)倾角最小的点,此最小点即为当前逆向最新顶点;B.过顺向次新顶点作X轴负向射线,并找出当前点集内对该顺向次新顶点负向射线(为终边的)倾角最小的点,此最小点即为当前顺向最新顶点。3)删除对已得各顶点所构成的子凸壳各内点。4)仅当所剩当前点集非空时才从"2)"继续作逐边双向圈绕。According to the isomorphic fundamental theorem of constructing for the convex hull, a more efficient new algorithm to find a convex hull based on coiling with a minimum lever pitch in single domain and double directions is advanced, which has realized the improvement of the Gift Wrapping convex hull algorithm and Coiling with a Minimum Lever Pitch in Single Domain and Single Direction Convex Hull Algorithm. This new algorithm＇s isomorphism characteristics are： 1） finds out the bottommost point on the convex hull as the initial vertex （i. e. apex） of the convex hull, which has the minimum coordinate value of the Y axis among all the points in given 2D point set （if the bottommost point is not only one, the leftmost point among the all bottommost points should be selected only） ; 2） seeks the newest apex with double direction： A. passing the last new regressive pre-vertex along the clockwise, make the pre-vertex＇s half line paralleled by X axis along positive direction, and find out a current vertex with a minimum pitch to its regressive pre-vertex＇s half line （as the initial line） to be the current newest vertex in coiling along the clockwise; B. passing the last new regressive pre-vertex along the reverse clockwise, make the pre-vertex＇s half line paralleled by X axis along negative direction, and find out a current vertex with a minimum pitch to its vertex＇s negative half line（as the finial line） to be the current newest vertex in coiling along the reverse clockwise; 3） deletes all the inner points of the sub-convex hull determined by all the got vertexes. 4） loops from ＂2）＂to coil with double direction side by side continuingly while the reminded point set is only not empty.

关 键 词：同构化 水平倾角 双向圈绕 凸壳算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]