平面点集凸包快速构建算法的研究

文章提出了一种提高构建凸包速度的新方法。该算法生成一个网格来管理离散点,在淘汰明显不位于凸包上的点时,将对离散点的取舍转换为对格的取舍,计算工作量只与离散点的范围及网格的密度有关,与离散点的数目无关;同时对点集也进行了初略的排序。在求取剩余点集的凸包时,采用了一种先分段求取凸包边界,最后将这些边界合并成凸包的方法,该方法充分利用了剩余点集所具有的有序性。

Study on Fast Convex Hull Algorithm of Planar Point Set

In this paper,a new algorithm is proposed for improving the speed of calculating the convex hull of planar point set.The algorithm creates a square mesh to manage points,when eliminating the points which are obviously not on the convex hull,selecting or eliminating of point can be converted to that of grid,the work of calculation depends on the range of point set and density of grid mesh but not the number of points.At the meantime,the points are sorted roughly.When calculating the convex hull of remainder points,a method is presented which can take advantage of order of the remainder points,it calculates the boundaries of the convex hull segment by segment,then,combines the boundaries to form convex hull.