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