Mètode de Graham
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, amb una complexitat computacional O(n log n). 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
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. Generalment, aquest procés es fa en el sentit antihorari.
Si un angle entre tres punts gira cap a dins, això implica que 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·lineals, 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]
Variants
La mateixa idea també funciona si els punts s'ordenen segons la seva coordenada X en lloc de l'angle, i el casc es calcula en dos passos produint la part superior i la inferior del casc respectivament. Aquesta modificació va ser ideada per A. M. Andrew[2] i té les mateixes propietats bàsiques que l'algorisme de Graham.[3]
La tècnica d'escaneig utilitzada en el mètode de Graham és molt similar a la del problema de valors petits més propers, així que el mètode es pot utilitzar juntament amb algorismes paral·lels per calcular eficientment cascos convexos de seqüències ordenades de punts.[4]
Vegeu també
Referències
Enllaços externs
- Podeu veure una descripció acurada i exemples en diversos llenguatges de programació de l'Algorisme de cadena monòtona de A. M. Andrew a Wikibooks (anglès)