Matematicamente

venerdì 21 agosto 2009

Diagrammi Di Voronoi E Triangolazioni Di Delaunay

Cari ragazzi e cari lettori, avete mai sentito parlare dei diagrammi di Voronoi? Ebbene, in matematica, un diagramma di Voronoi (dal nome di Georgii Voronoi), anche detto tassellatura di Voronoi, decomposizione di Voronoi, o tassellatura di Dirichlet (dal nome di Lejeune Dirichlet) consiste in un partizionamento del piano in n poligoni derivati da n punti principali, dove ciascun poligono contenga uno solo degli n punti principali e dove ogni altro punto del poligono sia più vicino al punto principale del poligono che a tutti gli altri punti principali. Il perimetro di ciascun poligono è a metà strada tra due punti principali.

Segue un esempio di tassellatura di Voronoi:


voronoi2


Un diagramma di Voronoi è dunque un particolare tipo di decomposizione di uno spazio metrico, determinata dalle distanze rispetto ad un determinato insieme discreto di elementi dello spazio (ad esempio, un insieme finito di punti).


Nel caso più semplice e comune, quello del piano, dato un insieme finito di punti S, il diagramma di Voronoi per S è la partizione del piano che associa una regione V(p) ad ogni punto p \in S in modo tale che tutti i punti di V(p) siano più vicini a p che ad ogni altro punto in S.


L'utilizzo informale dei diagrammi di Voronoi può essere fatto risalire a Cartesio nel 1644. Dirichlet utilizzò diagrammi di Voronoi bidimensionali e tridimensionali nei suoi studi delle forme quadratiche, nel 1850. Il medico britannico John Snow utilizzò un diagramma di Voronoi nel 1854 per illustrare come la maggioranza delle persone morte nell'epidemia di colera a Soho viveva più vicino ad una delle pompe infette di Broad Street che ad ogni altra pompa d'acqua.


Le tassellature di Voronoi traggono, come detto sopra, il loro nome dal matematico russo Georgii Fedoseevich Voronoi che definì e studiò il caso generale n-dimensionale nel 1908. I diagrammi di Voronoi che trovano applicazione in geofisica e in meteorologia per analizzare dati distribuiti spazialmente (come ad esempio misure delle precipitazioni) sono detti poligoni di Thiessen, dal nome del meteorologo americano Alfred H. Thiessen.


Si può sfruttare la struttura di un diagramma di Voronoi per scoprire il punto di S più vicino ad un punto dato x  senza calcolare ad ogni richiesta la distanza di x da ogni elemento di S. Una tale ricerca può avere applicazioni geografiche in sistemi informativi geografici (ad esempio "trova l'ospedale più vicino ad una data abitazione") o nella ricerca di elementi simili in un database.


I diagrammi di Voronoi sono anche utili nella fisica dei polimeri, dove possono essere infatti utilizzati per rappresentare il volume libero del polimero. Vi sono, inoltre, utili applicazioni nello studio delle capacità delle reti wireless.


Segue l'immagine di una struttura realizzata con l'utilizzo del diagramma 3D di Voronoi.


modello3d


Adesso un'applicazione ottenuta con  Rhino 4.0, che ha permesso di realizzare una semplice struttura a 2.5 dimensioni basata su diagrammi di Voronoi.



voronoi-rhino


Un diagramma di Voronoi da Wikipedia.



voronoiwikipedia


Una proprietà di questo tipo di tassellature è che il grafo duale per un diagramma di Voronoi corrisponde alla triangolazione di Delaunay rispetto allo stesso insieme di punti S. La triangolazione di Delaunay è, tra le molte possibili, una particolare triangolazione univocamente determinata dalla posizione dei punti P che gode di particolari proprietà geometriche. Esistono algoritmi efficienti e robusti per la costruzione della triangolazione di Delaunay a partire da un arbitrario insieme di punti dati. La triangolazione di Delaunay è il duale di un'altra costruzione geometrica nota come tassellatura di Dirichlet.

 



Ci sono molti algoritmi per costruire la triangolazione di Delaunay. Tra questi, due sono particolarmente utilizzati:


1. Algoritmo di Bowyer-Watson


2. Algoritmo di Green-Sibson


Per approfondire la triangolazione di Delaunay e i due algoritmi citati vi rimando a questa risorsa in rete.


Alcuni link per approfondire in rete.


Diagrammi interattivi di Voronoi and Delaunay (con codice sorgente)


Applet interattiva per la creazione di diagrammi di Voronoi


Applet per il calcolo e la visualizzazione di inviluppi convessi, triangolazioni di Delaunay e diagrammi di Voronoi nello spazio


Diagrammi di Voronoi su Mathworld


Algoritmo Quick hull per il calcolo dei diagrammi di Voronoi in 2 o più dimensioni


Applicazioni dei Diagrams di Voronoi: dall'Archeologia alla Zoologia


Di seguito diagrammi di Voronoi e triangolazioni di Delaunay realizzate da Fernando Cinquegrani. Fare clic sull'immagine per scaricare il modello per Excel.


 


voronoi-cinquegrani


