一种简单多边形凸包的新线性算法

摘要

给出了一个计算简单多边形凸包的新算法.其搜索策略为:对简单多边形上的点进行分类,排除不可能为凸包上的点,缩小搜索范围,从而降低算法的时间复杂度.该算法具有线性时间复杂度和空间复杂度.同时,具体量化了该算法的复杂度,给出了该算法的时间复杂度和空间复杂度的确定的上界,即,时间复杂度为不超过4(n-4)次乘法、6(n-4)次减法和17n-12次比较运算,空间复杂度为不超过2n个存储单元(n是该简单多边形顶点的个数).