SymmetricHull: A Convex Hull Algorithm Based on 2D Geometry and Symmetry

Owing to the advances in hardware (sensors and cameras) the number of points that convex hull algorithms must process is now much greater than when these algorithms were developed. This limitation entails focusing current research in convex hull algorithms on finding approaches capable of processing large sets of points. From the many works proposed in this area, the heuristic by Akl-Toussaint deserves a special mention, with outstanding results in execution times. In this article, we take the basic principles of this heuristic to create a convex hull algorithm, called SymmetricHull, that takes advantage of geometric and symmetric properties of the formed quadrants in 2D spaces. Our algorithm achieves better execution times than that heuristic, reducing the basic operations to a series of comparisons between consecutive points in an array lexicographically sorted by its y coordinate (i.e., in ascending order). SymmetricHull organizes the set of points by quadrants and, instead of using the orientation function, as the main operation, it appends the slope s between the analyzed point and its predecessor as a property of the point structure, without causing numerical errors. Our experiments show that SymmetricHull optimizations achieve good results, in terms of time and number of operations required (multiplications, sums, pushs and pops), being especially efficient with point sets greater than 10(4).