Descomposición de una figura poligonal sin huecos en un conjunto de polígonos convexos por medio de un algoritmo exacto y uno aproximado

Abstract

La descomposición de una figura poligonal sin huecos en un conjunto de polígonos convexos es una técnica que se aplica en el empaquetamiento de formas irregulares, corte de material, entre otros. Una figura poligonal está compuesta únicamente por lados rectos sin espacios internos. Los polígonos convexos son figuras en las que una recta que une cualquier par de puntos dentro de la figura siempre estará contenida dentro ella. Estos polígonos son útiles en la geometría computacional dada su notación compacta para representarlos. En este trabajo, se propone un algoritmo exacto y un aproximado basados en trabajos previos de la literatura implementando mejoras para abordar el problema de la mínima descomposición convexa de polígonos. Primeramente, adaptamos un modelo exacto de la literatura, generando una variante que logra soluciones óptimas. Adicionalmente, desarrollamos un algoritmo heurístico que, aunque no obtiene soluciones óptimas, ha demostrado ser más rápido que otros en la literatura. Finalmente, implementamos un algoritmo de mejoramiento que busca la unión de subpolígonos convexos con el objetivo de reducir aún más el número de subpolígonos obtenidos por la heurística. Comparamos los algoritmos propuestos con otras metodologías de la literatura, utilizando instancias de las mismas para evaluar su desempeño. Ambas metodologías logran resolver de manera aceptable el problema. Observamos que la heurística junto con la unión de convexos presentó un desempeño superior al mismo sin la unión al reducir la cantidad de estos. Asimismo, se presenta una disminución del número de convexos tomando el algoritmo exacto con la restricción de que las partes divididas deben ser disjuntas, junto con la mejora de unión, en la cual las partes no necesariamente son disjuntas y se obtiene una disminución menor. La solución exacta es indiscutiblemente recomendada si no se requiere de bajo tiempo computacional. Como trabajo futuro, se sugiere la integración de estos algoritmos con enfoques relacionados al corte bidimensional de piezas irregulares.

The decomposition of a polygonal figure without gaps into a set of convex polygons is a technique applied in the packing of irregular shapes, cutting of material, among others. A polygonal figure is composed only of straight sides with no internal gaps. Convex polygons are figures in which a straight line joining any pair of points within the figure will always be contained within the figure. These polygons are useful in computational geometry because of their compact notation for representing them. In this paper, we propose an exact and an approximate algorithm based on previous work in the literature implementing improvements to address the problem of minimal convex decomposition of polygons. First, we adapt an exact model from the literature, generating a variant that achieves optimal solutions. Additionally, we developed a heuristic algorithm that, although it does not obtain optimal solutions, has proven to be faster than others in the literature. Finally, we implement an improvement algorithm that seeks the union of convex subpolygons with the objective of further reducing the number of subpolygons obtained by the heuristic. We compare the proposed algorithms with other methodologies in the literature, using instances of them to evaluate their performance. Both methodologies manage to solve the problem acceptably. We observed that the heuristic together with the union of convexes presented a superior performance to the same without the union by reducing the number of convexes. Likewise, a decrease in the number of convexes is presented by taking the exact algorithm with the restriction that the split parts must be disjoint, together with the improvement of union, in which the parts are not necessarily disjoint and a smaller decrease is obtained. The exact solution is indisputably recommended if low computational time is not required. As future work, the integration of these algorithms with approaches related to two-dimensional cutting of irregular parts is suggested.