双域双向水平倾角最小化圈绕凸壳新算法
本文依据同构化凸壳构造基本定理,提出效率更高的双域双向水平倾角最小化圈绕凸壳新算法。本新算法的同构化特点是:①”初始顶点与双域生成”处理:找出给定二维点集S的最低点和最高点。即Y轴坐标值最小点(若有多个最小点则只取最左的最小点)和Y轴坐标值最大点。(若有多个最大点则只取最左的最大点),作为凸壳(逆时针圈绕的)A向初始顶点、(顺时针圈绕的)B向初始顶点，并以这两个初始顶点为端点的线段,把原二维点集划分为两个独立的子点集S右、S左.②在S右内,进行双向”圈绕寻找下一新顶点”即凸壳A向、B向最新顶点寻找处理:分别过自己的最近新顶点作X轴正向射线,并A向或B向找出当前点集内对该顶点正向射线(为始边的)倾角最小的点，删除对已得各顶点所构成的子凸壳内点。当所剩当前点集非空时继续作”②”逐边圈绕,直到为空.③同理,在子点集S左内,进行双向”圈绕寻找下一新顶点”即凸壳A向、B向最新顶点寻找处理.
同构化 凸壳算法 水平倾角 双域双向圈绕
周启海 黄涛 吴红玉
西南财经大学经济信息工程学院,成都,610074
国内会议
兰州、敦煌
中文
187-192
2007-07-15（万方平台首次上网日期，不代表论文的发表时间）