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

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

Linear Algorithms for Finding the Convex Hull of a Simple Polygon

This paper presents two algorithms to construct the vertex convex hull of a simple polygon in linear time. The basic idea of the first algorithm is that polygonal vertices are selected by using a technique so that the sizes of the angles of the remaining vertices are arranged into an incremental sequence, then the vertices of the non-convex hull are removed using Graham's scan method, finally a vertex sequence of the convex hull of a polygon is obtained. The second algorithm is that polygonal concave points and newly created concave points are continuously removed, and a vertex sequence of the convex hull is finally obtained. The two algorithms are not only simple but also easy to realize, and also their time complexity is O( n ).