A Total Order Heuristic-Based Convex Hull Algorithm for Points in the Plane
| العنوان: | A Total Order Heuristic-Based Convex Hull Algorithm for Points in the Plane |
|---|---|
| المؤلفون: | Abel J. P. Gomes |
| المصدر: | Computer-Aided Design. 70:153-160 |
| بيانات النشر: | Elsevier BV, 2016. |
| سنة النشر: | 2016 |
| مصطلحات موضوعية: | Convex hull, Mathematical optimization, Convex hull algorithms, Quickhull, 0206 medical engineering, Convex set, 020207 software engineering, 02 engineering and technology, Computer Graphics and Computer-Aided Design, Industrial and Manufacturing Engineering, Computer Science Applications, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, 0202 electrical engineering, electronic engineering, information engineering, Output-sensitive algorithm, Convex combination, Gift wrapping algorithm, Algorithm, 020602 bioinformatics, Orthogonal convex hull, Mathematics |
| الوصف: | 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. 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. |
| تدمد: | 0010-4485 |
| DOI: | 10.1016/j.cad.2015.07.013 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::dcb51dc93f8edbecc936d77366a5d7cf https://doi.org/10.1016/j.cad.2015.07.013 |
| Rights: | CLOSED |
| رقم الانضمام: | edsair.doi...........dcb51dc93f8edbecc936d77366a5d7cf |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 00104485 |
|---|---|
| DOI: | 10.1016/j.cad.2015.07.013 |