寻求简单多边形凸壳的线性时间算法

本文提出在线性时间内构造简单多边形顶点凸壳的两种算法。第一个算法的基本思想是利用一种技巧对多边形顶点进行筛选 ,使剩余顶点的角的大小排成递增序 ,然后用Graham扫描方法删去非凸壳顶点 ,最后得到多边形凸壳的顶点序列。第二个算法不断删去多边形的凹点及新产生的凹点 ,最后得到凸壳顶点序列。这两种算法简单 ,易于实现 ,时间复杂性都是O(n)