一种简单多边形凸包的快速算法及程序设计

An accelerating algorithm for computing convex hull of simple polygon

给出了一种求简单多边形凸包的快速算法,此算法采取将各个点按与X轴的夹角顺次排列,然后逐渐地删除凹顶点,求得简单多边形的凸包,并给出了算法的数据结构.算法达到了O(nlogn)的理论时间复杂度下限.

This paper focuses on an accelerating algorithm for computing convex hulls of s-polygon, which, at first, arranges all given points according to angle between X-axis and themselves, deletes gradually concave points. We get convex hulls of s-polygon, moreover, and we describe the data-structure of algorithm in details in the paper. Its time-complexity, in theory, is O(nlogn).