Convex Hull using Graham Scan...

Problema : Dada uma serie de pontos calcular o seu fecho convexo

Metodo :

1) Escolher o ponto mais baixo (mais proximo do eixo y) caso haja empate desempatar escolhendo aquele ponto que tiver a coordenada x menor

2) Calcular o cosseno do angulo entre o ponto mais baixo e todos os outros pontos da seguinte maneira :

2.1) Criar uma linha utilizando esse ponto mais baixo. O ponto inicial da linha será esse "ponto mais baixo" e o ponto final será um ponto com coordenada x um pouco maior que a coordanada x desse ponto mais baixo . Ex: Ponto mais baixo (2,2) a linha gerada poderia ser : (2,2) -> (3,2)

2.2) Criar uma linha ligando o ponto mais baixo ao ponto em analise que voce quer calcular o cosseno.

2.3) calcular o cosseno entre as linhas geradas. cos ( α ) = u.v ⁄ ( |u| |v| )
Fazer isso para todos os pontos do vetor de pontos

3) Organizar os pontos em ordem crescente de angulo

4) Adicionar ao vetor organizado ( na ultima posicao) o ponto que esta na primeira posicao. (desta maneira podemos verificar se o penultimo ponto esta ou nao no hull)

5) Tomar os pontos de tres em tres (seguindo a ordem crescente do seu vetor organizado) ate chegar ao fim do vetor . Analisar se eles fazer uma volta anti-horaria usando o seguinte principio:

Se (x2 -x1 ) (y3-y1)-(y2-y1) (x3-x1) = 0 alinhados
Se <0 horario
Se >0 Antihorario

Se P1,P2 e P3 estiverem em sentido horario deletar o ponto do meio desses tres pontos (nesse caso P2). Apos deletar qquer ponto , reiniciar o processo de verificacao (neste ponto , para otimizar o codigo vc pode verificar do fim para o comeco, partindo do ponto deletado) para assegurar que nenhum ponto anterior esta em sentido horario. Se nenhum ponto esta em sentido horario , prosseguir


Se P1,P2 e P3 eles estiverem em sentido antihorario prosseguir para P2,P3,P4 ...


e assim ate encontrar o primeiro ponto (que foi adicionado no final do vetor)


Resultado :


Qualquer duvida , comentem ... abraços !