Varredura de Graham: diferenças entre revisões

Depois, o conjunto de pontos deve ser ordenado em ordem crescente do ângulo que ele com o ponto ''P'' formam com o eixo X. Qualquer [[algoritmo ordenação]] de uso geral é apropriado para isto, por exemplo, o [[heapsort]] (o qual é da ordem de O(''n'' log ''n'')). De forma a acelerar os cálculos, não é necessário calcular os ângulos que estes pontos formam com o eixo x; ao invés disto é suficiente calcular a [[função trigonométrica|tangente]] deste ângulo, que pode ser feito com simples aritmética.

 

 

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 definidos definidos pelos pontos <math>(x_1,y_1)</math>, <math>(x_2,y_2)</math> e <math>(x_2,y_2)</math>, <math>(x_3,y_3)</math>. Se o resultado for Zero, os três pontos são colineares, se for positivo, os três pontos constituem uma "curva para esquerda", caso contrario uma "curva para direita".