Ciao a tutti,
ciao Giuliano e grazie per esserti preso la briga di verificare gli
algoritmi!
Il giorno gio, 16/06/2011 alle 09.48 +0200, giuliano ha scritto:
On Wed, 15 Jun 2011 15:46:29 +0200
0) mi sembra che il tuo algoritmo si basi sul fatto che per passare con
un orientamento ORARIO dall'ordinata max a quella min occorre passare
prima per l'ascissa max (o per passare dall'ascissa max a quella min
occorre prima passare dall'ordinata min): questo e' il senso
dell'ordine crescente richiesto per i dati secondo i tre indici 0,1,2 o
1,2,3;
Esattamente
1) mi sembra che l'algoritmo quindi funzioni solo per poligoni non
intrecciati (non ho un background geografico - cartografico, per cui ne
parlo in termini puramente geometrici);
Esatto; un poligono come quello da te descritto è topologicamente
sbagliato (presenta una autointersezione). Quindi prima di applicare
l'algoritmo, la geometria va controllata. Del resto, un poligono a forma
di 8 in che senso gira? Un anello in orario, e l'altro in antiorario, ma
per il poligono in se il senso di rotazione non ha valore.
A meno che non si desideri conoscere il senso di rotazione in
corrispondenza di un punto esterno al perimetro, ossia il verso del
vettore tangente al poligono nella proiezione del punto sul perimetro.
Questo potrebbe avere senso, ed è anche semplice da implementare (a
occhio).
2) non e' robusto: mi sembra che nel caso di un poligono antiorario
(1,1), (3,2), (4,4), (2,3), (1,1) o orario (1,1), (2,3), (4,4), (3,2),
(1,1) non sia in grado di determinarne il senso;
Hai ragione, hai trovato il caso limite, ovvero quello in due soli punti
soddisfano le 4 condizioni, ovvero quando due punti coincidono con 2
vertici opposti dell'MBR. Ho verificato il mio codice originale e manca
il controllo, che potrebbe essere implementato così (ora non ho molto
tempo per ragionarci bene):
Se al termine del ciclo sui vertici, la matrice bound contiene solo 2
indici che si ripetono, quindi nel tuo esempio
p[bound[0]] = 3 (4,4) ordinata max
p[bound[1]] = 3 (4, 4) ascissa max
p[bound[2]] = 1 (1, 1) ordinata minima
p[bound[3]] = 1 (1, 1) ascissa minima
dovrebbe essere sufficiente cercare un altro vertice per una qualunque
delle condizioni, escludendo dal suo proprio criterio i punti i cui
indici siano già contenuti nella matrice, ovvero:
p[bound[0]] = punto a ordinata massima che non sia 3 o 1 = 4 (2, 3)
Il che risulta in un ordine antiorario (4 3 3 1)
Se scelgo una delle altre condizioni:
p[bound[1]] = 2 (3 2 1 1) ascissa max <> 3 OK
p[bound[2]] = 2 (3 3 2 1) ordinata minima <> 1 OK
p[bound[3]] = 4 (3 3 1 4) ascissa minima <> 1 ?!?!?!
La quarta condizione è problematica: non so se basti "ruotare la
sequenza", ovvero se 3314 = 4331, oppure se la scelta di quale punto
cercare non possa essere casuale ma dipenda da determinate condizioni.
Ci penserò! Dammi una mano se vuoi/puoi.
3) curiosita': quale la fonte di questo algoritmo?
L'ho scritto io, in MapBasic, nel 2006.
4) il metodo dell'area proposto da Giovanni e' basato
sulla somma algebrica delle aree sottese ad ogni lato (cosi' mi sembra
di ricordare nelle versioni che ho visto pubblicate: Newmann/Sproull?
Foley/VanDam? Knuth? se e' importante cerco di trovarlo) quindi dovrebbe
dare comunque il valore dell'area; il segno sara' positivo o negativo a
seconda del senso di percorrenza (dovrebbe funzionare anche
per poligoni intrecciati);
5) un concetto analogo e' quello del momento statico di una forza
(un lato) rispetto ad un punto che puo' destrogiro o sinistrogiro, ma
occorre verificare e inoltre il calcolo probabilmente e' molto vicino a
quello fatto con il metodo dell'area;
Grazie per la spiegazione! Qui fatico un po', purtroppo il mio
background accademico da agronomo non mi aiuta molto.
Vorrei implementarlo in python sulla falsariga dell'implementazione
proposta da Giovanni, ovviamente appena riesco a prendermi il tempo per
imparare python. Nel frattempo, se a qualcuno interessa posso postare il
codice MapBasic.
Ciao e grazie ancora
Sig
ciao,
giuliano
_______________________________________________
Iscriviti all'associazione GFOSS.it: http://www.gfoss.it/drupal/iscrizione
Gfoss@lists.gfoss.it
http://lists.gfoss.it/cgi-bin/mailman/listinfo/gfoss
Questa e' una lista di discussione pubblica aperta a tutti.
Non inviate messaggi commerciali.
I messaggi di questa lista non rispecchiano necessariamente
le posizioni dell'Associazione GFOSS.it.
518 iscritti al 3.6.2011