A Total Order Heuristic-Based Convex Hull Algorithm for Points in the Plane |
| |
Affiliation: | 1. School of Aerospace Engineering and Applied Mechanics, Tongji University, Shanghai 200092, China;2. Shanghai Key Laboratory of Vehicle Aerodynamics and Vehicle Thermal Management Systems, Tongji University, Shanghai 201804, China;3. CSIRO Energy, 71 Normanby Road, Clayton, VIC 3169, Australia |
| |
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. |
| |
Keywords: | Convex hull Geometric algorithms Computational geometry |
本文献已被 ScienceDirect 等数据库收录! |
|