一种凸包的改进算法设计与实现

Design and Implementation of an Improved Algorithm of Convex Hull

给出一种求解多边形凸包的改进算法,该算法采取构造一个四边形并删除其内部的点集,从而达到减少扫描次数、提高运算速度的目的。该算法的时间复杂度为O(nlogn),具有实现简单,且比Graham扫描算法性能更好的特点。实验结果表明,改进后算法进一步提高了运算性能,效果更好。

Gives an improved algorithm of calculating polygon convex hull. This algorithm adopts a structure quadrangle and deletes its internal set of points, thus achieves the goal of reducing numbers of scanning, enhances the operating speed. The time complexity of this algorithm is O（nlogn）. Its realization is simple and its performance is better than Graham scanning algorithm.