LABORATORIO - INTEGRAZIONE ALL'ESERCIZIO SUL GRAFO

• Lettura del grafo dal file di input
• Traduzione delle coordinate del grafo da coordinate logiche lette da file a coordinate di device in pixel

Struttura dati per il grafo

Il modo piu' facile per memorizzare il grafo e' usare 4 array:

• Due array di double double[] x; e double[] y; per memorizzare le coordinate dei vertici. Questi due array vanno dimensionati al numero di vertici letto da file, e poi i vari elementi x[i], y[i] vanno riempiti con le coppie di coordinate lette dal file.
• Due array di int int[] a; e int[] b; per memorizzare gli archi. Questi due array vanno dimensionati al numero di archi letto da file, e poi i vari elementi a[j], b[j] vanno riempiti con le coppie di numeri interi letti dal file.

Come interpretare il contenuto della struttura dati

Vertici

Il vertice i-esimo ha come coordinate i due numeri double contenuti in x[i],y[i].
Bisogna tradurre queste coordinate logiche in coordinate di device e poi disegnare il vertice come un cerchietto centrato su quelle coordinate.

Archi

L'arco j-esimo ha come vertici estremi i due vertici che occupano, nei due array delle coordinate, le posizioni a[j] e b[j]. Trovo le coordinate dei due vertici quardando gli array x e y a quelle posizioni.
Le coordinate del primo estremo sono x[a[j]], y[a[j]] e quelle del secondo estremo sono x[b[j]], y[b[j]].
Bisogna tradurre queste coordinate logiche in coordinate di device e poi disegnare l'arco come un segmento di retta tra i due punti.

Dati del problema

Abbiamo due rettangoli:

• Il dominio del grafo, con (x0,y0) punto di aggangio (angolo di x ed y minime) e deltaX, deltaY lunghezze dei lati del terrangolo sull'asse x e y. Qui l'asse y e' orientato come siamo abituati, dal basso verso l'alto.
• Il pannello in cui deve essere visualizzato, con (0,0) punto di aggancio e w,h larghezza ed altezza. Qui l'asse y e' orientato al contrario, dall'alto verso il basso.

Variante 1

Il primo rettangolo (dominio) deve essere trasformato per andare a coincidere con il secondo rettangolo (pannello).
Questo implica deformazione se la proporzione tra deltaX e deltaY non coincide con quella esistente fra w e h. Poi vedremo due varianti che evitano la deformazione...

Dato un punto P=(xL,yL) in coordinate nel primo rettangolo (coordinate logiche), vogliamo trovare le coordinate (xD,yD) dello spesso punto (coordinate di device) nel secondo rettangolo.

Possiamo trattare x e y in modo indipendente.

Trasformazione per la x

In coordinate di device, xD esprime la distanza di P dalla parete sinistra del pannello (che e' anche l'asse x).

In coordinate logiche, la distanza di P dalla parete sinistra del dominio (retta di equazione x=x0) e' espressa da (xL-x0).

Fra le quantita' xD e (xL-x0) deve esistere la stessa proporzione che tra w e deltaX. Ovvero:
xD / (xL-x0) = w / deltaX.
In tale equazione l'incognita e' xD, percio' risolvendo abbiamo:
xD = (xL-x0) * (w/deltaX).

Trasformazione per la y

In coordinate di device, yD esprime la distanza di P dalla parete in alto del pannello (che e' anche l'asse y).

In coordinate logiche, la quantita' (yL-y0) esprime la la distanza di P dalla parete in basso del dominio (retta di equazione y=y0). Invece la distanza di P dalla parete in alto del dominio (retta di equazione x=y0+deltaY) e' espressa da: deltaY-(y-y0) = deltaY-y+y0.

Fra le quantita' yD e (deltaY-y+y0) deve esistere la stessa proporzione che tra h e deltaY. Ovvero:
yD / (deltaY-y+y0) = h / deltaY.
In tale equazione l'incognita e' yD, percio' risolvendo abbiamo:
yD = (deltaY-yL+y0) * (h/deltaY) = deltaY*(h/deltaY) - (yL-y0)*(h/deltaY) = h - (yL-y0)*(h/deltaY).

Altre varianti

Vogliamo mantenere la aspect ratio (rapporto fra le due dimensioni) del dominio quando lo mappiamo nel pannello. Possiamo fare in due modi:

