DESCOMPOSICIÓN DE UNA FIGURA POLIGONAL SIN HUECOS EN UN CONJUNTO DE POLÍGONOS CONVEXOS POR MEDIO DE UN ALGORITMO EXACTO Y UNO APROXIMADO
Cargando...
Fecha
Título de la revista
ISSN de la revista
Título del volumen
Editor
Politécnico Grancolombiano
Resumen
Descripción
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.
Palabras clave
Descomposición convexa, Nesting, Polígonos, Geometría computacional