Author Topic: Offset di una poligonale  (Read 4090 times)

0 Members and 1 Guest are viewing this topic.

zax2010

  • Guest
Offset di una poligonale
« on: 02 May , 2012, 22:46:03 PM »
Da una discussione in chat con afazio.
Un algoritmo per determinare una poligonale parallela ad un'altra, al suo interno.

Code: [Select]
/* reg1=n. del poligono che viene creato dalla operazione di offset */
/* reg2=n. del poligono di partenza di cui fare l'offset */
/* dist=distanza dell'offset */

Offset(int reg1,int reg2,float dist)
{
 int register k,np,nsz;
 int flag,att=0;
 float m0,m1,q0,q1,d0,d1,x,y;

 x=(poli[reg2].x[0]+poli[reg2].x[1])/2;
 y=(poli[reg2].y[0]+poli[reg2].y[1])/2;

 if (poli[reg2].x[0]-poli[reg2].x[poli[reg2].numv-1]==0)
    {
     m0=1234.56; q0=poli[reg2].x[0];
     if (x>poli[reg2].x[0]) flag=-1; else flag=1;
     if (poli[reg2].y[0]-poli[reg2].y[poli[reg2].numv-1]>0) d0=dist; else d0=-dist;
    }
 else
    {
     m0=(poli[reg2].y[0]-poli[reg2].y[poli[reg2].numv-1])/(poli[reg2].x[0]-poli[reg2].x[poli[reg2].numv-1]);
     q0=poli[reg2].y[poli[reg2].numv-1]-m0*poli[reg2].x[poli[reg2].numv-1];
     if (y>m0*x+q0) flag=1; else flag=-1;
     if (poli[reg2].x[0]-poli[reg2].x[poli[reg2].numv-1]<0) flag=-flag;
     d0=flag*dist/cos(atan(m0));
     if (poli[reg2].x[0]-poli[reg2].x[poli[reg2].numv-1]<0) d0=-d0;
    }

 for (k=0;k<=poli[reg2].numv-1;k++)
     {
      int pfin=k+1;

      if (pfin>poli[reg2].numv-1) pfin=0;

      if (m0>=1234.56) att=1;

      if (poli[reg2].x[pfin]-poli[reg2].x[k]==0)
         {
          m1=1234.56; q1=poli[reg2].x[k];
          if (poli[reg2].y[pfin]-poli[reg2].y[k]>0) d1=dist; else d1=-dist;
          att=2;
         }
      else
         {
          m1=(poli[reg2].y[pfin]-poli[reg2].y[k])/(poli[reg2].x[pfin]-poli[reg2].x[k]);
          q1=poli[reg2].y[k]-m1*poli[reg2].x[k];
          d1=flag*dist/cos(atan(m1));
          if (poli[reg2].x[pfin]-poli[reg2].x[k]<0) d1=-d1;
         }
      switch (att)
         {
          case 0: poli[reg1].x[k+poli[reg1].numv]=(q0-q1+d0-d1)/(m1-m0);
                  poli[reg1].y[k+poli[reg1].numv]=m0*poli[reg1].x[k+poli[reg1].numv]+q0+d0;
                  break;
          case 1: poli[reg1].x[k+poli[reg1].numv]=q0-flag*d0;
                  poli[reg1].y[k+poli[reg1].numv]=m1*poli[reg1].x[k+poli[reg1].numv]+q1+d1;
                  break;
          case 2: poli[reg1].x[k+poli[reg1].numv]=q1-flag*d1;
                  poli[reg1].y[k+poli[reg1].numv]=m0*poli[reg1].x[k+poli[reg1].numv]+q0+d0;
                  break;
          }

      m0=m1; q0=q1; d0=d1; att=0;
     }
 poli[reg1].numv+=poli[reg2].numv;
}

zax2010

  • Guest
Re: Offset di una poligonale
« Reply #1 on: 03 May , 2012, 14:15:13 PM »
Capisco si sia capito pochissimo. Ieri sera volevo far vedere ad afazio il listato, e non ho nè introdotto l'argomento, nè commentato bene il listato.

Posto intanto, quindi, la figura:





