Algorisme de l'embolcallament
En geometria computacional, l'algorisme de l'embolcallament (de l'anglès Gift wrapping algorithm) és un algorisme per calcular l'envolupant convexa d'un sistema finit de punts. Tal com el nom suggereix, la idea principal de l'algorisme és embolcallar el conjunt de punts com si es tractés d'un paper de regal, definint-lo a partir d'un punt i estirant-lo i girant-lo al voltant del núvol de punts fins a ternir-los tots recoberts.
Tot i que es pot generalitzar a 3 dimensions o més, l'algorisme va ser inicialment descrit per ser aplicat en 2 dimensions sobre un pla; en aquest cas també rep el nom de Jarvis march, en honor de Ray Jarvis, qui va publicar l'algorisme el 1973.[1]
L'algorisme no és gaire eficient; té un temps de processament O(nh) on n és el nombre total de punts i h la mida de l'envolupant. És per aquest motiu que posteriorment han sortit altres algorismes com el mètode de Graham o l'algorisme de Chan, que partint d'una idea similar utilitzen diversos trucs per augmentar l'eficiència.
Procediment[modifica]
Si comencem amb una distribució de punts a l'atzar, podem trobar l'envolupant convexa partint del punt de més a l'esquerra (el punt amb menor coordenada en l'eix X) i utilitzant-lo d'origen per calcular un angle entre aquest i qualsevol altre punt de la simulació. D'aquesta manera identifiquem el punt amb major angle interior i l'escollim com a següent punt de l'envolupant; al fer-ho tracem una línea entre els dos punts. Llavors, podem utilitzar el nou punt per calcular de nou els angles amb la resta de punts i fer el mateix. Aquest procediment es va repetint fins que retornem al punt inicial. El grup format per tots els punts escollits durant el procediment formaràn l'embolcall, és a dir, l'envolupant convexa.[1]