DESCOMPOSICIÓN DE UNA FIGURA POLIGONAL SIN HUECOS EN UN CONJUNTO DE POLÍGONOS CONVEXOS POR MEDIO DE UN ALGORITMO EXACTO Y UNO APROXIMADO
DOI:
https://doi.org/10.15765/tfmky635Palabras clave:
Descomposición convexa, Nesting, Polígonos, Geometría computacionalResumen
La descomposición de una figura poligonal en un conjunto de polígonos convexos es útil en el empaquetamiento de formas irregulares y el corte de materiales. Los polígonos convexos permiten que cualquier línea entre dos puntos dentro del polígono permanezca en su interior, resaltando que la figura no es hueca. En este trabajo, proponemos un algoritmo exacto y uno aproximado mejorados para la mínima descomposición convexa de polígonos. Adaptamos un modelo exacto existente, logrando soluciones óptimas, y desarrollamos un algoritmo heurístico más rápido, aunque no siempre óptimo. También implementamos un algoritmo de mejora que une subpolígonos convexos para reducir su número. Comparamos nuestros algoritmos con otros y encontramos que la heurística combinada con la unión de convexos tuvo un desempeño superior. La solución exacta es recomendada cuando el tiempo computacional no es una limitación. Para trabajos futuros, se sugiere integrar estos algoritmos en enfoques de corte bidimensional de piezas irregulares.
Descargas
Referencias
Deng, B., Genova, K., Hinton, G., Yazdani, S., Tagliasacchi, A., & Bouaziz, S. (2020). CvxNet: Learnable Convex Decomposition. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR).
Falcó, J. (2022). Experimental Mathematics: Manipulative activities to visualize concepts (Vol. 16). Ediciones SM Spain.
Fernández, J., Cánovas, L., & Pelegrin, B. (2000). Algorithms for the decomposition of polygon into convex polygons. European Journal of Operational Research.
Keil, M. (1991). Decomposing a polygon into simpler components. Journal of Algorithms, (págs. 71-79).
Li, Z., Zhang, Z., Lui, H., & Yang, L. (2020). A new path planning method basedon concave polygon convexdecomposition and artificialbee colony algorithm. International Journal of Advanced Robotic Systems.
Lien, J., & Amato, N. (2005). Aproximate convex decomposition of polygons. European Journal of Operational Research.
Pantoja, G., Álvarez, R., Parreño, F., & Álvarez, D. (2022). Nueva mate-heurística para solucionar el Strip Packing Problem con piezas irregulares (SPPI). IV Congreso Colombiano de Investigación Operativa ASOCIO 2022 - IISE REGIÓN 16.
Saracevic, M., & Selimi, A. (2019). Convex polygon triangulation based on planted trivalent binary treeand ballot problem. Turkish Journal of Electrical Engineering and Computer Sciences.
Schachter, B. (1978). Decomposition of polygons into convex sets. IEEE Transactions on Computers.
Taranilla, M., Gagliardi, E., Leguizamón, M., & Hernández, G. (2007). Descomposición de Minkowski usando Algoritmos Genéticos. In IX Workshop de Investigadores en Ciencias de la Computación.
Wei, Z., Ding, S., Cheng, L., Xu, W., Wang, Y., & Zhang, L. (2022). Linear building pattern recognition in topographical maps combining convex polygon decomposition. Geocarto International, 1-25.
Descargas
Publicado
Número
Sección
Licencia
Derechos de autor 2024 Elementos
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0.
Los autores/as que publiquen en la Revista ELEMENTOS aceptan las siguientes condiciones:
- Los autores/as conservan los derechos de autor y ceden a la revista el derecho de la primera publicación, con el trabajo registrado con Creative Commons: Reconocimiento - No Comercial -Sin Obra Derivada, que permite a terceros utilizar lo publicado siempre que mencionen la autoría del trabajo y a la primera publicación en esta revista.
- Los autores/as pueden realizar otros acuerdos contractuales independientes y adicionales para la distribución no exclusiva de la versión del artículo publicado en esta revista (p. ej., incluirlo en un repositorio institucional o publicarlo en un libro) siempre que indiquen claramente que el trabajo se publicó por primera vez en esta revista.
- Se permite y recomienda a los autores/as a publicar su trabajo en Internet (por ejemplo en páginas institucionales o personales) antes y durante el proceso de revisión y publicación, ya que puede conducir a intercambios productivos y a una mayor y más rápida difusión del trabajo publicado.
Panorama by Institución Universitaria Politécnico Grancolombiano is licensed under a Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Unported License.
