Diagramma di Voronoi

Il principio del diagramma di Voronoi ha stretta correlazione con la Triangolazione di Delaunay. Il centro del cerchio circoscritto dei triangoli di Delaunay sono i vertici del diagramma di Voronoi.

Triangolazione di Delaunay: Trama suddivisa in triangoli.

Diagramma di Voronoi: Trama suddivisa in poligoni.

Nel caso bidimensionale, i vertici di Voronoi sono collegati tramite spigoli, che possono essere derivati dalle relazioni adiacenti dei triangoli di Delaunay:

se due triangoli condividono uno spigolo nella triangolazione di Delaunay, i loro circumcentri devono essere collegati con uno spigolo nella tassellazione di Voronoi.

I diagrammi di Voronoi scompongono lo spazio in celle a seconda di punti centrali specifici. In questo caso, le celle sono progettate geometricamente in modo che la distanza tra tutti i punti all'interno della cella al proprio punto centrale sia più breve rispetto al centro delle celle adiacenti. Il bordo di ciascuna cella è sempre alla stessa distanza dai due punti vicini.

Sia S un insieme di punti nel piano, che chiamiamo sito. Ad ogni sito P è associata una regione di Voronoi R, definita come la parte di piano che è più vicina a P che a qualsiasi altro punto di S. L'insieme dei siti e delle loro regioni costituisce il diagramma di Voronoi.

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 ∈ S in modo tale che tutti i punti all'interno del perimetro di V(p) siano più vicini a p che a ogni altro punto in S.

Alcune proprietà:

Per ogni sito P, la corrispondente regione di Voronoi e' un poligono contenente P al suo interno.

Il lato di confine fra due regioni di Voronoi, associate a due siti P1 e P2, e' un tratto dell'asse del segmento P1-P2 (l'asse e' la retta perpendicolare al segmento nel punto medio di questo).

Le regioni del diagramma di Voronoi ricoprono tutto il piano senza intersecarsi fra loro e senza lasciare "buchi". Ogni volta che tre linee si incontrano, otteniamo un nuovo vertice, lontano secondo distanze identiche ai punti più vicini.

L’algoritmo di Lloyd, noto anche come iterazione di Voronoi, è un algoritmo che trova insiemi di punti equidistanti in sottoinsiemi di spazi euclidei e partizioni di questi sottoinsiemi in celle. Questo algoritmo trova ripetutamente il baricentro di ciascun insieme nella partizione e quindi ripartiziona l'insieme dei punti in base a quale di questi baricentri è più vicino. L'algoritmo può essere applicato nello smussamento delle mesh triangolari. Descrizione L'algoritmo di Lloyd inizia con un posizionamento iniziale di un certo numero k di siti nel dominio di input. Quindi viene eseguita ripetutamente la seguente fase di rilassamento: Viene calcolato il diagramma di Voronoi dei k siti. Ogni cella del diagramma di Voronoi è integrata e viene calcolato il baricentro. Ogni sito viene quindi spostato al baricentro della sua cella di Voronoi. Poiché gli algoritmi per la costruzione dei diagrammi di Voronoi possono essere altamente complessi, i passaggi per calcolarli e trovare i baricentri esatti delle celle possono essere sostituiti da un'approssimazione.