Comencem l'aventura. Imagineu-vos que tenim una empresa de transport amb diverses centrals de distribució, cada punt de la imatge representa un d'aquests centres:
Ara imagineu-vos que hem de determinar les zones que ha de cobrir cada central de distribució de manera que haguem de viatjar el mínim possible. És a dir, hem de determinar les zones del pla que estan més properes a cada punt.Per calcular aquestes zones cal seguir una sèrie de passos. Primer hem d'aplicar l'algoritme de Delaunay, que consisteix a traçar triangles entre els vèrtexs amb certes restriccions que ara veurem. Vegem una possible triangulació:
Aquesta és una forma de triangular, però per al nostre propòsit no és vàlida. Hem d'aconseguir una triangulació de manera que qualsevol circumferència traçada entre els 3 vèrtexs de cada triangle no tingui cap altre punt dins. Ho veurem més clar amb una imatge que demostra que la triangulació anterior no era vàlida:
Com solucionem el problema? Doncs provant diverses triangulacions (Hi ha un mètode complicat d'explicar que ho fa molt bé) fins que no hi hagi cap circumferència que toqui més de 3 vèrtexs. En el nostre cas només hem de canviar una aresta:
Fixeu-vos que hem canviat una mica la triangulació i ara en traçar la circumferència ja no tenim cap altre vèrtex interior. Si fem el mateix amb la resta de triangles veiem que hem aconseguit que no tinguin altres vèrtexs dins, en aquest moment hem aconseguit la Triangulació de Delaunay a partir dels vèrtexs / centrals de distribució inicials. A la següent imatge tracem totes les circumferències possibles, fixeu-vos que cap toca més de 3 vèrtex.
Pufff, una mica embolicat. A continuació hem de calcular les regions més properes a cada punt (A aquestes regions les anomenarem Regions de Voronoi). Per a això ens recolzarem en la Triangulació de Delaunay que ja hem calculat. Marquem el punt central de cada circumferència i tracem Perpendiculars a les arestes dels triangles. Ho veurem amb dos dels cercles per no embolicar (Els punts grocs són els centres de les circumferències i les línies taronges són perpendiculars a les arestes dels triangles):
Si seguim aplicant el mateix mètode (i eliminem del dibuix els cercles per no liar) obtindrem el següent:
Si a més eliminem la Triangulació de Delaunay, tindrem la imatge definitiva on es defineixen les zones més properes a cada centre de distribució:
Per exemple, la zona acolorida de verd és la Regió de Voronoi del punt A. Això vol dir que tot el que està pintat de verd està més a prop de A que de qualsevol altre punt del dibuix. Ho podeu comprovar amb una regla si no us convenço:
Cap comentari:
Publica un comentari a l'entrada