[Gfoss] verifica senso digitalizzazione geometria

Gio 16 Giu 2011 12:54:55 CEST

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 a 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