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

摘要：

依据同构化凸壳构造基本定理,提出了效率更高的单域双向水平倾角最小化圈绕二维点集凸壳新算法,它实现了对卷包裹凸壳算法、单域单向水平倾角最小化圈绕凸壳算法的改进与创新.本新算法的同构化特点是:1)找出给定二维点集的最低点,即Y轴坐标值最小点(若有多个最小点,则只取最左的最小点),并作为凸壳逆向(即逆时针)圈绕、顺向(即顺时针)圈绕的共同初始顶点(即最低顶点).2)双向圈绕寻找最新顶点(即凸壳的下一组逆向、顺向最新顶点,而该组最新顶点"初始组必为一个,最末组方可一个,其余组总为一对" ):A.过逆向次新顶点作X轴正向射线,并找出当前点集内对该逆向次新顶点正向射线(为始边的)倾角最小的点,此最小点即为当前逆向最新顶点;B.过顺向次新顶点作X轴负向射线,并找出当前点集内对该顺向次新顶点负向射线(为终边的)倾角最小的点,此最小点即为当前顺向最新顶点.3)删除对已得各顶点所构成的子凸壳各内点.4)仅当所剩当前点集非空时才从"2)"继续作逐边双向圈绕.

关键词：同构化、水平倾角、双向圈绕、凸壳算法

所属期刊栏目：34

分类号：TP3(计算技术、计算机技术)

资助基金：西南财经大学校科研和教改项目06K975

在线出版日期：2007-10-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：223-226