Newsgroup: it.comp.programmare.win32
Titolo: [FORSE OT] Problema con algoritmo

salve a tutti :)
Innanzitutto mi scuso se non e' il ng giusto, ma ho un po' cercato e
non sembrano esserci ng 'giusti' ;)
ho un problema e mi domandavo se qualcuno ha un'idea per risolverlo in
maniera 'carina'.
Allora:
Io ho una griglia rettangolare MxN, i vertici del rattangolo si
possono muovere liberamente. Alla fine del movimento devo poter
calcolare dove si trovano i punti interni rettangolo deformato.
la soluzione che mi e' venuta in mente e' di calcolarmi le
intersezioni tra rette che uniscono i punti corrispondenti sui lati
opposti; quello che vorrei sapere e' se esiste un qualche
teorema/formula/algoritmo di geometria che risolva la questione.
mi sono venute in mente alcune reminescenze del corso di geometria, ma
nessuna delle tecniche per maneggiare le trasformazioni in forma
matriciale mi sembrava adatta.
grazie a tutti.
garph0

 sui lati opposti; [...]
Non ricordo teoremi che possano risultare utili; per semplificare il
lavoro potresti dividere il quadrilatero in due triangoli, poi
determinare se un punto e` contenuto in un triangolo dovrebbe essere un
po' piu` facile.
Oppure, essendo un newsgroup che tratta di programmazione Windows,
potresti usare le regioni: puoi creare una regione poligonale con
CreatePolygonRgn(), poi verificare se un punto e` al suo interno con
PtInRegion().
Attenzione che se ti servono alte velocita`, le regioni non sono
esattamente un fulmine.
---
Bye! Lorenzo Lutti
http://www.geocities.com/cirovampiro/


mmmm... a me servono le coordinate precise dei punti che formano i
reticolo...
attacco qua una immagine, muy piccola, per spiegare cosa mi serve.
Ci sono le due configurazioni, una iniziale e una qualsiasi
configurazione finale.
io conosco la posizione dei punti in verde (vertici :) ) e devo
calcolarmi la posizione dei punti in rosso.
una ricerca attraverso le regions non mi sembra fattibile... a parte
la velocita' il fatto e' che per vedere se un punto e' in una regione,
devo conoscerne le coordinate, che sono esattamente quello che devo
calcolarmi :)
g0

 configurazione finale.
non siamo in un NG binario
ti hanno segato l'attachement :(
se hai uno spazio web metti l'allegato lě e posta l'url
--
ciao
xAERO

 attacco qua una immagine, muy piccola
Devi usare un newsgroup per i binari, altrimenti gli attach vengono
segati in pochissimo tempo e solo pochi eletti fanno in tempo a
vederli... io non sono uno di quelli. :)


 garph0
Diciamo che sei leggermente OT. Sicuramente comp.graphics.algorithms
era il newsgroup giusto. Ma tutto sommato sei perdonato! ;-)
Non e' una soluzione banalissima (direi il contrario se si considera
una soluzione analitica, vedi piu' sotto). Oltretutto se il poligono
non e' convesso le tue intersezioni della griglia cadono all'esterno
del poligono. Es:
  A    B               A
  *    *               *
                        *   B
  *    *            *   C   *
  D    C            D
Come gia' anticipato la trattazione analitica del problema e' piuttosto
complessa. Esitono volumi interi di geometria analitica che trattano la
trasformazione degli spazi (in particolare quelli planari) e cioe'
quelle leggi che permettono di passare da un sistema di coordinate
ad un altro solo conoscendo alcuni punti in comune tra i due spazi.
Quello che devi fare e' calcolare i coefficenti geometrici di una
TRASFORMAZIONE che solo nel caso piu' fortunato e' lineare (traslazione,
rotazione e ridimensionamento). Es dati 3 punti in uno spazio A di
coordinate Pi(xi,yi) e 3 punti in uno spazio B di coordinate Qi(ri,si)
(per i=1,2,3):
         P2                    Q2
           *                    *
   P1 *      *P3 ->  Q1           Q3
                     *            *
si ha che:
 ri = a * xi + b * yi + c                     (1)
 si = d * xi + e * yi + f    (per i=1,2,3)
