An Algorithm for Finding Convex Hulls of Planar Point Sets

作者:Mei Gang*; Tipper John C; Xu Nengxiong
来源:2nd International Conference on Computer Science and Network Technology (ICCSNT), 2012-12-29 to 2012-12-31.

摘要

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