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

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

作　　者：黄涛[1] 周启海[1] 

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

出　　处：《计算机科学》2007年第11期208-211,共4页Computer Science

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

摘　　要：本文依据同构化凸壳构造基本定理,提出了效率更高的双域单向水平倾角最小化圈绕二维点集凸壳新算法,实现了对卷包襄凸壳算法、单域单向水平倾角最小化圈绕凸壳算法的改进与创新。本新算法的同构化特点是:1)"初始顶点与双域生成"处理:找出给定二维点集S的最低点和最高点,即Y轴坐标值最小点(若有多个最小点,则只取最左的最小点)和Y轴坐标值最大点(若有多个最大点,则只取最右的最大点),作为凸壳逆时针圈绕的初始顶点;并以这两个初始顶点为端点的线段,把原二维点集划分为两个独立的子点集S_右、S_左。2)进行单向"圈绕寻找下一新顶点":A)在S_右内,过逆向次新顶点作X轴正向射线,并找出当前子点集内对该逆向次新顶点正向射线(为始边的)倾角最小的点,此最小点即为S_右逆向最新顶点;B)在S_左内,过次新顶点作X轴负向射线,并找出当前子点集内对该逆向次新顶点负向射线(为终边的)倾角最小的点,此最小点即为S_左逆向最新顶点。3)删除对已得各顶点所构成的子凸壳各内点。4)仅当所剩当前点集非空时才从"2)"继续作逐边双域单向圈绕。According to the isomorphic fundamental theorem of the convex hull construction, a more efficient new algorithm to find a convex hull based on coiling with a minimum lever pitch in double domain and single direction is advanced. It 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 AlgorithrrL This new algorithm isomorphism characteristic is： 1）＂the generation of initial vertex and double domain＂： find out the bottommost point and the highest point on the convex hull S as the initial vertex of the convex hull, which has the minimum or the maximum coordinate value of the Y axis among all the points in given 2D point set （if the hottommost point is not only one, the bottommost and leftmost or the highest rightmost point should be selected）. The line which take the two initial vertexes as end points divide the 2D point set into two absolute point set Sright, Sleft,. 2）in the 2D point set Sleft do the process of seeking the newest apex with single direction： A. in Sright, passing the last new regressive vertex, make the vertex＇s half line paralleled by X axis along positive direction, and find out the current vertexes with a minimum pitch to its vextex＇s regressive half line（as the initial line） to be the newest vertex in coiling; B. A. in Sleft ,passing the last new regressive vertex, make the vertex＇s half line paralleled by X axis along negative direction, and find out the current vertexes with a minimun pitch to its vertex＇s regressive half line（as the final line） to be the newest vertex in coiling; 3）Deletes the sub-convex hull＇s inner points, And loop from＂2）＇to coil with double direction side by side continuingly while the reminded point set is not empty.

关 键 词：同构化 凸壳算法 顶点射线 水平倾角 双域单向圈绕 

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