Parcours de Graham
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche à compléter concernant la géométrie, vous pouvez partager vos connaissances en le modifiant. |
Le parcours de Graham se fait en 4 étapes :
- Recherche d'un point intérieur à l'enveloppe O
Pour ce faire, il suffit de prendre l'isobarycentre de trois points au hasard non alignés, le point obtenu sera forcément à l'intérieur de l'enveloppe
- Recherche d'un point appartenant à l'enveloppe P
Pour ce faire, on prend le point d'abscisse et d'ordonnée maximales.
- Tri des points par ordre polaire selon la demi-droite [OP])
- Elimination des tours gauches selon l'algorithme dit de la marche de Graham.
Cet algorithme est de complexité O(n.log(n)), soit la complexité de l'étape la plus coûteuse (le tri).
