An algorithm for finding convex hulls of planar point sets
- 1 December 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 888-891
Abstract
This paper presents an alternate choice of computing the convex hulls (CHs) for planar point sets. We firstly discard the interior points and then sort the remaining vertices by x-/y- coordinates separately, and later create a group of quadrilaterals (e-Quads) recursively according to the sequences of the sorted lists of points. Finally, the desired CH is built based on a simple polygon derived from all e-Quads. Besides the preprocessing for original planar point sets, this algorithm has another mechanism of discarding interior point when form e-Quads and assemble the simple polygon. Compared with three popular CH algorithms, the proposed algorithm can generate CHs faster than the three but has a penalty in space cost.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Designing and proving correct a convex hull algorithm with hypermaps in CoqComputational Geometry, 2012
- GPU accelerated convex hull computationComputers & Graphics, 2012
- CudaHull: Fast parallel 3D convex hull on the GPUComputers & Graphics, 2012
- A fast convex hull algorithm with maximum inscribed circle affine transformationNeurocomputing, 2012
- An Efficient Convex Hull Algorithm for Planar Point Set Based on Recursive MethodActa Automatica Sinica, 2012
- Convex hull properties and algorithmsApplied Mathematics and Computation, 2010
- Self-improving Algorithms for Convex Hulls2010
- Another efficient algorithm for convex hulls in two dimensionsInformation Processing Letters, 1979
- On the identification of the convex hull of a finite set of points in the planeInformation Processing Letters, 1973
- An efficient algorith for determining the convex hull of a finite planar setInformation Processing Letters, 1972