Nos algoritmos de Geometria Computacional, precisamos de um algoritmo de ordenação polar (dados vetores x1, x2, ... , xn do R², devemos ordená-los angularmente no sentido anti-horário).
Muita opções de algoritmos são custosas, requerendo trabalhos com arccos(x), o que pode acarretar em perdas significativas de desempenho.
A opção menos custosa, e, portanto, utilizada nos trabalhos posteriores, é a do cálculo do pseudo-ângulo no quadrado unitário, cujo cálculo pode ser feito de modo a envolver apenas três comparações, uma soma e uma divisão.
Nesse algoritmo, o ângulo é substituído pelo comprimento do percurso nas arestas do quadrado partindo do ponto (1,0), tomando valores de [0, 8]. É verificado em qual quadrante o ponto está, e se a
semi-reta que vai do centro desse quadrado até o ponto intercepta a aresta do quadrado antes ou depois do vértice pertencente
ao mesmo quadrante do ponto. Com essas informações, é possível calcular parte do pseudo-ângulo. O restante é calculado por semelhança de triângulos, custando apenas uma divisão.
Acesse o meu código de pseudo-ângulo: https://dl.dropboxusercontent.com/u/21447748/Pseudoangulo.rar
O código acima possui senha, disponibilizada apenas para o professor da disciplina.
