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