Come Voronoi ti aiuta a trovar la fidanzata

Mi viene in mente una storia che mi successe tanti anni fa, talmente tanti che potrebbe cominciare con “c’era una volta….” 😀

Dunque, un mio amico ed io eravamo in bus, mentre stavamo tornando a casa da lezione ( all’epoca frequentavamo le scuole medie ). Mentre chiacchieravamo del più e del meno, il mio amico si zittisce all’improvviso e comincia a cercare di imitare un geco, spiattellandosi sul vetro del finestrino laterale del bus.

Rimase in quella posizione per 3 o 4 fermate di fila suscitando la mia curiosità.

“Da queste parti spesso sale la ragazza più bella del mondo, ma non sono mai riuscito ad attaccarci discorso né a capire dove stia di casa. Ogni volta che passo di qui cerco di vederla e nel caso scendo per cercare di correrle dietro. Tu hai qualche idea su cosa fare per beccarla o almeno per sapere dove andare a cercarla ?”

Onestamente non mi vennero idee. E lui concluse che o sarebbe andato a farsi benedire presso un’eremo sperduto o si sarebbe messo a camminare in quella zona, battendo ogni strada per cercare di incontrarla o forse, meglio, avrebbe fatto entrambe le cose.

Ma poi seppi che nonostante tutto, i suoi sforzi non andarono a buon fine.

Se al giorno d’oggi il mio amico mi avesse posto la stessa domanda gli avrei risposto “Prova ad usare una tassellatura del Voronoi, che magari non vagoli a vuoto!”

Ma cosa è questa “tassellatura” che avrebbe potuto aiutare il mio amico a trovare la fidanzatina ? Detto in parole povere e limitandoci a considerare un piano e non un volume, una tassellatura è un modo di ricoprire un piano con delle regole fissate a priori usando delle figure geometriche, in modo che nessuna parte del piano sia esclusa e senza che ci siano sovrapposizioni.

Semplice esempi di tassellautre regolari  vengono mostrati dalle seguenti figure.

            

Ma vorrei divagare un attimo, per giungere a vedere come funziona il metodo di  Voronoi tramite una serie di esempi e non tramite dei formalismi.

Immaginiamo di avere un  formicaio in uno spazio piano. Usiamo il formicaio come un esempio puramente didascalico, ma potrei parlare di una tribù di indiani, di una colonia di cellule, di una persona che in giorni successivi fa percorsi diversi a partire dallo stesso punto; la dinamica sarebbe sempre la stessa e quindi, ai nostri fini cambierebbe ben poco.

Dicevamo del nostro formicaio: se il cibo è distribuito omogeneamente nello spazio attorno ad esso, le formiche, per raccogliere il cibo, si irradieranno dal formicaio omogeneamente in tutte le direzioni fino a raggiungere una distanza massima per cui non conviene più portare cibo indietro verso il formicaio.

Ma se i formicai sono due, cosa accade in quel caso? Se la distanza fra loro è superiore alla distanza massima per cui è conveniente riportare indietro il cibo, i 2 formicai sono due isole felici ignari della presenza l’uno dell’altro. Ognuno raccoglie cibo nella sua zona senza essere consapevole della presenza dell’altro.

Ma se i due formicai sono più vicini ? Cosa cambia ?

Ci sarà una zona posta fra le due rispettive aree di raccolta del cibo in cui esse si sovrappongono.

E questo cosa comporta ? Comporta che quando una formica di un formicaio si trova in quella zona si troverà contemporaneamente anche nella zona di raccolta dell’altro formicaio. Nel caso in cui in questa zona si trovino contemporaneamente formiche di entrambi i formicai, come minimo, si attaccheranno a vicenda cercando di spingere le avversarie fuori della propria zona di procacciamento del cibo.

Alla fine le formiche, per evitare di essere sempre in conflitto con le vicine cercheranno di stare sempre dalla loro parte rispetto ad una linea immaginaria che incrocia a 90° la linea che unisce i due formicai. In ogni punto oltre tale linea saranno più vicini al formicaio avversario che al proprio: nella figura sopra questo confine non scritto è rappresentato dalla fascia azzurra.

E se i formicai sono 3 ? Nessun problema !

Accade la stessa identica cosa. A separare il territtorio ci saranno delle linee immaginarie che si trovano poste fra i formicai, poste a distanza identica fra ogni coppia possibile di formicai (FG,FH,GH). Queste linee di confine avranno la proprietà di essere ortogonali alle linee che uniscono i  2 formicai più vicini e di trovarsi esattamente a metà strada fra i 2. ( vedi figura sopra )

E quando abbiamo n formicai ? La procedura da seguire è sempre la solita!

Prima si costruisce la rete di triangoli che connette i 2 punti più vicini ( triangolazione di Delaunay – in inglese ) e poi su questa rete si costruiscono le rette ortogonali che passano per il punto medio di ogni segmento.

E tutto questo ci porta ad ottenere una divisione del piano ( un partizionamento del piano )  secondo delle regole prefissate. Il diagramma che ne risulta viene detto “Diagramma di Voronoi“. Questo diagramma ci consente di individuare in quali aree le formiche di un certo formicaio possono andare senza incorrere nel rischio di finire a scontrarsi con le formiche rivali.

Nota bene: alcune aree sono finite, altre sono infinite. Ma tutte hanno la stessa identica proprietà: all’interno di una certa area si è più vicini al proprio formicaio che a tutti gli altri.

E tutto questo come poteva aiutare il mio compagno di classe a trovare la fidanzatina ?

Se invece dei formicai, avesse segnato le fermate dei bus, ed invece della zona dove le formiche raccolgono il cibo ci fosse stata la distanza …… 😉

… e non dico altro per non guastarvi il gusto di capire da soli come funziona la cosa.

E magari, se vi venisse in mente qualcos’altro e me lo voleste far sapere, mi rendereste felice.

🙂

PS: ci sono anche altre cose che si possono evincere da questo diagramma, ma per ora vorrei che ognuno ci ragionasse con la sua testa. 😉

Advertisements

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...