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

skampus · May 19, 2013, 12:10am

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:

QGIS dev (280):
1) sextante:
   - qgis_voronoi (FTools)
   - v.voronoi (grass)
   - saga_thiessen (saga)
2) Ftools:
   - voronoi polygons (0% buffer)
   - voronoi polygons (10% buffer)
3) MMQGIS
   - voronoi diagram

gvSIG 1.10:
- thiessen incremental TIN
- thiessen Chew's model

AdB Toolbox (Openjump)

ArcView 3.3
- Edit Tool extension

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.

il modulo qgis di sextante ad esempio individua i punti più esterni come
limite dell'analisi e i lati del perimetro passano per tali punti. questo
risultato è esattamente quello ottenuto col medesimo modulo Ftools che si
trova sotto il menu vector e utilizzando come buffer 0%. se con questo
modulo si imposta un buffer di 10%, il comportamento ai confini cambia.

il modulo v.voronoi di grass in sextante si comporta bene al centro, ma
anche in questo caso la chiusura del poligono ai bordi è differente.

il comportamento di saga ai bordi non riesco proprio a capirlo (io sarei
dell'idea di toglierlo da sextante), così come quello dell'estensione edit
tool di arcview 3.1 che ho tirato fuori per l'occasione
adbtoolbox (personalizzazione di openjump a cura del ministero dell'ambiente
e gvsig, invece, esagerano proprio nell'estensione del poligono.

mmqgis credo che sia il miglior prodotto: al centro la soluzione è uguale a
quella degli altri moduli, ma al contorno considera i punti più esterni e il
lato del poligono dista in questo caso un paio di chilometri, sufficienti
per la caratterizzazione.

per chi ha voglia di guardare i risultati, allego gli shp file e un progetto
qgis 1.9

Thiessen.rar
<http://gfoss-geographic-free-and-open-source-software-italian-mailing.3056002.n2.nabble.com/file/n7582299/Thiessen.rar>

--
View this message in context: http://gfoss-geographic-free-and-open-source-software-italian-mailing.3056002.n2.nabble.com/poligoni-di-thiessen-o-tassellatura-di-voronoi-tp7582299.html
Sent from the Gfoss -- Geographic Free and Open Source Software - Italian mailing list mailing list archive at Nabble.com.

Paolo_Cavallini · May 19, 2013, 9:51am

On 2013-05-19 02:10, stefano campus wrote:

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:

Molto interessante, grazie. Alcune considerazioni:
* potresti creare e condividere un modellino di sextante per realizzare tutte le analisi possibili al suo interno, fare la differenza e misurare i risultati?
* puoi creare un test per alcuni dei moduli? E' facile, senti Victor per dettagli
* lo stesso approccio sarebbe interessante per altre analisi, sia raster che vettoriali; sono sicuro che salteranno fuori cose interessanti, per qualcuno anche inquietanti
* manca evidentemente una opzione nel modulo di sextante per fTools: puoi aprire un ticket? Aggiungerlo e' banale
* il comportamento ai bordi e' opinabile, ma comprensibile; per me l'approccio giusto e' quello di fTools, ovvero di GEOS
* il comportamento di saga sembra francamente sbagliato: io aprirei un ticket li'
* quello di grass credo dipenda da come viene generata la region: due punti sono esclusi, da li' il risultato errato (ticket su sextante).
Saluti, e grazie ancora.
--
Paolo Cavallini - Faunalia
www.faunalia.eu
Full contact details at www.faunalia.eu/pc
Nuovi corsi QGIS e PostGIS: http://www.faunalia.it/calendario

Antonio_Vinci · May 19, 2013, 5:51pm

stefano campus wrote/

la regione di calcolo deve essere un pelo più estesa sì da comprendere
tutti i punti

/

Beh, proprio a quello serve il buffer di Ftools...
Peraltro non avrebbe fisicamente senso escludere i punti esterni, perche'
anche loro hanno influenza "centrifuga" esattamente come gli altri.
Sarebbe interessante mostrare il tuo confronto ad un professore di
matematica, in modo da avere un giudizio oggettivo sui quei risultati.

-----

--
View this message in context: http://gfoss-geographic-free-and-open-source-software-italian-mailing.3056002.n2.nabble.com/poligoni-di-thiessen-o-tassellatura-di-voronoi-tp7582299p7582312.html
Sent from the Gfoss -- Geographic Free and Open Source Software - Italian mailing list mailing list archive at Nabble.com.

Stefano_Campus · May 20, 2013, 6:16am

hahahahah, avrei fatto meglio a stare zitto!!!
guarda quanto lavoro nuovo.
scherzo...

per i primi due punti sarà per me l'occasione di cominciare a giocare con i
modelli di sextante con cui non ho ancora avuto occasione di giocare.
come pensi che possa misurare i risultati, facendo le differenze o union?

le altre cose le faccio immediatamente!

per saga esiste già un ticket aperto da un sacco di tempo nella lista
propria di saga. ecco perchè dicevo di eliminarlo finchè non viene
aggiustato nel core di saga.

perchè invece dici che il comportamento più coerente ai bordi è quello di
ftools? se hai visto, cambiando il buffer cambia completamente il risultato
al contorno.

_____________________________________________________
In reply to this post by Paolo Cavallini

    Paolo Cavallini wrote
    * quello di grass credo dipenda da come viene generata la region: due
    punti sono esclusi, da li' il risultato errato (ticket su sextante).

sì infatti dipende dalla regione. se come estensione dell'analisi dò quella
del layer di thiessen ottenuto con mmqgis, il risultato è identico.
sembrerebbe quidi che i punti (più) esterni siano esclusi. bisogna aprire un
ticket su sextante e dire che come minimo la regione di calcolo deve essere
un pelo più estesa sì da comprendere tutti i punti?

______________________________________
    Novarese wrote
    Beh, proprio a quello serve il buffer di Ftools...
    Peraltro non avrebbe fisicamente senso escludere i punti esterni,
perche' anche loro hanno influenza "centrifuga" esattamente come gli altri.

però mi sembra strano dover esplicitamente dichiarare di considerare anche i
punti estremi.
in questo modo la funzione utilizza sempre m-n punti, a partire dal dataset
formato da m punti.

infatti mmqgis il "bufferino" di fatto lo aggiunge di default

--
View this message in context: http://gfoss-geographic-free-and-open-source-software-italian-mailing.3056002.n2.nabble.com/poligoni-di-thiessen-o-tassellatura-di-voronoi-tp7582299p7582314.html
Sent from the Gfoss -- Geographic Free and Open Source Software - Italian mailing list mailing list archive at Nabble.com.

giuliano · May 21, 2013, 9:55pm

Il giorno Sat, 18 May 2013 17:10:20 -0700 (PDT)
stefano campus <stefano.campus@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

Antonio_Vinci · May 21, 2013, 10:24pm

giuliano su Tiscali wrote/

ogni lato del poligono che racchiude un punto biseca la congiungente del
punto con un punto omologo vicino

/

Mi permetto di tradurre in linguaggio umano: il lato di un poligono e'
l'asse di due punti adiacenti.

giuliano su Tiscali wrote/

il fatto di terminarla ad un

*

certo

*

punto credo sia solo una convenzione

/

Bravo, e' proprio questo il nocciolo della questione: a quale "certo" punto
e' giusto confinarla esternamente?

In altre parole: qual e' il buffer ottimale nell'accezione Ftools?

-----

--
View this message in context: http://gfoss-geographic-free-and-open-source-software-italian-mailing.3056002.n2.nabble.com/poligoni-di-thiessen-o-tassellatura-di-voronoi-tp7582299p7582348.html
Sent from the Gfoss -- Geographic Free and Open Source Software - Italian mailing list mailing list archive at Nabble.com.

Stefano_Campus · May 21, 2013, 11:13pm

giuliano, grazie mille per il contributo.
dunque quanto detto da me prima è sbagliato, relativamente al fatto che
avevo l'impressione che i punti più esterni fossero presi in considerazione
solo nella definizione dei lati più esterni.
non avevo dubbi sul fatto che all'interno tutti i moduli si comportassero
nella medesima maniera, ma la chiusura dei poligoni esterni non mi è tuttora
chiara.
in particolare due sono i casi che mi perplimono: il primo è saga, ma credo
di avere capito che ha un baco e quindi auspicavo che venisse eliminato da
sextante in attesa che sia "schiacciato". il secondo è proprio ftools che
cambia di molto la forma dei poligoni (più) esterni in funzione del buffer
scelto.

però potrei usare la tassellatura ad esempio per decidere dove installare un
nuovo punto di misura cercando di mantenere le aree più o meno simili. in
questo caso, mi serve sapere come si comporta il modello nella "zona
esterna" che, aggiungendo un nuovo punto, cambia.
sbaglio?

per curiosità un'occhiata alla tesi che citi la darei volentieri, grazie
mille

s.

--
View this message in context: http://gfoss-geographic-free-and-open-source-software-italian-mailing.3056002.n2.nabble.com/poligoni-di-thiessen-o-tassellatura-di-voronoi-tp7582299p7582349.html
Sent from the Gfoss -- Geographic Free and Open Source Software - Italian mailing list mailing list archive at Nabble.com.

giuliano · May 22, 2013, 7:52am

Il giorno Tue, 21 May 2013 16:13:38 -0700 (PDT)
stefano campus <skampus@gmail.com> ha scritto:

giuliano, grazie mille per il contributo.

ciao Stefano;

dunque quanto detto da me prima è sbagliato, relativamente al fatto
che avevo l'impressione che i punti più esterni fossero presi in
considerazione solo nella definizione dei lati più esterni.

per quello che ho capito io (e quindi con tutti i benefici del
caso :-)))) ogni punto concorre con ogni altro alla divisione del
piano; nel caso di 2 soli punti le porzioni sono i due semipiani
individuati dall'asse rispetto ai due punti(come opportunamente
mi corregge Novarese); nota che i semipiani sono spazi infiniti;

