Translações Aplicadas a Polígonos de Obstrução para que Regiões Livres de Colisão Degeneradas Sejam Criadas por Operações Booleanas Não Regularizadas

Resumo

Durante o programa de mestrado foi pesquisado, proposto e desenvolvido um algoritmo para a determinação correta e eficiente do polígono de obstrução e da região livre de obstrução. A determinação correta do polígono de obstrução e da região livre de obstrução implica em representar polígonos degenerados com arestas e vértices salientes. A determinação eficiente, por outro lado, implica em determinar o resultado correto em tempo computacional razoável. Quando existirem arestas e/ou vértices salientes no resultado final, indica que existe uma situação de encaixe perfeito e, portanto, um mínimo local. Resultados obtidos com o algoritmo desenvolvido demostram ser muito competitivos com resultados publicados na literatura, em algumas situações melhoramos os resultados publicados. Entretanto, o tempo computacional se apresenta demasiadamente elevado. Durante o doutorado, será pesquisado, proposto e desenvolvido um algoritmo que determinará translações que ao serem aplicadas a polígonos de obstrução criem arestas e/ou vértices degenerados. As translações serão aplicadas tanto na criação sequencial item a item de leiautes, bem como na manipulação de itens já posicionados em leiautes já definidos. Os leiautes já definidos possuem dois tipos de itens posicionados: fixos e móveis. Os itens que podem ser movimentados são apenas os móveis. Também serão estudadas formas de paralelizar a determinação da região livre de colisão. Desta maneira, o recozimento simultado possuirá como soluções candidatas apenas mínimos locais e consequentemente deverá localizar o mínimo global em menor tempo computacional.