[Gfoss] poligoni di thiessen (o tassellatura di voronoi)

[giuliano]

Il giorno Sat, 18 May 2013 17:10:20 -0700 (PDT)
stefano campus <stefano.campus a regione.piemonte.it> ha scritto:

> L'altro giorno mi sono divertito a giocare un po' con le varie
> modalità di creazione dei poligoni di thiessen (o tassellazione di
> voronoi) presenti in diversi software.
> ho creato uno shape file di punti e poi applicato la funzione.
> ho provato i seguenti moduli:
> 
> ........
>    
> i risultati sono tutti coerenti tra di loro nella parte centrale
> dell'area di studio. ai confini, ognuno sembra comportarsi in maniera
> differente, con diversi modi di "chiudere" i poligoni relativi ai
> punti più esterni.
> 
> ........

ciao Stefano,

non sono un professore di matematica come piacerebbe a Novarese, però
posso provare a dare un contributo;

la tassellazione di Thiessen (o Voronoi) partiziona il piano in
porzioni più vicine ad uno dei punti di un insieme rispetto a tutti gli 
altri; la situazione diventa evidente nel grafo duale (la
triangolazione di Delaunay) dove si vede chiaramente che ogni lato del
poligono che racchiude un punto biseca la congiungente del punto con un
punto omologo vicino;

i punti periferici hanno punti "concorrenti" alla (s)partizione del
piano solo da una parte, la parte opposta del piano è tutta loro in
quanto non contesa da altri punti; il fatto di terminarla ad un certo
punto credo sia solo una convenzione;

mi scuso: è solo una banalizzazione, non una dimostrazione; se ti
interessa approfondire posso darti qualche riferimento, ad es. la tesi
di Shamos che, fra altre cose, si occupa anche di questo oppure qualche
testo di Computational Geometry (che trovi facilmente in rete); 


ciao,
giuliano