An algorithm for finding convex hulls of planar point sets

摘要

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.