10.3969/j.issn.1002-137X.2007.12.060
求解简单多边形和平面点集凸包的新算法
沿一定方向遍历凸多边形的边,其内部在边的同一侧.本文依据凸多边形的这一特性,提出求解简单多边形凸包的新算法,进而扩展得到求解平面点集凸包的新算法.新点集凸包算法先找到点集的极值点,得到极值点间的候选点子集,再求得相邻极值点间的有序凸包点列,最后顺序连接极值点间的有序凸包点列,得到凸包.新算法达到目前平面点集凸包问题的渐进最好算法的时间复杂度O(n log h),其中,n为平面点集的点数,h为平面点集凸包的顶点数.相比相同复杂度的凸包算法,新算法简单、易于实现.又由于是顺序求得凸包上的点,新算法还具有更易于实现基于其上的有效空间算法的优点.
计算几何、凸包、极值点、有序凸包点列、有效空间
34
TP3(计算技术、计算机技术)
国家高技术研究发展计划863计划2004AA420100
2008-03-17(万方平台首次上网日期,不代表论文的发表时间)
共5页
222-226