nel caso di più punti, a ciascuno alla fine resta l'intersezione di
tutti i semipiani individuati sopra; normalmente ai punti interni
competeranno delle porzioni poligonali finite, ma ai punti perimetrali,
non avendo competitori all'esterno, rimane un sottospazio infinito;
dovendo passare dall'infinito al finito una operazione di clipping è
necessaria; dove questa sia compiuta è, credo, arbitrario;

@Novarese: era questo che volevo dire; ovviamente che sia corretto
è tutto da dimostrare mi sembra invece assodato che
non ti abbia soddisfatto, ma fa parte del gioco, come dice Nathan nel
primo post indicato da Paolo:-))))

non avevo dubbi sul fatto che all'interno tutti i moduli si
comportassero nella medesima maniera, ma la chiusura dei poligoni
esterni non mi è tuttora chiara.
.....
però potrei usare la tassellatura ad esempio per decidere dove
installare un nuovo punto di misura cercando di mantenere le aree più
o meno simili. in questo caso, mi serve sapere come si comporta il
modello nella "zona esterna" che, aggiungendo un nuovo punto, cambia.
sbaglio?

quì non riesco ad aiutarti; forse bisogna guardare nella documentazione
dei vari software, però, sempre SE ho capito bene io, la questione è
ininfluente; provo a fare un esempio, sperando di non cascare, come
fanno spesso i profani, dalla padella alla..... ammettiamo che
i tuoi punti rappresentino delle scuole in un territorio, tu sai che la
scuola a te più vicina è quella "proprietaria" del poligono dove
sei collocato; quando sei alla periferia, intendo al di là di tutti
i punti, quello che determina la scuola vicina non è tanto l'essere
nel poligono indicato da Grass o da fTools o Saga, ecc. bensì nel
semispazio infinito che contiene la scuola; i poligoni indicati dai
vari sw credo siano semplici identificatori "finiti" di spazi
"infiniti";

