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:

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 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.

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.

Un diagramma di Voronoi da Wikipedia.

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.