Varredura de Graham: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m r2.7.1) (Robô: A adicionar: fa:پیمایش گراهام |
m Checkwiki + ajustes |
||
Linha 1:
O ''' Exame de Graham''', cuja a denominação vem de [[Ronald Graham]], é uma técnica de computação usada para determinar o [[envoltória convexa]] de um dado conjunto de pontos no plano como [[complexidade de tempo]] [[notação O|O]](''n'' log ''n'').
== O Algoritmo ==
{| class="infobox" style="align: center; width: 160px; font-size: 90%;"
|+
; Ilustação
|
[[Ficheiro:Graham scan.png]]
Linha 27 ⟶ 28:
Find pivot P;
Sort Points by angle (resolve ties in favor of point farther from P);
Stack.push(Points[1]);
Stack.push(Points[2]);
Linha 46 ⟶ 47:
ENDIF
NEXT i
FUNCTION Cross_product(p1, p2, p3)
RETURN (p2.x - p1.x)*(p3.y - p1.y) - (p3.x - p1.x)*(p2.y - p1.y);
Linha 56 ⟶ 57:
== Ligações Extenas ==
*
{{Portal3|Tecnologias de informação}}
{{DEFAULTSORT:Exame Graham}}
[[Categoria:Algoritmos]]
[[Categoria:Teoria dos grafos]]
| |||