Implementación de algoritmos para calcular el Convex Hull

DOI: https://doi.org/10.31908/19098367.2668
Palabras clave: Convex Hull, Geometría computacional, Gift Wrapping, Graham Scan, QuickHull

Resumen

La geometría computacional es una disciplina enfocada en la resolución de problemas en el ámbito geométrico. En este contexto, el algoritmo para calcular el polígono convexo llamado Convex Hull (CH) es importante, debido a que es la base de muchos otros algoritmos. El objetivo de la investigación fue implementar algoritmos que calculan el CH incorporando modificaciones para reducir el tiempo de ejecución. El trabajo inició con la revisión bibliográfica acerca de geometría computacional y los algoritmos destacados en el cálculo del CH. Posteriormente, se realizó la implementación en JAVA de los algoritmos QuickHull, Gift Wrapping y Graham Scan en sus versiones originales; también se implementaron algunas versiones con modificaciones.  Al finalizar la implementación, se ejecutaron pruebas para verificar los tiempos de ejecución. Finalmente, se comprobó que el algoritmo QuickHull es el más rápido entre las implementaciones realizadas en esta investigación. También se nota reducción en los tiempos de ejecución en las implementaciones modificadas con relación a las originales de los algoritmos Gift Wrapping y Graham Scan.

Descargas

La descarga de datos todavía no está disponible.

Biografía del autor

Christian Andrés Candela Uribe., Universidad del Quindío, Universidad Tecnológica de Pereira

Estudiante del Doctorado en Ingeniería con énfasis en Ciencias de la Computación de la Universidad Tecnológica de Pereira. Profesor Asociado en la Universidad del Quindío Colombia. Sus áreas de interés son: Arquitectura de Software, Ingeniería de Software y Microservicios.

Julio César Chavarro Porras, Universidad Tecnológica de Pereira

Doctorado en Ingeniería con énfasis en Ciencias de la Computación de la Universidad del Valle. Profesor Asociado en la Universidad Tecnológica de Pereira Colombia. Sus áreas de interés son: Inteligencia Artificial, Arquitectura de Software, Ingeniería de Software y Bases de Datos.

Carlos Augusto Meneses Escobar, Universidad Tecnológica de Pereira

Estudiante del Doctorado en Ingeniería con énfasis en Ciencias de la Computación de la Universidad Tecnológica de Pereira. Profesor Asistente en la Universidad Tecnológica de Pereira Colombia. Sus áreas de interés son: Inteligencia Artificial, Arquitectura de Software, Ingeniería de Software y Bases de Datos.

John Alexander Sanabria Ordoñez, Universidad del Valle

Doctorado en Computer Information Science and Enginnering de la Universidad de Puerto Rico. Profesor Asistente en la Universidad del Valle Colombia. Sus áreas de interés son: Redes de computadores, Sistemas Distribuidos, Grid Computing y Plataformas Computacionales.

Citas

S. Bu-Qing and L. Ding-Yuan, Computational geometry: curve and surface modeling. Elsevier, 2014.

M. A. Jayaram and H. Fleyeh, "Convex Hulls in Image Processing: A Scoping Review," American Journal of Intelligent Systems, Artikel PeerReviewed no. 2, p. 48, 2016. [Online].

O. Y. Buitrago, A. L. Ramírez, and R. A. Britto, "Nuevo Algoritmo para la Construcción de la Envolvente Convexa en el Plano," New Algorithm to Construct a Planar Convex Hull., Article vol. 26, no. 4, pp. 137-144, 2015, doi: 10.4067/S0718-07642015000400017.

Y. Xu and W. Hou, "Calculation of operational domain of virtual maintenance based on convex hull algorithm," ed: IEEE, 2017, p. 1.

J. F. Peters, "Foundations of computer vision," ed: Springer International Publishing: 2017.

