求解简单多边形和平面点集凸包的新算法

摘要：

沿一定方向遍历凸多边形的边,其内部在边的同一侧.本文依据凸多边形的这一特性,提出求解简单多边形凸包的新算法,进而扩展得到求解平面点集凸包的新算法.新点集凸包算法先找到点集的极值点,得到极值点间的候选点子集,再求得相邻极值点间的有序凸包点列,最后顺序连接极值点间的有序凸包点列,得到凸包.新算法达到目前平面点集凸包问题的渐进最好算法的时间复杂度O(n log h),其中,n为平面点集的点数,h为平面点集凸包的顶点数.相比相同复杂度的凸包算法,新算法简单、易于实现.又由于是顺序求得凸包上的点,新算法还具有更易于实现基于其上的有效空间算法的优点.

关键词：计算几何、凸包、极值点、有序凸包点列、有效空间

所属期刊栏目：34

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

资助基金：国家高技术研究发展计划863计划2004AA420100

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

页数：共5页

页码：222-226