12 commenti:

  1. M'è venuto alla mente un lavoro che, appena laureato, iniziai a svolgere (ma che, purtroppo, abbandonai subito) per conto dell'Osservatorio Geofisico Sperimentale di Trieste.


    Articolo veramente interessante, Annarita :-)


    Maurizio.

    RispondiElimina
  2. Li ho utilizzati durante il corso di Idrogeologia all'Università, per ricostruire le superfici superiori delle falde a partire dalla posizione e profondità dei pozzi. Ma mai nessuno m'aveva spiegato così bene:

    - che si chiamano così;

    - la loro base teorica.

    Grazie, mitica!

    Pop

    RispondiElimina
  3. Comprendo il "purtroppo" Mauri, è un vero peccato infatti!


    Ti ringrazio dell'apprezzamento.

    Ciao:)

    RispondiElimina
  4. Troppo buono, Pop!;)


    Felice di essere stata utile in qualche modo:)


    Come va alle terme? Ci sentiamo presto!:)

    RispondiElimina
  5. Confesso candidamente che non ero a conoscenza dei diagrammi di Voronoi. Molto interessanti anche per le applicazioni pratiche.


    Visiterò i numerosi link che hai segnalato.

    Un grazie come sempre e un bacione. ruben


    ps: le vacanze stanno per finire, mammaaaaa!

    RispondiElimina
  6. Argomento difficile per me che sono una vera capra in fatto di matematica. Vedrò di capirci qualcosa con l'aiuto di mio figlio.


    Abbraccione

    Mary:)

    RispondiElimina
  7. Cara Annarita, credo di fare cosa buona aggiungere le seguenti annotazioni pertinenti al tuo post. A me sono parse di notevole interesse per tutti coloro che hanno impatto con figure e disegni presentati sul web.


    L'IMMAGINE CALCOLATA. LE CURVE SPLINES (1)


    Da poco, aiutato da mio figlio Gianluca fresco dottorato in ingegneria strutturale, sto cercando di migliorare la realizzazione di immagini partendo da disegni che quasi sempre presentano incertezze e sbavature. È un'esperienza davvero stimolante che, per certi versi trova legami, appunto, con l'argomento delle tassellature di Voroi a commento.


    «Si tratta di una ricerca che, aldilà di ogni possibile valenza artistica, è innanzitutto di metodo e come tema di fondo ha ciò che si potrebbe definire l’uso virtuoso del computer finalizzato all’espressione grafica di concetti o immagini. Virtuoso in che senso? Nel senso che è caratterizzata da un uso minimo di mezzi, e costituisce quindi un’indicazione che può essere utilmente colta dal mondo della scuola.»

    Qui non sono io che scrivo ma è l'introduzione di un interessante articolo a cura di Aldo Spizzichino che ho colto da internet. Vedi qui. Il titolo è L'IMMAGINE CALCOLATA.


    Spizzichino così prosegue.

    «La scelta di lavorare con software auto-costruito crea a mio avviso le premesse per un percorso più stimolante, personale e didatticamente ricco, rispetto a quella di basarsi su un software commerciale, pensato e organizzato per esigenze di produzione. Per chiarire, non mi sto riferendo a un percorso per imparare la matematica, ma per applicare delle nozioni matematiche in un contesto di espressività artistica.».


    Ora non sto qui a riportare per intero l'interessante articolo, perciò rimando al sito indicato sopra per chi sia curioso di saperne.

    Per quanto riguarda il nesso con l'argomento di questo post, l'autore Spizzichino fa queste raccomandazioni.


    «La grafica al computer invita ad affrontare temi classici di morfogenesi e geometria della natura: dalle partizioni regolari e semiregolari del piano e dello spazio, alle strutture labirintiche, arboriformi, spiraliformi, ecc, in un lento progredire verso la complessità che di per sé costituisce una grande avventura intellettuale ed estetica. Ovviamente, prima di affrontare un progetto specifico è bene aver messo a punto strumenti software di uso abbastanza generale (per es. interpolazione con splines, tassellature di Voronoi, linee di livello, frattali lineari, ecc.), in modo che il lavoro di composizione non sia troppo ostacolato da difficoltà tecniche di base...».


    Cari abbracci,

    Gaetano


    (1) Vedi qui.

    RispondiElimina
  8. Ma sì, Mary! Ci capirai qualcosa di sicuro, vedrai!;)

    RispondiElimina
  9. Ruben, sapessi di quante cose non sono a conoscenza io!


    Per quanto riguarda la fine delle vacanze, purtroppo, le cose belle finiscono presto!

    Salutoni:)

    RispondiElimina
  10. Caro Gaetano, le tue aggiunte sono utili di sicuro. Visiterò volentieri i link che hai segnalato.


    Un caro saluto e a presto:)

    RispondiElimina
  11. sono contento che qualcuno abbia letto il mio articolo he ho messo nella mia pagina web

    www.computedart.org

    ho aggiunto altri due  testi che riguardano il mio lavoro.

    il mio indirizzo e-mail è

    aldo@computedart..org

    fra pochi giorni si apre una mia mostra al Festival della Scienza di Genova.

    saluti

    Aldo Spizzichino

    RispondiElimina
  12. Benvenuto, Aldo. Ho visitato il suo sito che trovo molto interessante...però non riesco a risalire all'articolo cui si riferisce e che avrei letto a suo dire. Vorrebbe segnalarlo per cortesia?

    In bocca al lupo per il Festival della Scienza di Genova.

    Cordiali saluti

    RispondiElimina

Related Posts Plugin for WordPress, Blogger...