A Total Order Heuristic-Based Convex Hull Algorithm for Points in the Plane. (January 2016)

• Record Type: Journal Article
• Authors: Gomes, Abel J.P.
• Is Part Of: Computer aided design. Volume 70(2016)
• Page Start: 153
• Page End: 160
• Publication Date: 2016-01
• Subjects: Convex hull -- Geometric algorithms -- Computational geometry; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2015.07.013
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: Computing the convex hull of a set of points is a fundamental operation in many research fields, including geometric computing, computer graphics, computer vision, robotics, and so forth. This problem is particularly challenging when the number of points goes beyond some millions. In this article, we describe a very fast algorithm that copes with millions of points in a short period of time without using any kind of parallel computing. This has been made possible because the algorithm reduces to a sorting problem of the input point set, what dramatically minimizes the geometric computations (e.g., angles, distances, and so forth) that are typical in other algorithms. When compared with popular convex hull algorithms (namely, Graham's scan, Andrew's monotone chain, Jarvis' gift wrapping, Chan's, and Quickhull), our algorithm is capable of generating the convex hull of a point set in the plane much faster than those five algorithms without penalties in memory space. Highlights: We propose a 2D convex hull algorithm based on comparison operators. We propose a 2D convex hull algorithm that outperforms Quickhull. We propose a 2D non-convex hull algorithm.