per curiosità un'occhiata alla tesi che citi la darei volentieri,
grazie mille

dovrebbe essere questo link "Computational Geometry" alla pagina
http://euro.ecom.cmu.edu/shamos.html;

s.

chiedo scusa della prolissità (delle cavolate è sottinteso:-))), ciao,
giuliano

Antonio_Vinci · May 22, 2013, 10:57am

Ottima l'idea della scuola, ti seguo.

Essendo necessario definire un perimetro esterno, il problema è di "quanto"
offsettarlo rispetto all'inviluppo definito dalle scuole più esterne...

Invece di mettere un buffer a casaccio, ho pensato di legarlo in qualche
modo alla geometria esistente.

Creata la triangolazione di Delaunay, ho fatto la media M delle distanze
reciproche fra punti adiacenti, ho piazzato cerchi di diametro M in
corrispondenza dei punti più esterni, infine ho disegnato il poligono
circoscritto a tali cerchi.

<http://gfoss-geographic-free-and-open-source-software-italian-mailing.3056002.n2.nabble.com/file/n7582357/buffer_non_casuale.gif>

Non so se sia logicamente sensato (l'ultima volta che ho aperto un libro di
matematica, i Vopos ancora sparavano ai fuggitivi attraverso il Muro di
Berlino...) ma almeno è un buffer "proporzionato" alla densità dei punti del
rilievo.

Per gli appassionati, allego il file .QGS con le shape usate:
http://novarese.t15.org/gfoss/thiessen.zip
<http://novarese.t15.org/gfoss/thiessen.zip>

-----

--
View this message in context: http://gfoss-geographic-free-and-open-source-software-italian-mailing.3056002.n2.nabble.com/poligoni-di-thiessen-o-tassellatura-di-voronoi-tp7582299p7582357.html
Sent from the Gfoss -- Geographic Free and Open Source Software - Italian mailing list mailing list archive at Nabble.com.