A Linear Time Convex Hull Algorithm for Simple Polygons

摘要

An algorithm is presented that finds the convex hull of any orderly sequence of points in linear time. It is then shown that any simple polygon is an orderly sequence. Hence, the algorithm constructs that convex hull of any simple polygon in linear time. (Author)