Il problema, a prima vista banale, è il seguente: data una poligonale chiusa, con i vertici ordinati in modo da percorrere il poligono stesso in senso orario, trovare le coordinate dei vertici del poligono interno al primo, e con i lati distanziati della quantità dist.
Nient'altro che quanto facciamo giornalmente e più o più volte con il nostro CAD preferito.

Procedendo 'manualmente' il problema risulta banale, come dicevo, ma creare una procedura 'automatica' e numerica non lo è affatto (o almeno, io ho trovato parecchie difficoltà).

Parlandone in chat con afazio egli aveva istantaneamente prospettato un procedimento che tramite la bisettrice dell'angolo formato dalla poligonale al vertice i, consentisse di trovare il vertice cercato. Egli riteneva, a mio avviso errando, che bisognasse scegliere solamente tra due possibili vertici, uno interno, l'altro esterno al poligono.
Già così come si è parlato altre volte il concetto 'interno'/'esterno' non è affatto banale (anche questo) come apparirebbe a prima vista.
Ma in effetti risulta anche difficile decidere di quale angolo si parla. Perchè in effetti le bisettrici sarebbero 2, e quindi i punti possibili candidati 4.

In passato ci avevo sbattuto la testa proprio con questo approccio senza riuscire a trovare un criterio numerico che mi consentisse certamente di scartare i 3 vertici e considerare solamente quello realmente interno.
(Si tratta dell'approccio rappresentato nella parte superiore della figura di cui sopra)

In realtà alla fine ho seguito un altro approccio, ovvero quello di determinare quattro rette a due a due parallele ai due segmenti che uniscono il vertice i al vertice i-1 ed i+1, e riuscire infine a decidere quale sia il punto certamente interno al poligono (con l'ipotesi che il poligono sia certamente costruito con il senso orario di ordinamento dei vertici stessi).
(Parte bassa della figura).

L'algoritmo che ho postato nel post precedente quindi persegue questa via. Esso funziona. Ma esso è frutto di una serie di sessioni di debug, in cui ho pazientemente inserito vertici comunque disposti, ed in cui di volta in volta ho 'messo le pezze' in modo che restituisse esattamente ciò che volevo.

In realtà sono sicuro di aver sbagliato approccio, troppe 'pezze', troppi if. E così troppe condizioni fanno si che nemmeno io ricordi più come e perchè l'algoritmo funzioni.

In pratica per ogni segmento calcolo le equazioni delle rette ad esso parallelo, quindi definito m, il coefficiente angolare del segmento, trovo le rette parallele con una equazione y=m*x+q, in cui m è proprio il coefficiente angolare del segmento considerato e q varrebbe il q del segmento sottraendo e/o sommando dist proiettato sull'asse delle y.

Il trucco è tutto qui. m0 e q0 sono coefficiente angolare e segmento sulle ascisse staccato dal segmento che va dal vertice i-1 ad i.
Invece m1 e q1 sono coefficiente angolare e segmento sulle ascisse del segmento che va da i ad i+1.

sommando/sottraendo ai q dist opportunamente proiettato trovo le quattro rette da cui 4 intersezioni.
In realtà ho il parametro flag che, con valore 1 o -1, subito mi fa scartare una delle due rette, per cui riesco a trovare un solo punto, scartando preventivamente gli altri.

Non lo so se così ho reso più 'leggibile' il tabulato di cui sopra. Ma il mio intento è quello di stimolare il pensiero circa un 'metodo' migliore di quello da me implementato.

Fate delle prove con Autocad. Lì l'algoritmo utilizzato è evidentemente molto sofisticato. Se dist raggiunge una certa entità il nuovo poligono, se interno al primo, non necessariamente avrà lo stesso numero di vertici dell'originale. L'algoritmo presentato invece questa particolarità non la possiede.
« Last Edit: 03 May , 2012, 14:17:27 PM by zax2010 »

Offline afazio

  • Veterano del forum
  • ****
  • Posts: 663
  • Karma: 273
  • dovizio mi delizio
    • CI si vede al Bar
Re: Offset di una poligonale
« Reply #2 on: 03 May , 2012, 17:01:26 PM »
Capisco si sia capito pochissimo. Ieri sera volevo far vedere ad afazio il listato, e non ho nè introdotto l'argomento, nè commentato bene il listato.

Posto intanto, quindi, la figura:





Il problema, a prima vista banale, è il seguente: data una poligonale chiusa, con i vertici ordinati in modo da percorrere il poligono stesso in senso orario, trovare le coordinate dei vertici del poligono interno al primo, e con i lati distanziati della quantità dist.
Nient'altro che quanto facciamo giornalmente e più o più volte con il nostro CAD preferito.

Procedendo 'manualmente' il problema risulta banale, come dicevo, ma creare una procedura 'automatica' e numerica non lo è affatto (o almeno, io ho trovato parecchie difficoltà).

Parlandone in chat con afazio egli aveva istantaneamente prospettato un procedimento che tramite la bisettrice dell'angolo formato dalla poligonale al vertice i, consentisse di trovare il vertice cercato. Egli riteneva, a mio avviso errando, che bisognasse scegliere solamente tra due possibili vertici, uno interno, l'altro esterno al poligono.
Già così come si è parlato altre volte il concetto 'interno'/'esterno' non è affatto banale (anche questo) come apparirebbe a prima vista.
Ma in effetti risulta anche difficile decidere di quale angolo si parla. Perchè in effetti le bisettrici sarebbero 2, e quindi i punti possibili candidati 4.

In passato ci avevo sbattuto la testa proprio con questo approccio senza riuscire a trovare un criterio numerico che mi consentisse certamente di scartare i 3 vertici e considerare solamente quello realmente interno.
(Si tratta dell'approccio rappresentato nella parte superiore della figura di cui sopra)

In realtà alla fine ho seguito un altro approccio, ovvero quello di determinare quattro rette a due a due parallele ai due segmenti che uniscono il vertice i al vertice i-1 ed i+1, e riuscire infine a decidere quale sia il punto certamente interno al poligono (con l'ipotesi che il poligono sia certamente costruito con il senso orario di ordinamento dei vertici stessi).
(Parte bassa della figura).

L'algoritmo che ho postato nel post precedente quindi persegue questa via. Esso funziona. Ma esso è frutto di una serie di sessioni di debug, in cui ho pazientemente inserito vertici comunque disposti, ed in cui di volta in volta ho 'messo le pezze' in modo che restituisse esattamente ciò che volevo.

In realtà sono sicuro di aver sbagliato approccio, troppe 'pezze', troppi if. E così troppe condizioni fanno si che nemmeno io ricordi più come e perchè l'algoritmo funzioni.

In pratica per ogni segmento calcolo le equazioni delle rette ad esso parallelo, quindi definito m, il coefficiente angolare del segmento, trovo le rette parallele con una equazione y=m*x+q, in cui m è proprio il coefficiente angolare del segmento considerato e q varrebbe il q del segmento sottraendo e/o sommando dist proiettato sull'asse delle y.

Il trucco è tutto qui. m0 e q0 sono coefficiente angolare e segmento sulle ascisse staccato dal segmento che va dal vertice i-1 ad i.
Invece m1 e q1 sono coefficiente angolare e segmento sulle ascisse del segmento che va da i ad i+1.

sommando/sottraendo ai q dist opportunamente proiettato trovo le quattro rette da cui 4 intersezioni.
In realtà ho il parametro flag che, con valore 1 o -1, subito mi fa scartare una delle due rette, per cui riesco a trovare un solo punto, scartando preventivamente gli altri.

Non lo so se così ho reso più 'leggibile' il tabulato di cui sopra. Ma il mio intento è quello di stimolare il pensiero circa un 'metodo' migliore di quello da me implementato.

Fate delle prove con Autocad. Lì l'algoritmo utilizzato è evidentemente molto sofisticato. Se dist raggiunge una certa entità il nuovo poligono, se interno al primo, non necessariamente avrà lo stesso numero di vertici dell'originale. L'algoritmo presentato invece questa particolarità non la possiede.


 io insisto sul fatto che la bisettrice falsa non esiste e che quindi in punti di partenza sono solo due e cioè quelli che stanno sulla bisettrice vera il primo da un lato ed il secondo dal lato opposto. Le coordinate di questi due punti si possono ricavare quasi immedamente.
Per adesso non ho nulla di ben definito da proporre ma mi è balenata in mente questa: fissiamo come quello giusto uno dei due, quindi determiniamo anche gli altri vertici ofsettati congruenti con la scelta del punto iniziale. Otteniamo cosi un poligono offset del primo. Questo potrebbe essere o quello interno o quello esterno.
Eì evidente che bastarebbe fare un confronto tra il perimetro di questo ottenuto ed il perimetro del poligono iniziale: se il nuovo poligono ha perimetro maggiore, allora torniamo indietro e scegliemo l'altro punto altrimenti abbiamo trovato il poligono cercato a prima botta.

ciao
« Ogni qualvolta una teoria ti sembra essere l’unica possibile, prendilo come un segno che non hai capito né la teoria né il problema che si intendeva risolvere. »
K.P.

Renato

  • Guest
Re: Offset di una poligonale
« Reply #3 on: 03 May , 2012, 17:25:51 PM »
               Xc(Nv% + 1, 1) = Xc(1, 1)
               Yc(Nv% + 1, 1) = Yc(1, 1)
               Xc(0, 1) = Xc(Nv%, 1)
               Yc(0, 1) = Yc(Nv%, 1)
             For I = 0 To Nv% - 1
                 X1 = Xc(I, 1): Y1 = Yc(I, 1)
                 X2 = Xc(I + 1, 1): Y2 = Yc(I + 1, 1)
                   az = AZIMUT1(X1, Y1, X2, Y2)
                 AzP = az + pi / 2#       ' azimut punto P normale al lato 1-2
                 Xp = X1 + Spessore * Sin(AzP)
                 Yp = Y1 + Spessore * Cos(AzP)
                 Xq = Xp + 100# * Sin(az)
                 Yq = Yp + 100# * Cos(az)

                 Ak(I) = Yp - Yq               'Coeff. retta P-Q
                 Bk(I) = Xq - Xp
                 Ck(I) = Xp * Yq - Xq * Yp
             Next I
                                     'Calcolo coord. vertici poligono interno
                 Ak(Nv%) = Ak(0)
                 Bk(Nv%) = Bk(0)
                 Ck(Nv%) = Ck(0)
           
             For I = 0 To Nv% - 1
                 ak1 = Ak(I): bk1 = Bk(I): ck1 = Ck(I)
                 ak2 = Ak(I + 1): bk2 = Bk(I + 1): ck2 = Ck(I + 1)
                     Delta = ak1 * bk2 - ak2 * bk1
                        If Delta = 0# Then
                           MsgBox ("Ci sono 2 lati consecutivi paralleli. Calcolo interrotto"), 48, ""
                           End
                        End If
                 X(I + 1) = (-bk2 * ck1 + bk1 * ck2) / Delta
                 Y(I + 1) = (-ak1 * Ck2 + Ak2 * ck1) / Delta
             Next I
               
                 X(0) = X(Nv%)
                 Y(0) = Y(Nv%)
                                 
                 X(Nv% + 1) = X(1)
                 Y(Nv% + 1) = Y(1)


Ho utilizzato in parte il ragionamento di Zax (ma la sub data di una quindicina d'anni). Cerco le parallele ai lati distanti della quantità Spessore (è l'offset positivo o negativo). Per evitare tentativi con gli angoli è utile calcolare l'Azimut Az (angolo in radianti formato dal lato corrente 1-2 con l'asse X del riferimento: l'azimut va da 0 a 2*PI) di ogni singolo lato. P e Q sono due punti qualsiasi del lato parallelo: Trovato P è immediato il calcolo di Q (distante 100) conoscendo l'azimut. P si trova sulla normale al lato 1-2, a distanza = Spessore, ed in corrispondenza del punto 1 origine dell'azimut.
ak, bk, ck  sono i coeff. dell'eq. retta nella forma ak*x +bk*y+ck=0
Xc(Nv),Yc(Nv) coord. ingresso
X(Nv),Y(Nv)  coord. uscita 

 

Sitemap 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24