poligoni di thiessen (o tassellatura di voronoi)

[stefano campus]

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
 

[pcav]

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
_______________________________________________
[hidden email]
http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
Questa e' una lista di discussione pubblica aperta a tutti.
I messaggi di questa lista non hanno relazione diretta con le posizioni dell'Associazione GFOSS.it.
638 iscritti al 28.2.2013

[stefano campus]

CONTENTS DELETED

The author has deleted this message.

[Novarese]

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.

[stefano campus]

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

[giuliano su Tiscali]

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

_______________________________________________
[hidden email]
http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
Questa e' una lista di discussione pubblica aperta a tutti.
I messaggi di questa lista non hanno relazione diretta con le posizioni dell'Associazione GFOSS.it.
638 iscritti al 28.2.2013

[Novarese]

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?

[stefano campus]

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.

[giuliano su Tiscali]

Il giorno Tue, 21 May 2013 16:13:38 -0700 (PDT)
stefano campus <[hidden email]> 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

_______________________________________________
[hidden email]
http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
Questa e' una lista di discussione pubblica aperta a tutti.
I messaggi di questa lista non hanno relazione diretta con le posizioni dell'Associazione GFOSS.it.
638 iscritti al 28.2.2013

[Novarese]

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.



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