Teste de ponto em polígono usando o algoritmo do Número de Voltas
Recentemente comecei a trabalhar na Tecgraf PUC-Rio e precisei resolver um problema interessante: dado um polígono desenhado pelo usuário, o sistema deve selecionar todos os objetos contidos, total ou parcialmente, em seu interior. Introdução À primeira vista esse problema parece apenas mais um teste de interseção entre polígonos. Como o sistema trabalha em 2 dimensões a minha primeira ideia foi utilizar o Teorema do Eixo Separador (SAT). Entretanto, o polígono de seleção pode possuir qualquer formato, sendo convexo ou côncavo. O SAT, por outro lado, pressupõe que ambos os polígonos sejam convexos. Para utilizá-lo seria necessário decompor previamente o polígono de seleção em um conjunto de polígonos convexos menores, utilizando algoritmos como Ear Clipping, e somente então executar os testes de interseção. ...