R. Xu, H. Dai, F. Wang, and Z. Jia, "A convex hull based optimization to reduce the data delivery latency of the mobile elements in wireless sensor networks," in 2013 IEEE 10th International Conference on High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing, 2013: IEEE, pp. 2245-2252.

H. Brönnimann, J. Iacono, J. Katajainen, P. Morin, J. Morrison, and G. Toussaint, "Space-efficient planar convex hull algorithms," Theoretical Computer Science, vol. 321, no. 1, pp. 25-40, 2004.

Z. Qihai, "New serial and parallel algorithms for finding convex hull based on clusters, domains and directions from single to multitude," Journal of Algorithms & Computational Technology, vol. 3, no. 2, pp. 191-227, 2009.

H.-Y. CHIANG, "Solving 2D Convex Hull with Parallel Algorithms," 2010.

N.-D. Hoang and N. K. Linh, "Quicker than Quickhull," Vietnam Journal of Mathematics, vol. 43, no. 1, pp. 57-70, 2015, doi: 10.1007/s10013-014-0067-1.

V. Skala, M. Smolik, and Z. Majdisova, "Reducing the number of points on the convex hull calculation using the polar space subdivision in E2," 2016.

A. N. Gamby and J. Katajainen, "Convex-hull algorithms: Implementation, testing, and experimentation," Algorithms, vol. 11, no. 12, p. 195, 2018.

A. N. Gamby and J. Katajainen, "A faster convex-hull algorithm via bucketing," in International Symposium on Experimental Algorithms, 2019: Springer, pp. 473-489.

K. Borna, "Sweep Line Algorithm for Convex Hull Revisited," Journal of Algorithms and Computation, vol. 51, no. 1, pp. 1-14, 2019.

J. Lesjak, "Pregled in primerjava algoritmov za izračun konveksne ovojnice," 2021.

F. P. Preparata and M. I. Shamos, "Computational Geometry An Introduction," in Computational Geometry: Springer, 1985, pp. 1-35.

J.-R. Sack and J. Urrutia, Handbook of computational geometry. Elsevier, 1999.

M. De Berg, O. Cheong, M. Van Kreveld, and M. Overmars, Computational Geometry: Algorithms and Applications, Third Edition ed. Springer, 2008.

J. o'Rourke and A. J. Mallinckrodt, "Computational geometry in C," Computers in Physics, vol. 9, no. 1, pp. 55-55, 1995.

W. F. Eddy, "A new convex hull algorithm for planar sets," ACM Transactions on Mathematical Software (TOMS), vol. 3, no. 4, pp. 398-403, 1977.

A. Bykat, "Convex hull of a finite set of points in two dimensions," Information Processing Letters, vol. 7, no. 6, pp. 296-298, 1978.

N. K. Linh, P. T. An, and T. Van Hoai, "A fast and efficient algorithm for determining the connected orthogonal convex hulls," Applied Mathematics and Computation, vol. 429, p. 127183, 2022.

D. M. Steier and A. P. Anderson, Algorithm Synthesis: A comparative study. Springer Science & Business Media, 2012.

D. R. Chand and S. S. Kapur, "An algorithm for convex polytopes," Journal of the ACM (JACM), vol. 17, no. 1, pp. 78-86, 1970.

R. L. Graham, "An efficient algorithm for determining the convex hull of a finite planar set," Info. Pro. Lett., vol. 1, pp. 132-133, 1972.

Publicado
2022-12-31
Cómo citar
Candela Uribe., C., Sepúlveda Rodríguez, L., Chavarro Porras, J., Meneses Escobar, C., Sanabria Ordoñez, J., & Arcila Guzmán, O. (2022). Implementación de algoritmos para calcular el Convex Hull. Entre Ciencia E Ingeniería, 16(32), 27-34. https://doi.org/10.31908/19098367.2668
Número
Vol. 16 Núm. 32 (2022)
Sección
Artículos
Derechos de autor 2023 Entre Ciencia e Ingeniería