passando alle coordinate omogenee (versione matriciale) si ha:
[r1]  [x1  y1  1]   [a]
[r2]= [x2  y2  1] * [b]
[r3]  [x3  y3  1]   [c]
[s1]  [x1  y1  1]   [d]
[s2]= [x2  y2  1] * [e]
[s3]  [x3  y3  1]   [f]
risolvendo l'equazione per i coeeficenti del sistema lineare otteniamo:
                -1
[a]  [x1  y1  1]   [r1]
[b]= [x2  y2  1] * [r2]
[c]  [x3  y3  1]   [r3]
                -1
[a]  [x1  y1  1]   [s1]
[b]= [x2  y2  1] * [s2]
[c]  [x3  y3  1]   [s3]
Fin qui e' facile. Ora mettiamo il caso che il fattore di scala non sia
costante. Ti dico solo che passare da un sistema di coordinate all'altro
servono come minimo 6 punti di riferimento che porta la (1) al sistema
di 2° ordine:
r = a5 * x^2 + a4 * y^2 + a3 * x + a2 * y + a1 * x * y + a0
s = b5 * x^2 + b4 * y^2 + b3 * x + b2 * y + b1 * x * y + b0
...e ti lascio immaginare la matrice 6x6 dei coefficenti per calcolare
le 12 incognite del sistema! E questo sarebbe solo l'inizio....8-S
Come vedi questa strada non e' percorribile (a meno che non ti
piaccia il masochismo :^) e neanche utile visto che noi abbiamo
dei vincoli molto stretti (la linearita' del sistema).
La soluzione, quindi, si sposta verso un algoritmo di individuazione
del coefficente angolare delle rette del reticolo passanti per quel
punto! La geometria ci viene incontro con questa semplice
considerazione grafica:
  Dato il solito rettangolo di partenza e il quadrangolo trasformato
  consideriamo i punti P e Q creati intersecando la prosecuzione dei
  segmenti che formano i lati del poligono convesso.
                           P
                           *
  A    B               A      B
  *    *               *      *                 *Q
            ->           *K    C
  *    *            D          *
  D    C            *
Si notera' subito che per un qualunque punto K interno il coefficente
angolare delle rette del reticolo e' forzatamente nel range formato
da AD-BC e AB-CD e piu' precisamente quelli passanti per K valgono KQ-PK.
Per analogia basta notare che il rettangolo di partenza ABCD ha i punti
P e Q sulla retta impropria. A questo punto il gioco e' fatto.
Calcolando le intersezioni sui lati del poligono e possibile risalire
alle coordinate di partenza (grazie a una parametrizzazione lineare) e
trovare di conseguenza le coordinate nel sitema originale.
Se invece si vuole disporre del massimo grado di liberta trasformando il
rettangolo con la sua griglia in una qualunque forma si deve concentrare
l'attenzione sulle Splines, cioe' curve costituite da polinomi di 3°
grado (o superiore) dette blending function. Esistono numerosi tipi di
spline (Hermite, Bezier, uniform nonration B-spline, nonuniform
nonration B-Spline, nonuniform rational B-Spline dette comunemente
NURBS ecc ecc). Quello che devi creare e' una patch rettangolare
parametrizzando la superfice attraverso 2 soli parametri U-V.
Quando ai realizzato tutto questo devi creare un algoritmo
di passaggio tra U-V -> X-Y. Le rette delle tua griglia di partenza
diverranno', dopo la trasformazione, linee a parametro costante
(es. se 0<=U<=1 k=0,0.2,0.4,0.6,0.8,1). Calcolare comunque il punto
esatto sulla patch (trovare U e V del punto) non e' semplice come prima.
Ci sono due strade: poligonizzare la patch e ricondurre tutto alla soluzione
precedente oppure calcolare le coordinate con un algoritmo di ricorsione
per approssimazioni successive (non semplicissimo ma abbastanza rapido,
complessita' proporzionale a log n).
Ultima notazione in caso di texture mapping. Visto la possibilita' di un
notevole streching delle dimensioni del poligono e' VIVAMENTE consigliato
utilizzare un doppio texture mapping (originale e trasformato)con un
bel oversampling per evitare che l'immagine si sgrani troppo.
Per ora e' tutto.....e come dice Morpheus in Matrix :
"Welcome....to the real world!"
Ciao.
Il Michett@
--
p.s. Faccio pubblica ammenda per l'OT!

A completamento di quanto detto nel messaggio precedente me' venuto
in mente che su "Digital Imaging - Theory and Application" c'era un
un algoritmo di una trasfomazione del primo ordine (warping)
piuttosto efficente che richiede solo 4 punti di controllo
(precisamente gli  angoli del rettangolo) per passare da uno spazio
X a uno X':
x' = a0 + a1*x + a2*y + a3*x*y
y' = b0 + b1*x + b2*y + b3*x*y
Questo e' sicuramente meno impegnativo di un secondo ordine o superiore
ed e' facilmente maneggiabile. Ecco il codice relativo:
/*********************************************************/
/* first-order polynomial warp                           */
/*********************************************************/
#define  XSIZE  640
#define  YSIZE  480
main()
  {
  unsigned char *ir,*ig,*ib;
  unsigned char *or,*og,*ob;
  long  int  ix,iy;
  long  int  ox,oy;
  long  int  x1,x2,x3,x4;
  long  int  y1,y2,y3,y4;
  double     xa0,xa1,xa2,xa3;
  double     ya0,ya1,ya2,ya3;
  double     IX,IY;
  double     OX,OY;
  double     DX,DY;
  /* set corner warp control points */
  x1 = 140; y1 = 10;
  x2 = 535; y2 = 105;
  x3 = 610; y3 = 360;
  x4 = -30; y4 = 400;
  /* calculate X coefficients */
  xa0 = (double)x1;
  xa1 = (double)(x4 - x1) / (double)YSIZE;
  xa2 = (double)(x2 - x1) / (double)XSIZE;
  xa3 = (double)(x1-x2+x3-x4) / (double)XSIZE / (double)YSIZE;
  /* calculate Y coefficients */
  ya0 = (double)y1;
  ya1 = (double)(y4 - y1) / YSIZE;
  ya2 = (double)(y2 - y1) / XSIZE;
  ya3 = (double)(y1-y2+y3-y4) / XSIZE / YSIZE;
  /* allocate input and output memory buffers */
  ir = (unsigned char *) malloc (XSIZE*YSIZE);
  ig = (unsigned char *) malloc (XSIZE*YSIZE);
  ib = (unsigned char *) malloc (XSIZE*YSIZE);
  or = (unsigned char *) malloc (XSIZE*YSIZE);
  og = (unsigned char *) malloc (XSIZE*YSIZE);
  ob = (unsigned char *) malloc (XSIZE*YSIZE);
  /* read the input image */
  read_image("input",ir,ig,ib);
  /* process all lines of image */
  /* note: since this is a forward transform,
       compute location every 1/2 pixel */
  for (IY = 0; IY < YSIZE; IY = IY + 0.5)
    {
    for (IX = 0; IX < XSIZE; IX = IX + 0.5)
      {
      /* compute output pixel location */
      OX = xa0 + (xa1 * IY) + (xa2 * IX) + (xa3 * IX * IY);
      OY = ya0 + (ya1 * IY) + (ya2 * IX) + (ya3 * IX * IY);
      /* reduce input and output pixel locations to integer */
      ix = (long)IX;
      iy = (long)IY;
      ox = (long)(OX + 0.5);
      oy = (long)(OY + 0.5);
      /* select nearest neighbor */
      /* note: bilinear interpolation could also be performed */
      if ((ox >= 0) && (ox < XSIZE) && (oy >= 0) && (oy < YSIZE))
        {
        or[(oy*XSIZE)+ox] = ir[(iy*XSIZE)+ix];
        og[(oy*XSIZE)+ox] = ig[(iy*XSIZE)+ix];
        ob[(oy*XSIZE)+ox] = ib[(iy*XSIZE)+ix];
        }
      }
    }
  /* write the output image */
  write_image("output",or,og,ob);
  /* free memory buffers */
  free(ir);
  free(ig);
  free(ib);
  free(or);
  free(og);
  free(ob);
  }
Ciao.
Il Michett@
--