摘要：

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

关键词: 易多边形凸壳 线性时间算法 复杂性 计算几何