文献类型：期刊文章

作　　者：黄涛[1] 周启海[1] 吴红玉[2]

机构地区：[1]西南财经大学信息技术应用研究所,成都610074 [2]西南财经大学经济信息工程学院,成都610074

出　　处：《计算机科学》

年　　份：2008

卷　　号：35

期　　号：2

起止页码：235-237

语　　种：中文

收录情况：BDHX、BDHX2004、CSA、CSCD、CSCD2011_2012、IC、JST、UPD、ZGKJHX、核心刊

摘　　要：本文依据同构化凸壳构造基本定理,提出效率更高的双域双向水平倾角最小化圈绕凸壳新算法。本新算法的同构化特点是:1)"初始顶点与双域生成"处理:找出给定二维点集S的最低点和最高点,即Y轴坐标值最小点(若有多个最小点,则只取最左的最小点)和Y轴坐标值最大点(若有多个最大点,则只取最左的最大点),作为凸壳(逆时针圈绕的)A向初始顶点、(顺时针圈绕的)B向初始顶点;并以这两个初始顶点为端点的线段,把原二维点集划分为两个独立的子点集S右、S左。2)在S右内,进行双向"圈绕寻找下一新顶点"即凸壳A向、B向最新顶点寻找处理:分别过自己的最近新顶点,作X轴正向射线,并A向或B向找出当前点集内对该顶点正向射线(为始边的)倾角最小的点;删除对已得各顶点所构成的子凸壳内点,当所剩当前点集非空时继续作"2)"逐边圈绕,直到为空。3)同理,在子点集S左内,进行双向"圈绕寻找下一新顶点"即凸壳A向、B向最新顶点寻找处理。

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

分 类 号：TP301.6] TN791.02[计算机类]