Mètode de Graham

De Viquipèdia
Salta a la navegació Salta a la cerca

El mètode de Graham (Graham scan) és un mètode de càlcul computacional de l'envolupant convexa d'un grup finit de punts en el pla de complexitat. El nom fa honor a Ronald Graham, qui va publicar l'algorisme el 1972.[1] L'algorisme calcula tots els vèrtexs de l'envolupant convexa ordenats al llarg de la frontera. Pot ser modificat fàcilment per trobar els punts que, sense ser vèrtexs, pertanyen a aquesta envolupant.

Procediment[modifica]

Es comença pel punt de més avall (el punt amb menor coordenada en l'eix Y), al que anomenarem origen. Llavors s'ordena la distribució de punts basant-se en l'angle entre el punt origen i tots els altres punts. Després de l'ordenament, es va punt per punt eliminant aquells que no es troben a l'envolupant convexa. Aquest procés es fa en el sentit antihorari.

Si un angle entre tres punts gira cap a dins la forma no és convexa, de manera que podem treure aquest resultat. Podem trobar si una rotació és antihorària amb funcions trigonomètriques o mitjançant un producte creuat:

Si el resultat d'aquesta funció és 0 els punts són col·linears, si és positiva vol dir que van en sentit antihorari, i si és negativa en sentit horari. No volem rotacions en sentit horari ja que impliquen que estem en un angle interior.[1]

Vegeu també[modifica]

Referències[modifica]

  1. 1,0 1,1 Graham, R.L. (1972). An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Information Processing Letters 1, 132-133