Desenvolvimento de algoritmo para executar operações booleanas não regularizadas em regiões poligonais para aplicação na determinação de regiões de obstrução

Resumo

Um problema fundamental no problema de empacotamento irregular é a determinação eficiente do polígono de obstrução. O polígono de obstrução é criado a partir de dois polígonos, definindo a região em que um polígono móvel pode ser posicionado sem colidir com o polígono fixo. O polígono de obstrução ainda não é amplamente utilizado pelos pesquisadores envolvidos com o problema do posicionamento pela dificuldade em implementá-lo. Em um trabalho de pesquisa realizado pelo proponente, uma primeira versão do algoritmo de definição do polígono de obstrução por meio de operações Booleanas regularizadas foi implementado (durante o programa de doutorado de Thiago de Castro Martins). Diversos estudos comparativos existentes na literatura fazem uso de encaixes perfeitos, sendo necessário utilizar operações Booleanas não regularizadas na determinação do polígono de obstrução. Neste projeto, será desenvolvida uma implementação aprimorada para realizar operações Booleanas não regularizadas (polígonos que não possuem o seu contorno). Desta maneira problemas de encaixe perfeito poderão ser testados. Também, os nossos resultados atuais indicam que o posicionamento sobre os vértices dos polígonos de obstrução aceleram o algoritmo, reduzindo o tempo de processamento e aumentando a probabilidade do algoritmo convergir para o ótimo global. (AU)