Entre Ciencia e Ingeniería · 2022

Implementation of algorithms to compute the Convex Hull

Resumen

Computational geometry is a discipline focused on solving problems in the geometric domain. In this context, the algorithm for computing the convex polygon called Convex Hull (CH) is important, because it is the basis for many other algorithms. The objective of the research was to implement algorithms that compute the CH incorporating modifications to reduce the execution time. The research started with a bibliographic review of computational geometry and the algorithms highlighted in the calculation of CH. Subsequently, the QuickHull, Gift Wrapping, and Graham Scan algorithms were implemented in JAVA in their original versions; some versions with modifications were also implemented. Upon completion of implementation, tests were run to verify the execution times. Finally, the QuickHull algorithm was found to be the fastest among the implementations performed in this research. It is also noted a reduction in execution times in the modified implementations in relation to the original ones of the Gift Wrapping and Graham Scan algorithms.