Varredura de Graham: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
→O Algoritmo:
Correcção do português. |
→O Algoritmo:
Remoção da repetição "definidos" |
||
Linha 19:
O algoritmo procede considerando cada um dos pontos do array ordenado em sequência. Para cada ponto, é determinado, se ao mover-se dos dois pontos anteriores para este ponto se forma uma "curva para esquerda" ou uma "curva para direita". Se é uma "curva para direita", isto significa que o ponto de partida não faz parte do envoltório convexo e deve ser removido da pesquisa. Este processo continua ao longo do conjunto até que o conjunto dos três últimos pontos seja uma curva para direita. Assim que uma "curva para esquerda" é encontrada, o algoritmo salta para o próximo ponto do array ordenado. ( Se em qualquer etapa três pontos são colineares, é indiferente se o ponto do meio é removido ou não. Removendo-o obteremos um envoltório convexo mínimo, mas o mantendo isto não o inválida).
Novamente, para determinar se três pontos constituem uma "curva a esquerda" ou "curva a direita" não é necessário calcular o ângulo existente entre os dois segmentos de retas, isto pode ser obtido simplesmente por aritmética inteira. Dado três pontos <math>(x_1,y_1)</math>, <math>(x_2,y_2)</math> e <math>(x_3,y_3)</math>, simplesmente calculando o [[produto vetorial]] <math>(x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)</math> dos dois [[vetor]]es
Este processo irá eventualmente retornar ao ponto de início, neste ponto o algoritmo estará concluído e o array agora contém os pontos do envoltório convexo no sentido anti-horário.
| |||