摘要
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.
- 出版日期2012