1. Obter um dos vértices do conjunto de pontos. No meu algoritmo, tomo o ponto de menor ordenada (suponhamos que tal ponto seja p1). Se houver mais de um ponto com a mesma ordenada mínima, tomamos entre eles o de maior abscissa.
2. O ponto que se segue a p1 no fecho convexo no sentido anti-horário pode ser obtido da seguinte forma: tomamos a semi-reta paralela ao semi-eixo horizontal positivo Ox passando por p1 e giramos tal semi-reta em torno de p1 no sentido anti-horário até que um ponto p2 seja atingido. Caso mais de um ponto se encontrar sobre sobre a semi-reta, tomamos o ponto mais distante de p1).
3. A partir de p2, giramos a semi-reta obtida prolongando p1p2 também no sentido anti-horário, até determinar p3, e assim por diante, até que retornemos ao ponto p1.
Pseudo-código:
Algoritmo de Jarvis
p1 = ponto de ordenada mínima
p2 = próximo(p1, (1,0))
i = 2
repita
pi+1 = próximo(pi, pipi-1)
i = i+1
até que pi = p1
Esse algoritmo determina corretamente o fecho convexo, mas não é ótimo. A determinação do vértice seguinte requer tempo O(n). Como é possível que cada ponto de C seja vértice, esta determinação ocorre também O(n) vezes, resultando em um algoritmo O(n²).
Portanto, para melhorar o desempenho, o método que adotei foi o seguinte:
1. Geração de n pontos aleatoriamente.
2. Classificação por pseudo-ângulos.
Ao pegarmos o ponto de menor y, calculamos, para todos os outros
pontos, os seus valores de pseudo-ângulo.
Depois, selecionamos
o de menor valor e usamos ele como base para o cálculo dos outros valores de pseudo-ângulo. O algoritmo
continua até que o ponto encontrado na n-ésima iteração, ou seja, no primeiro ponto.
 |
| Cálculo dos pseudo-ângulos a partir do ponto inicial (marcado com 0) |
Acompanhe nos slides abaixo o funcionamento do algoritmo que implementei:
Código disponível para download exclusivo do professor da disciplina: https://dl.dropboxusercontent.com/u/21447748/ConvexHull.rar
Nenhum comentário:
Postar um comentário