1. Mappiamo tutto il dominio in una sotto-parte del pannello che abbia le stesse proporzioni del dominio, ved. figura variante 2.
2. Mappiamo in tutto il pannello una sotto-parte del dominio che abbia le stesse proporzioni del pannello, ved. figura variante 3.

Variante 2

Nelle equazioni della Variante 1, la x subisce una scalatura di w/deltaX e la y di h/deltaY. In questa variante, vogliamo scalare entrambe dello stesso fattore, il piu' piccolo dei due. In modo tale, una delle due coordinate verra' scalata "troppo", e il suo lato del dominio non occupera' tutto l'equivalente spazio nel pannello.

Consideriamo il rapporto minimo tra w/deltaX e h/deltaY.
Sia f = min{ (w/deltaX), (h/deltaY) }.

Applichiamo questo rapporto a entrambe le coordinate:
xD = (xL-x0)*f e yD = h - (yL-y0)*f.
Cosi' abbiamo ottenuto la Variante 2(a) in figura, cioe' nel pannello lo spazio occupato dall'immagine del dominio e' attaccato all'asse y (nel caso di figura) o x (nel caso le proporzioni fossero invertite).

Potremmo, invece, volerlo collocare al centro come nella Variante 2(b) di figura. Per fare questo bisogna agire sulla coordinata, delle due, che e' stata moltiplicata per un fattore "non suo", cioe' sulla x se il minimo f accade sulla y e sulla y se il minimo f accade sulla x. In figura dobbiamo agire sulla y.

La y va traslata di una quantita' pari a meta' dello spazio che "avanza". Lo spazio che avanza e' dato dalla differenza tra lo spazio totale (=h, altezza del pannello) e lo spazio occupato dall'immagine del dominio (=deltaY*f).
Lo spazio che avanza e' quindi: s = h - (deltaY*f).
E l'espressione finale per la y e': yD = h - (yL-y0)*f + s/2.

Variante 3

Nelle equazioni della Variante 1, la x subisce una scalatura di w/deltaX e la y di h/deltaY. In questa variante, vogliamo scalare entrambe dello stesso fattore, il piu' grande dei due. In modo tale, una delle due coordinate verra' scalata "troppo poco", e il suo lato del dominio strabordera' fuori dall'equivalente spazio nel pannello.

Consideriamo il rapporto massimo tra w/deltaX e h/deltaY.
Sia F = max{ (w/deltaX), (h/deltaY) }.

Applichiamo questo rapporto a entrambe le coordinate:
xD = (xL-x0)*F e yD = h - (yL-y0)*F.
Cosi' abbiamo ottenuto la Variante 3 in figura, cioe' la parte di dominio che cade fuori dal pannello e' quella piu' distante dall'asse (in questo caso asse y) delle coordinate logiche.
La si potrebbe invece centrare... con ragionamento analogo a quello fatto per passare da variante 2(a) a variante 2(b).

Facciamolo con le trasformazioni Java

Le equazioni tipo xD = ... e yD = ... corrisposdono all'opzione di "fare a mano" la traduzione di coordinate.
Potremmo usare invece le trasformazioni di coordinate della grafica 2D di Java.

Nelle equazioni viste, per es. quella della x (della y) nella variante 1:

• partiamo da xL (yL) e seguiamo tutti i passaggi
• ogni volta che moltiplichiamo per una costante, questa e' una scalatura
• ogni volta che sommiamo/sottraiamo una costante, questa e' una traslazione.
• se sottraiamo da una costante il risultato finora calcolato, questo equivale a cambiare di segno (=moltiplicare per -1) e sommare la costante: k-x = (-1*x)+k

Nell'esempio: xD = (xL-x0) * (w/deltaX)

• -x0 e' traslazione
• * (w/deltaX) e' scalatura

• -y0 e' traslazione
• *(h/deltaY) e' scalatura
• -1* e' scalatura negativa (ribaltamento)
• +h e' traslazione

1. traslazione di (-x0,-y0) = porta il punto di aggancio (x0,y0) del dominio nell'origine
2. scalatura di (w/deltaX, h/deltaY) = fai coincidere le dimensioni del dominio con quelle del pannello
3. ulteriore scalatura di (1,-1) = lascia la x invariata e ribalta la y
4. traslazione di (0,h) = lascia la x invariata e sposta la y