-
francesco.coppola
.User deleted
So di fare contento Afazio dicendogli che a furia di leggere di poligoni, di semine di punti, di destra e sinistra, ecc.; di problemi topologici insomma - qualche lampadina mi si è accesa - e sono tornato ad un mio vecchio problema mai soddisfacentemente risolto.
Dato un generico poligono chiuso, di n vertici ed n lati, trovare i vertici del poligono da esso distanziato 'dist' interno o esterno.
Nulla di più di quanto da sempre non faccia il comando 'OFFSET' di Autocad, quindi.
Per capirci, un disegnino per visualizzare bene.
Ho segnato in tratteggio i poligoni esterno ed interno, rispetto al poligono originario.
Una decina di anni fa avevo affrontato il problema e lo avevo risolto con un approccio che non mi aveva mai convinto del tutto (anche per i risultati bizzarri che in qualche raro caso esso forniva).
In pratica, non sapendo a priori verso quale 'parte' del poligono dovesse trovarsi il lato del poligono offsettato, provavo con tutte le direzioni, ottenendo questo (un ingrandimento in corrispondenza del vertice 2):
Come vedete, per ricavare il vertice 2' del nuovo poligono, basterebbe tracciare le parallele dei lati 1-2 e 2-3 e cercare di 'selezionare' il punto giusto tra le 4 intersezioni effettive.
Nel caso si volesse il poligono interno, vi è ancora modo di procedere poichè uno solamente dei 4 è realmente interno al poligono. La cosa diventa invece più complessa se si volesse il poligono esterno, poichè gli altri 3 vertici sono sempre esterni al poligono stesso, per cui decidere quale sia quello giusto.....
Altro caso in cui tale criterio va totalmente in tilt è quando i vertici 1-2-3 sono allineati. Le 4 rette sono tutte parallele tra loro e le loro 4 intersezioni sono tutte all'infinito.
Lo so, visivamente è una bazzecola. Ma qui si tratta di 'studiare' un meccanismo algoritmico che consenta di trovare il nuovo vertice senza 'guardare le figure'.
. -
.
Ma il vertice 2' del poligono offsettato puo trovarsi solo sulla bisettrice dell'angolo (esterno o interno poco importa) formato dalle semirette su cui giacciono i due lati convergenti al vertice 2. 
L'altra bisettrice, quella in cui hai ubicato gli altri due punti, non esiste. Esisterebbe solo se considerassimo anziche le semirette di cui sopra, le rette su cui giacciono i due segmenti-lato. -
francesco.coppola .
User deleted
.... assolutamente Afazio, assolutamente.....
Tanto è vero che adesso ho deciso di cambiare approccio e sfruttare proprio la bisettrice per trovare il punto giusto, come vedrai in seguito.
Faccio però un piccolo passo indietro.
Quando nel passato avevo affrontato la questione mi ero trovato in 'imbarazzo' nel determinare correttamente l'equazione della bisettrice. Ovvero ad operare con le regole della geometria analitica si fa un mare di casino, e soprattutto non riuscivo a decidere quale fosse il verso della bisettrice.
Se invece di operare con i segmenti, si operasse con le equazioni delle rette (così facevo) due rette che si intersecano generano 4 angoli a due a due uguali e contrapposti. Quale porzione di piano considerare?
Ora tu, correttamente hai tracciato in giallo la bisettrice 'giusta' (e avendo il poligono disegnato non è possibile sbagliare). Ma esisterebbe anche la bisettrice ortogonale a quella che hai tracciato e che, sempre algoritmicamente, si dovrebbe essere in grado di escludere.
Ecco, questa decisione (è la bisettrice corretta o no?) mi era rimasta 'indigesta'.
Ricordi però di un passato lontano.
P.S. Adesso parlerò di azimuth e cose così. Se anche tu stai pensando la stessa cosa, non togliermi il gusto di essere io a parlarne.. -
.P.S. Adesso parlerò di azimuth e cose così. Se anche tu stai pensando la stessa cosa, non togliermi il gusto di essere io a parlarne.
Già. Sinceramente stavo pensando alla stessa cosa (anche se io non li chiamo azimuth) poiche stavo trattando la stessa cosa per la ricerca de convexHull.
A proposito, potrebbe esserti utile una funzione che calcola l'azimangolo o l'angoluth ? Una specie di rivisitazione della funzione AtnCODICEFunction arcotangente(X_i As Double, Y_i As Double, X_f As Double, Y_f As Double) As Double
Dim pi As Double
pi = 4 * Atn(1)
If X_i = X_f Then
arcotangente = Sgn(Y_f - Y_i) * pi / 2
Else
arcotangente = Atn((Y_f - Y_i) / (X_f - X_i))
If (X_f - X_i) < 0 Then arcotangente = arcotangente + pi
End If
End Function
P.S.:16.09.2012. QUesta funzione ha subito delle modifiche. vedere nel sgeuito
Edited by afazio - 16/9/2012, 08:57. -
francesco.coppola .
User deleted
Afazio, la tua funzione è 'limitata' qui: CODICEIf X_i = X_f Then
arcotangente = Sgn(Y_f - Y_i) * pi / 2
Perchè io ho bisogno di angoli non negativi e che vadano da 0 a 2*pi.
Adesso spiego meglio come intendo procedere.
Per avere sempre perfetta 'padronanza' della questione bisognerà procedere orientando ed ordinando i singoli segmenti.
Ovvero, sempre guardando il vertice 2, orienterò i due segmenti che convergono su di esso in modo che siano sempre 'uscenti' dal vertice stesso. Poi ho bisogno di sapere a priori se il poligono è 'ordinato' in senso orario o antioriario (ovvero seguendo la sequenza dei vertici 1-2-3-4 procedo in senso orario o no).
Con queste due piccole precisazioni ed il seguente schema:
in cui ho provveduto segnare l'orientamento dei segmenti (le frecce bianche), potrò calcolare gli azimuth 'topografici' dei due segmenti convergenti in 2.
E cosa non di secondo piano avere subito l'azimuth della bisettrice (anche essa, non secondaria come cosa, orientata).
Infatti:
alfa-b=[(alfa-2_1)+(alfa-2_3)]/2
Vedrò di specificare meglio in un prossimo messaggio perchè è necessario conoscere la orarietà o antiorarietà del poligono originario, perchè adesso non sembra evidente.
(Ed anche perchè devo riflettere meglio, poichè mi pare al momento non debba poi essere così importante. Vedremo...). -
francesco.coppola .
User deleted
Come ulteriore riprova, ho replicato lo schema fatto sul vertice 2, anche sul vertice 4, che essendo convesso poteva far sballare il ragionamento: 
con tutte le precisazioni di prima, orientamento dei segmenti, ordinamento del poligono, ecc. ad occhio mi pare funzioni.
Sono sempre in grado di calcolare l'angolo interno al poligono (azimuth del primo segmento meno il secondo), ed orientare quindi correttamente la bisettrice.. -
.Afazio, la tua funzione è 'limitata' qui:CODICEIf X_i = X_f Then
arcotangente = Sgn(Y_f - Y_i) * pi / 2
Perchè io ho bisogno di angoli non negativi e che vadano da 0 a 2*pi.
E perchè mai?
Non puoi ragionare mantenendo il verso di definizione del lato i-esimo del poligono cosi come definito nella lista dei suoi vertici?
Ops, ma tu hai scritto un romanzo appresso. Dammi il tempo di leggere il resto, nel frattempo non tenere conto della presente risposta.. -
.
infatti:
considera la figura che segue
l'angolo formato dalla bisettrice e l'asse delle x (con il quale poi ti calcoli il coefficiente angolare della stessa), è sempre pari al valore medio dei due angoli Alfa21 (notare che è diverso dall'angolo alfa12) e l'angolo alfa23
L'angolo alfa21 è legato all'angolo alfa12 dall'operazione di cambiamento dell'orientamento del segmento, che in ultima analisi significa semplicemente sottrarre 180° (o se si preferisce sommare è indifferente) dall'angolo originario.
Quindi avremo sempre:
alfa= (alfa12 - 180 + alfa23 )/2
questo vale sempre, sia per poligoni orari che per poligoni antiorari.
La funzione che ho scritto sopra serve a determinarsi l'angolo formato tra il segmento orientato e l'asse delle x. Se l'angolo è negativo poco importa, sarà la sequenza delle coordinate dei vertici a stabilire i coefficienti angolari di tutte le bisettrice e con il loro giusto segno.
Ricordare infine che la tangente ha periodo pari a 180, cio significa che la tangente dell'angolo -122 è uguale alla tangente dell'angolo -122+180 = 58
Edited by afazio - 13/9/2012, 18:32. -
francesco.coppola .
User deleted
Prima porzione di codice per il calcolo dell'azimuth di un segmento. (Mattone che ovviamente serve per il resto).
In input 4 parametri: x1,y1 coordinate del primo punto; x2,y2 coordinate del secondo. Orientamento del segmento: da 1 a 2.CODICEfloat azimuth_segmento (float x1,float y1,float x2,float y2)
{
float azmth;
float deltax,deltay;
deltax=x2-x1;
deltay=y2-y1;
if (deltay!=0.0) azmth=atan(fabs(deltax)/fabs(deltay));
else
{
if (deltax>0.0) azmth=1.570796; else azmth=4.712389;
}
if (deltay<0.0 && deltax>=0.0) azmth=3.141593-azmth; /* Segmento nel II quadrante */
if (deltay<0.0 && deltax<=0.0) azmth=3.141593+azmth; /* segmento nel III quadrante */
if (deltay>0.0 && deltax<0.0) azmth=6.283185-azmth; /* Segmento nel IV quadrante */
return(azmth);
}
Come vedete sono stato molto 'pedissequo'.
D'altra parte sono andato a riprendere un vecchio libro di topografia che parlava ancora di tavole logaritmiche per ricavare il valore dell'arcotangente del rapporto dei valori assoluti di deltax e deltay (il fabs() dentro cui sono contenuti nella funzione atan()), e dal segno dei quali poi ricavare il quadrante in cui si trova effettivamente il segmento orientato, con il relativo aggiustamento angolare.
Edited by francesco.coppola - 14/9/2012, 12:01. -
francesco.coppola .
User deleted
Aggiungo un altro piccolo tassello al problema.
Una volta trovato l'azimuth della bisettrice, non mi serve più ricavare l'equazione analitica di questa retta, perchè il vertice del poligono offsettato è possibile ricavarlo semplicemente con semplice notazione 'polare'.
Il tutto con un ulteriore piccolo tassello, da cui si capirà la necessità dell'ordinamento del poligono.
Ulteriore piccola notazione a chi ci legge.
Io determino l'azimuth seguendo regole 'topografiche' da istituto tecnico per geometri. Afazio invece ricava angoli da trigonometria da 'Liceo Scientifico'.
Ovviamente sono l'uno angolo complementare dell'altro. I concetti rimangono identicamente identici.. -
.Aggiungo un altro piccolo tassello al problema.
Una volta trovato l'azimuth della bisettrice, non mi serve più ricavare l'equazione analitica di questa retta, perchè il vertice del poligono offsettato è possibile ricavarlo semplicemente con semplice notazione 'polare'.
Il tutto con un ulteriore piccolo tassello, da cui si capirà la necessità dell'ordinamento del poligono.
Ulteriore piccola notazione a chi ci legge.
Io determino l'azimuth seguendo regole 'topografiche' da istituto tecnico per geometri. Afazio invece ricava angoli da trigonometria da 'Liceo Scientifico'.
Ovviamente sono l'uno angolo complementare dell'altro. I concetti rimangono identicamente identici.
Confermo. Ho studiato al liceo scientifico.
Colgo l'occasione riprendendo il termine "trigonometria" per raccontare che al quarto liceo, questa branca della geometria mi affascinò cosi tanto da spingermi a studiare da solo la materia lasciando perdere il programma che intanto sviluppava la prof.
A gennaio io sapevo risolvere i triangoli e le equazioni/disequazioni trigonometriche, mentre i miei compagni si attorcigliavano ancora con gli angoli complementari, supplementari, con le formule di duplicazione dei seni e dei coseni.
. -
francesco.coppola .
User deleted
Anch'io provengo dal Liceo Scientifico.
Ma quando ho iniziato a studiare all'università ho avuto modo di vedere che chi proveniva dal Geometra ragionava 'al contrario'.
Quando poi ho studiato topografia, in effetti ho visto che tutti i ragionamenti e gli schemi venivano svolti in senso orario, invece che antiorario, e partendo dall'asse Y (meglio dire Nord) piuttosto che dall'asse X.
Tutti i teodoliti poi da sempre presentano il cerchio segmentato in senso orario.
Chissà perchè in ambito matematico/tecnico si sia prodotta questa 'dicotomia', e non ci sia mai stato nessuno che abbia pensato bene di uniformare le 'forme' ('chè poi solamente di questo si tratta).
Ovviamente io ho sempre ritenuto l'una e l'altra convenzione degne della stessa considerazione. Non i miei amici ex-geometri che da sempre hanno ritenuto 'giusta' solamente la loro.
Una volta avuto l'azimuth della bisettrice, orientato, il problema si semplifica di botto.
Ragionando infatti in termini di coordinate polari, il vertice del poligono offsettato 'coninugato' del poligono originario, verrebbe ricavato partendo dalle coordinate iniziali come:
x'i=xi+d'*sen(alfa_b)
y'i=yì+d'*cos(alf_b)
Unica cosa da definire ancora è il valore di d', che ovviamente deriverà dalla distanza d che si vuole avere tra il poligono originario e il poligono offsettato.
Domani preparerò una ulteriore figura in cui si vedrà che anche questo 'dettaglio' è una pura fesseria. (Ma da cui emergerà l'importanza dell'orientamento orario o anti-orario del poligono di origine).
Infine, ultima chicca, basterà calcolare il valore di d' ed inserirlo nelle formule di cui sopra in valore positivo o negativo per ottenere rispettivamente il poligono offsettato interno o esterno.. -
francesco.coppola .
User deleted
Come promesso schema grafico da cui ricavare la grandezza d': 
Nulla di che, semplice trigonometria. Detto alfa_2-3-b l'angolo formato dalla bisettrice con il secondo lato indagato, il valore di d' è:
d'=d/sen(alfa_2-3-b)
Cosa importante per la struttura stessa della formula è che mai e poi mai, se d è positivo (e mi pare che trattandosi di una distanza....) d' sarà sempre e per forza positivo.
Infatti essendo alfa_2-3-b l'angolo 'metà' dell'angolo possibile formato tra due lati consecutivi del poligono, esso potrà variare da un minimo di 0° ad un massimo di 180° (valori estremi questi che fanno 'fallire' la formulina di cui sopra, ma che spunterebbero fuori per poligoni 'degeneri' che andrebbero prima ben sistemati). Ed sappiamo con questo range di angoli che il relativo seno è sempre positivo.
Come detto nel post precedente, se si volesse il poligono in offset esterno, invece che l'interno, basta mettere il segno meno (-) davanti a d' e continuare tranquillamente ad utilizzare le formuline polari precedenti.
Ora torno indietro sui miei passi. Avevo sempre affermato che il poligono avrebbe dovuto essere orario, avevo avuto qualche dubbio, mi ero ricreduto, adesso mi pare che in effetti questa mia pre-condizione iniziale non sia affatto necessaria.
Gli azimuth li ho calcolati semplicemente orientando i singoli segmenti (facendoli sempre partire dal vertice indagato), l'azimuth della bisettrice la trovo con semplice media tra i due azimuth, senza bisogno di correzione alcuna.
L'unico dubbio lo avevo sul possibile segno di quest'ultimo angolo tra bisettrice ed un lato. Ma basta prendere in valore assoluto la differenza: (alfa_b)-(alfa_2-3) perchè la 'costrizione' sul senso orario o anti-orario del poligono si sciolga come neve al sole.
O mi sbaglio?
Edited by francesco.coppola - 14/9/2012, 12:13. -
francesco.coppola+1 .
User deleted
Facciamo adesso diventare codice tutta la discussione geometrica.
La routine opererà su 'variabili globali', ovvero, sia i vertici del poligono origine, sia i vertici del poligono offsettato saranno variabili esterne alla funzione.
Per mia particolare affezione utilizzo il costrutto struct tipico del C. Da quanto letto nel codice di Afazio vedo che è possibile anche in VBA dichiarare una variabile con typedef 'collezione' di variabili singole. E' quanto in effetti fa lo struct del c, assembla variabili semplici, per crearne una più 'complessa'.
Per prima cosa devo specificare di che 'mattoni' è costituita la struct:CODICEstruct vertici_poligono
{
float x[100];
float y[100];
int numv;
};
Non si tratta di una variabile vera e propria, piuttosto di quello che in C viene definito 'prototipo'. Si avvisa il compilatore che prima o poi si useranno delle variabili che avranno quella 'forma' (il compilatore utilizza questa informazione solamente per determinare lo spazio in memoria utilizzato dalla variabile che si andrà successivamente a dichiarare).
Come si vede si sta dicendo che la variabile conterrà un vettore x costituito da 100 posizioni, un vettore y anch'esso di 100 posizioni (ovviamente saranno le coordinate x ed y dei singoli vertici che costituiranno il poligono), numeri in virgola mobile, ed infine un singolo intero che conterrà il numero effettivo di vertici che costituisce il poligono. Superando i 100 vertici, lo anticipo, succedono sfracelli.
Da qualche parte nel mio codice, prima di chiamare la funzione che adesso presenterò, bisognerà dichiarare le variabili polig1 e polig2, in questo modo:CODICEstruct vertici_poligono polig1,polig2;
E quando bisognerà richiamare i dati troverete espressioni del genere: polig1.x[k], oppure polig1.numv
In sintesi, con il (.) ci si infila dentro la variabile, nelle sue sotto-variabili.
Ultima avvertenza, polig1 sarà la variabile che contiene il poligono originario; polig2 sarà la variabile che conterrà il poligono offsettato.
Nel codice provvederò a creare il poligono distanziato dall'originale del parametro in ingresso alla funzione dist. Se l'altro parametro flag vale 1 il nuovo poligono sarà quello interno, se invece flag vale -1 il nuovo poligono sarà esterno. L'eventuale poligono esterno abbiamo detto si otterrebbe cambiando di segno il valore di d' (vedi post precedente), ma questa informazione dovrebbe darla l'utente con una variabile aggiuntiva (il segno di spunta su una casella, ecc.)CODICEvoid offset_poligono(float dist,int flag)
{
int register k;
int km1,kp1;
float azm1,azm2,azmb,alfa;
float dist1;
for (k=1;k<=polig1.numv;k++)
{
if (k==1) km1=polig1.numv; else km1=k-1;
if (k==polig1.numv) kp1=1; else kp1=k+1;
azm1=azimuth_segmento(polig1.x[k],polig1.y[k],polig1.x[km1],polig1.y[km1]);
azm2=azimuth_segmento(polig1.x[k],polig1.y[k],polig1.x[kp1],polig1.y[kp1]);
azmb=(azm1+azm2)/2;
alfa=fabs(azmb-azm2);
dist1=flag*dist/sin(alfa);
polig2.x[k]=polig1.x[k]+dist1*sin(azmb);
polig2.y[k]=polig1.x[k]+dist1*cos(azmb);
}
polig2.numv=polig1.numv;
}
In definitiva come potete vedere poche righe. Il grosso del lavoro lo fa la funzione che calcola gli azimuth.
Infine ho provveduto a calcolare l'angolo alfa per il calcolo di dist1 in valore assoluto, in modo che non ci sia il problema orario/antiorario.
Ho fatto una cortesia ad afazio, se intende convertire queste poche righe in VBA di partire con l'indice 1 per il vettore di x ed y.
In effetti in C i vettori dimensionati 100, partono dal numero 0 ed arrivano a 99.
[Ad esempio il primo contatore avrei dovuto scrivere: for(k=0;k<=polig1.numv-1;k++)]
Infine piccola dissertazione su flag. E' sicuro che quando tra tre mesi qualcuno (anche io stesso) dovesse riutilizzare la funzione, non capirà affatto a cosa serve flag e che valori esso potrà avere.
Quindi documentare bene la funzione in modo da far risaltare che flag deve per forza valere 1 oppure -1 (tertium non datur).
Ad esempio passando flag=0, si ottiene esattamente lo stesso poligono originario.. -
.
Ottimo.
Ho trovato cosa fare per questo fine settimana..
Algoritmi: Offset di un poligono |
