%0 Journal Article
%T A New Algorithm for Finding Convex Hull Based on Coiling with a Minimum Lever Pitch in Double Domain and Double Direction<br>基于双域双向水平倾角最小化圈绕的凸壳新算法
%A HUANG Tao
%A ZHOU Qi-Hai
%A WU Hong-Yu
%A <br>黄涛
%A 周启海
%A 吴红玉
%J 计算机科学
%D 2008
%I 
%X 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 double direction is advanced.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 bottommost 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 Sright do the process of seeking the newest apex with double direction: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 vertex's regressive half line(as the initial line)to be the newest vertex in coiling;Delete 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.3)in the 2D point set Sleft do the similar process.
%K Isomorphic
%K Convex hull algorithm
%K Vertex's half line
%K Pitch of base Lines
%K Double domain and double direction coiling<br>同构化
%K 凸壳算法
%K 顶点射线
%K 水平倾角
%K 双域双向圈绕
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=DDC938848A885B06E4E21B097D447CD1&yid=67289AFF6305E306&vid=6209D9E8050195F5&iid=0B39A22176CE99FB&sid=6CCE24D86D03D083&eid=FE4C96E058BB2280&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=7