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

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