Computing & ElectronicsEnvironmentalMathematics

(Italiano) I poligoni di Voronoi: il modo di costruzione tradizionale dell’interpolazione “al più vicino” (nearest neighbour)

Pubblicato il

Poiché il campionamento ambientale prende campioni qua e là (analizza valori di contaminazione nel suolo, ad esempio), e poi estende i risultati su tutta l’area di interesse, vale la pena di capire, nel dettaglio, come questo avviene.

E poiché per arrivare al kriging si passa, sempre, nelle varie spiegazioni, per il metodo di interpolazione “al più vicino” (nearest neighbour) eseguita con i Poligoni di Thiessen o di Voronoi, partiremo da questo.

Detto in altre parole, the nearest neighbour è il metodo più semplice per estendere a punti non campionati i valori dei punti campionati (cioè analizzati).

 

Quindi, preso un certo numero di punti casuali su di un piano, come faccio a estendere la loro influenza su l’area di interesse?

L’idea è che tutto quello che è vicino ad un punto abbia il suo stesso valore (analitico).  Ecco come apparirebbe un piano diviso in tal senso secondo Paolo Zatelli (Metodi di interpolazione spaziale, università di trento).

poligoni di voronoi nella dispensa unitn di Zatelli

Ogni punto contenuto nell’area confinata dalla linee nere è più vicino al punto rosso contenuto anch’esso nelle area che ai punti rossi esterni.

Lo si vede tracciando dei cerchi attorno a due punti.

voronoi

Ma se è così, perché l’area segnalata in rosa (violetta) non è attribuita al punto in verde, ma al punto in viola, sebbene sia più vicina al punto in verde?

 

Ripercorriamo il processo di costruzione “tradizionale” dei poligoni di Voronoi.

  • dati due punti, il confine di distanza fra i due è dato da una linea: la linea perpendicolare alla retta che li unisce, e che parte dalla metà di questa distanza
  • se non ci sono altri punti questa linea di confine si estende a tutta l’area
  • se ci sono altri punti, si deve tenere conto anche di questi

 

Ecco il risultato (il fatto che un punto sia evidenziato non vuol dire nulla):

Voronoi solo confini

La costruzione appena citata (1. unisco a due a due i punti con una retta; 2. divido a metà questa distanza; 3. a partire dal punto di mezzo traccio una retta perpendicolare; 4. questa rappresenta i confine di influenza dei vari punti) porta ad alcune simpatiche proprietà.

  • evidenziata la retta -usata nella costruzione dei poligoni –  che unisce due coppie di punti campionaripoligoni di voronoi con evidenziata la retta che unisce 4 punti campionari
  • i punti di incontro delle linee di confine son anche i centri di di cerchi che hanno nel bordo i punti campionari
    i poligoni di Voronoi con evidenziati i cerchi costruiti nei punti di intersezione delle linee di confinealtro esempio dei poligoni di Voronoi con evidenziati i cerchi costruiti nei punti di intersezione delle linee di confine
  • i vertici di questi punti rossi rappresentano i punti di massima distanza dai punti campionari (o se vogliamo, il massimo spazio circolare libero da campioni!).
  • se vogliamo verificare che effettivamente i punti campionari estendano correttamente la propria influenza nel piano, allora potremmo disegnare dei cerchi di pari raggio centrati nei punti campionari stessi (verdi nell’immagine) l'area di influenza dei punti campionari, verificata con cerchi verdi
  • correttamente, l’intersezione di questi cerchi verdi (si veda la parte superiore) coincide con la linea di confine dell’influenza.
  • Andando sulla matematica: questa procedura, in 2 dimensioni, si estende anche alle n-dimensioni.

 

In sintesi, pertanto, alla domanda “perché è rosa e non verde?” possiamo rispondere “perché il disegno è sbagliato e non rappresenta i poligoni di Voronoi” (anche se nel contesto presentato, rende bene l’idea di come appaiono i poligoni di Varonoi, che sono, di fatto, questi poligoni per lo più irregolari, costruiti attorno a dei punti campionari).

Lo vediamo anche dal fatto che le linee di separazione (i lati dei poligoni) non sono disegnati perpendicolarmente alla retta che unisce i due vertici.

Sulla costituzione dei poligoni, passo passo,- con procedura automatizzate – rimandiamo a altre pagine .


Giova concludere presentando un modo per tracciare i poligoni di Voronoi, certo non il più intuitivo, ma sicuramente evocativo.

Come detto un metodo affascinante ma complesso (si tratta dell’applicazione dell’algoritmo di Fortune—un algoritmo di complessità O(n log(n)) per generare il diagramma di Voronoi di un insieme di punti nel piano).

I cerchi da noi disegnati all’inizio, diventano, nel movimento, delle parabole a geometria variabile.


Note a margine,

  • nonostante il nome molto noto di poligoni di Thiessen, il meteorologo americano Alfred H. Thiessen è un utilizzatore, non il primo scopritore, che è Voronoi
  • Voronoi non è indiano (asia) ma europeo (russo nato nell’attuale ucraina)
  • i poligoni di Voronoi sono comunque un modi di interpolazione spaziale piuttosto vecchiotto, sostituito da altri con vantaggi evidenti

 

 

Un pensiero su “(Italiano) I poligoni di Voronoi: il modo di costruzione tradizionale dell’interpolazione “al più vicino” (nearest neighbour)

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *