Utilizando o CGAL para a construção de No Fit Polygons

 O presente trabalho situa-se no contexto dos problemas de empacotamento de peças irregulares em faixa, em que, dentro de uma placa de altura fixa e comprimento ilimitado deveremos alocar peças convexas ou não-convexas utilizando o menor comprimento possível e garantindo que essas peças não se sobreponham. Problemas como esses ocorrem em diversas indústrias, como empresas de corte de metal e têxtil. Por se tratar de um problema NP-Completo, devido ao uso de peças irregulares, ou seja, que não pode ser resolvido por um algoritmo de tempo polinomial, torna-se um desafio computacional. Em outras palavras, conforme vamos aumentando a quantidade de peças, cresce a complexidade do problema, e, por isso, torna se necessário o uso de computadores e métodos mais robustos para encontrar a solução ótima, caso ela exista.

 O algoritmo que utilizamos é o No Fit Polygon (NFP), neste algoritmo, consideramos uma peça fixa A, que possui um ponto de referência na origem, ou seja, no par ordenado (0,0), e uma peça B a qual denominaremos orbital. Definimos que o NFP_AB é obtido ao deslizarmos a peça B ao redor de A, garantindo que as peças sempre se toquem, mas jamais se sobreponham. Ao final, teremos um polígono que será utilizado para verificação de sobreposição entre as peças A e B. Assim, se o ponto de referência da peça B estiver dentro do NFP_AB, ocorre a sobreposição das peças, se estiver fora não há intersecção entre elas, e por fim, se estiverem na borda as peças se tocam.

 Outra questão que aumenta a complexidade do problema é a existência de peças de formato não convexo. Neste caso podemos decompor a peça não convexa em uma união de partes convexas. Um polígono é convexo se ao traçarmos um seguimento de reta entre quaisquer dois pontos dentro do polígono, todos os pontos deste segmento pertencerem ao interior da peça. Ao tratarmos de polígonos não convexos, retornamos ao ponto do aumento da complexidade computacional necessária para a resolução, neste caso, podemos adotar uma estratégia onde realizamos a decomposição desses polígonos convexos (que chamaremos de subpeças). Assim, podemos realizar com mais facilidade o NFP entre essas subpeças convexas. Por definição a união entre esses NFP será o NFP_AB.

 Neste trabalho, implementamos uma solução computacional em C++, para obter o NFP entre peças convexas ou não, utilizando a biblioteca CGAL que possui foco em geometria computacional, para a construção do NFP, e a biblioteca SFML, oferecendo recursos eficientes para a visualização. O produto final foi um sistema onde o usuário informa a quantidade de vértices dos polígonos e suas respectivas coordenadas cartesianas, e o programa devolve o NFP gerado.