The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences
Publications Copernicus
Download
Citation
Articles | Volume XXXIX-B2
https://doi.org/10.5194/isprsarchives-XXXIX-B2-63-2012
https://doi.org/10.5194/isprsarchives-XXXIX-B2-63-2012
25 Jul 2012
 | 25 Jul 2012

AN EFFICIENT ALGORITHM FOR THE CONVEX HULL OF PLANAR SCATTERED POINT SET

Z. Fu and Y. Lu

Keywords: Scattered Point Set, Minimum Convex Hull, Convex Hull Algorithm, Initial Boundary of Convex Hull

Abstract. Computing the convex hull of a point set is requirement in the GIS applications. This paper studies on the problem of minimum convex hull and presents an improved algorithm for the minimum convex hull of planar scattered point set. It adopts approach that dividing the point set into several sub regions to get an initial convex hull boundary firstly. Then the points on the boundary, which cannot be vertices of the minimum convex hull, are removed one by one. Finally the concave points on the boundary, which cannot be vertices of the minimum convex hull, are withdrew. Experimental analysis shows the efficiency of the algorithm compared with other methods.