A Fast Convex Hull Algorithm of Planar Point Set

Abstract:

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

• Periodical: Advanced Materials Research (Volumes 706-708)
• Pages: 1852-1855
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.706-708.1852
• Online since: June 2013
• Authors: Hong Fei Jiang
• Keywords: Computational Geometry, Convex Hull, Mesh, Planar Point Set

References

[1] F. P.Preparata,J S Hong.Convex Hulls of Finite Sets of Points in Two and Three Dimension. Communications of the ACM.1977,20(2):87-93

DOI: 10.1145/359423.359430

[2] G. S. Akl, T. G. Toussaint.A Fast Convex Hull Algorithm. Inf Proc Lett.1978,7(5):219-222

[3] M. A.Andrew,Another Efficient Algorithm for Convex Hulls in Two Dimension.Inf Proc Lett,1979,9(5):216-219

[4] F. P.Preparata,Michael Lan Shamos.Computational Geometry:an Introduction.New York: Springer-Verlag,(1985)

[5] Jin Wenhua,He Tao,Liu XiaoPing,A Fast Convex Hull Algorithm of Planar Point Set Based on Sorted Simple Polygon. Chinese journal of computer.1998,21(6):533-539

[6] Yu Xiang-yu, Sun Hong, Yu Zhi-wiong. An Improved Algorithm to Determine the Convex Hull of 2-D Points Set. Journal of Wuhan University of Technology. 2005,27(10):81-83

[7] Fan Guang-quan, Qu Wen-long,Yang Bing-ru. A Property of the Convex Hull of Planar Point Set.Geography and Geo-Information Science.2008,24(1):46-48

[8] Guang-hui Liu,Chuan-bo Chen, A New Algorithm for Computing the Convex Hull of a Planar Point Set. Journal of Zhejiang University SCIENCE A, 2007,8(8):1210-1217

DOI: 10.1631/jzus.2007.a1210

[9] Liu Guang-Hui Chen Chuan-Bo, New Algorithms for Computing the Convex Hulls of a Simple Polygon and a Planar Point Set. Computer Science.2007,34(12):222-226

[10] Zhao Jun, Qu Shi-ru, Efficient Convex Hull Algorithm for Plane Point Set. Computer Engineering and Application, 2009,45(1):56-58

[11] Fan Guang-quan,Zhang Gui-yun,Yang Bing-ru, Efficient Convex Hull Algorithm for Very Large Planar Point Set.2006,32(21):64-66