[Java] disegnare rettangoli con valori non interi

[Pompolus]

Salve,

sto implementando un algoritmo per le Treemaps di shneidermann ma ho un problema.

Ho un rettangolo in input che devo dividere in altri 4 rettangoli coprendo tutta l'area del primo, secondo questa figura:


Il problema è che per seguire l'algoritmo, R1 ha un'area data quindi per farlo entrare correttamente devo fare areaR1/latocortodiR per ottenere la misura del secondo lato di R1.
Ora effettuando questa divisione il lato di R1 potrebbe essere un numero non intero e quando lo vado a disegnare (sto usando drawrect delle AWT) il valore viene approssimato ad un numero intero per usare i pixel.
Solo che così facendo gli altri rettangoli non coprono correttamente tutta l'area del rettangolo di partenza, ma non posso aumentare o diminuire le loro aree perchè vanno rispettate.
Inoltre l'algoritmo prevede di dividere ricorsivamente nello stesso modo i rettangoli R1,R2,R3 e così facendo accumulo errori ad ogni approssimazione.

Come faccio a far entrare correttamente i rettangoli? Ovvero come posso interpretare correttamente le dimensioni non intere dei loro lati senza perdere informazione con l'approssimazione per disegnarli in pixel?

Grazie per l'attenzione, se qualcosa non vi è chiaro o volete più dettagli dite pure

[yorkeiser]

Non credo di aver capito benissimo (non conoscendo neanche l'algoritmo che stai utilizzando) comunque provo lo stesso a darti qualche suggerimento: per la rappresentazione grafica non puoi farci niente, è discretizzata in base alla risoluzione dello schermo.
Ma nulla ti vieta di storare le coordinate dei vertici in variabili di tipo double, in maniera che anche facendo le eventuali operazioni non perdi di precisione (o comunque l'errore è molto piccolo). In sostanza, dovresti utilizzare un set di variabili di tipo double per le coordinate reali (su cui effettui le eventuali operazioni), e qui non perdi di precisione. Quando vai a fare la rappresentazione grafica, utilizzerai ovviamente dei cast ad int, con i quali dovrai necessariamente perdere qualcosa (e l'errore relativo sarà maggiore via via che suddividerai). A meno di non modificare progressivamente la scala dell'immagine disegnata: se diminuisci la scala, l'errore diventa minore visto che è al massimo di un pixel.

[Pompolus]

Originariamente inviato da yorkeiser

Non credo di aver capito benissimo (non conoscendo neanche l'algoritmo che stai utilizzando) comunque provo lo stesso a darti qualche suggerimento: per la rappresentazione grafica non puoi farci niente, è discretizzata in base alla risoluzione dello schermo.
Ma nulla ti vieta di storare le coordinate dei vertici in variabili di tipo double, in maniera che anche facendo le eventuali operazioni non perdi di precisione (o comunque l'errore è molto piccolo). In sostanza, dovresti utilizzare un set di variabili di tipo double per le coordinate reali (su cui effettui le eventuali operazioni), e qui non perdi di precisione. Quando vai a fare la rappresentazione grafica, utilizzerai ovviamente dei cast ad int, con i quali dovrai necessariamente perdere qualcosa (e l'errore relativo sarà maggiore via via che suddividerai). A meno di non modificare progressivamente la scala dell'immagine disegnata: se diminuisci la scala, l'errore diventa minore visto che è al massimo di un pixel.

Purtroppo è come già faccio, ma con un alto numero di elementi l'errore diventa comuqneu troppo grosso

[yorkeiser]

Originariamente inviato da Pompolus

Purtroppo è come già faccio, ma con un alto numero di elementi l'errore diventa comuqneu troppo grosso

Prova a postare un po' di codice (perlomeno le parti più importanti e quelle in cui perdi precisione) e vediamo se si può fare qualcosa: parlando astrattamente è difficile trovare una soluzione.

[MEMon]

yorkeiser credo sia stato molto chiaro.
Se devi rappresentare graficamente un numero(esempio una lunghezza) è normale approssimare per il semplice fatto che l'unità grafica più piccola è il pixel.

Se devi rappresentare un numero decimale ti devi porre il limite di che precisione vuoi, se vuoi arrivare fino ai decimi è normale che ogni pixel assuma il significato di 0.1, ai centesimi 0.01 e così via.

Inoltre come già ti è stato suggerito i calcoli li fai sempre sui valori NON approssimati.

[wizard1993]

Originariamente inviato da MEMon

yorkeiser credo sia stato molto chiaro.
Se devi rappresentare graficamente un numero(esempio una lunghezza) è normale approssimare per il semplice fatto che l'unità grafica più piccola è il pixel.

Se devi rappresentare un numero decimale ti devi porre il limite di che precisione vuoi, se vuoi arrivare fino ai decimi è normale che ogni pixel assuma il significato di 0.1, ai centesimi 0.01 e così via.

Inoltre come già ti è stato suggerito i calcoli li fai sempre sui valori NON approssimati.

poi visto che l'utente accusa una certa mancanza di precisione, gli suggerirei anche di usare le classi bigdecimal per non incorrere in errori di precisione

[Pompolus]

io il codice lo posto ma ho paura che non sia di facile interpretazione (sono poco ordinato )

comunque ecco qui il pezzo incriminato, ho aggiunto le righe //HARDWAREUPGRADE: blablabla
per cercare di spiegarvi come funziona

//trovo il miglior aspect ratio per RP
//HARDWAREUPGRADE: qui c'è il primo problema, devo far sì che il rettangolo 
//HARDWAREUPGRADE: di area "areap" sia il più possibile simile ad un 
//HARDWAREUPGRADE: quadrato, quindi faccio la radice quadrata ed 
//HARDWAREUPGRADE: ottengo il primo elemento non intero.
       double sqrtside1 = Math.sqrt(areap);
       double sqrtside2 = sqrtside1;

       double bestR2side;

//HARDWAREUPGRADE: quando trovate "wismax" è solo un controllo per 
//HARDWAREUPGRADE: vedere se l'height del rettangolo è maggior della 
//HARDWAREUPGRADE: Weight o viceversa.
       if (actualr.wismax == true){
           bestR2side = actualr.H - sqrtside1;
       }
       else{
           bestR2side = actualr.W - sqrtside1;
       }
       double bestR2area = bestR2side * sqrtside2;
       double tempR2area = 0;
       int index = actualindexp+1; //indice del primo elemento dopo P
       double el = -1;


//HARDWAREUPGRADE: questo passo serve a capire quanto deve essere 
//HARDWAREUPGRADE: grande il rettangolo R2. Avendo trovato il lato ideale 
//HARDWAREUPGRADE: di Rp per farlo sembrare un quadrato, il miglior 
//HARDWAREUPGRADE: rettangolo R2 sarebbe quello con il lato uguale al 
//HARDWAREUPGRADE: migliore per Rp e l'altro lato uguale alla Height di R 
//HARDWAREUPGRADE: (tutto il rettangolone) - la Height di Rp. Quindi 
//HARDWAREUPGRADE: aggiungo più elementi possibili dalla lista L2 senza
//HARDWAREUPGRADE:  sforare questa area ideale. Una volta che so al 
//HARDWAREUPGRADE: massimo  quanti elementi possono entrare, basta 
//HARDWAREUPGRADE: sommare le loro aree e so quanto deve essere grande 
//HARDWAREUPGRADE: l'area di R2.
       
//aggiungiamo elementi fino a non sforare l'area presunta di R2
       while(index < ElL.size() && (el = ((ElRect)ElL.get(index)).dim)+tempR2area <= bestR2area){
           tempR2area = tempR2area + el;
           ElRect temp = (ElRect) ElL.get(index);
           L2List.add(temp);
           index++;
       }

       while(index < ElL.size()){
           el = ((ElRect)ElL.get(index)).dim;
           ElRect temp = (ElRect) ElL.get(index);
           L3List.add(temp);
           index++;
       }

//HARDWAREUPGRADE: A questo punto posso creare sia Rp che R2, ma
//HARDWAREUPGRADE: ma devo per forza dividere l'area per il lato di R1 per
//HARDWAREUPGRADE: sapere quanto deve essere grande il lato in comune di
//HARDWAREUPGRADE: Rp e R2, e qui c'è il secondo problema!

       areaR2 = tempR2area;
       double R2plusRP = areap + areaR2;
       
       double sideR2RP = 0;
       sideR2RP = R2plusRP / (bestR2side+sqrtside1);

       double sideRP = 0;
       sideRP = areap / sideR2RP;
       
       double sideR2 = 0;
       sideR2 = areaR2 / sideR2RP;
       

//HARDWAREUPGRADE: ormai so sia le dimensioni di R1, che di Rp che di R2,
//HARDWAREUPGRADE: non mi resta che calcolare R3, ma è banale visto che
//HARDWAREUPGRADE: chela sua area sarà esattamente quella avanzata di R.
       double side1R3 = sideRP+sideR2;



//HARDWAREUPGRADE: ora che ho tutti i dati posso creare gli oggetti
//HARDWAREUPGRADE: "Rectangle" che verranno poi disegnati. E' a questo
//HARDWAREUPGRADE: punto che approssimo i vari double con Math.ceil()

       if (actualr.wismax == true){
           actualr.rp = new Rectangle ((int)Math.ceil(actualr.r1.X+actualr.r1.W), actualr.r1.Y, sideR2RP, sideRP);
           actualr.r2 = new Rectangle ((int)Math.ceil(actualr.r1.X+actualr.r1.W), (int)Math.ceil(actualr.r1.Y+sideRP), sideR2RP, sideR2);
           actualr.r3 = new Rectangle ((int)Math.ceil(actualr.r1.X+actualr.r1.W+actualr.rp.W), actualr.Y, actualr.W - actualr.r1.W - actualr.rp.W, actualr.H);
       }
       else{
           actualr.rp = new Rectangle ((int)Math.ceil(actualr.r1.X+sideR2), (int)Math.ceil(actualr.r1.Y+actualr.r1.H), sideRP, sideR2RP);
           actualr.r2 = new Rectangle (actualr.r1.X, (int)Math.ceil(actualr.r1.Y+actualr.r1.H), sideR2, sideR2RP);
           actualr.r3 = new Rectangle (actualr.X,(int)Math.ceil(actualr.Y+actualr.r1.H+actualr.r2.H),actualr.W,actualr.H - actualr.r1.H - actualr.rp.H);
       }


//HARDWAREUPGRADE: ho creato tutti i rettangoli e le nuove liste, quindi
//HARDWAREUPGRADE: riapplico questo algoritmo ai rettangoli R1,R2,R3
       
       if(L1List.size()>0)
           createTreemap(actualr.r1, L1List);
       if(L2List.size()>0)
           createTreemap(actualr.r2, L2List);
       if(L3List.size()>0)
           createTreemap(actualr.r3, L3List);

Spero di essere stato abbastanza chiaro.
Allego anche una foto dell'output del mio programma:

i bordi più neri sono quelli incriminati, sono i rettangoli che sforano di un pixel!

[wizard1993]

cambia tutti i double in bigdecimal, ci credo che ti perde precisione con tutti quei calcoli. con bigdecimal andari un po' più piano, ma sicuramente guadagni il precisione.

poi sinceramente non capisco perchè se ti serve un "rettangolo più simile possibile a un quadrato" non prendi direttamente un quadrato

[MEMon]

Lascia stare i bigdecimal almeno per ora...

Una semplice domanda, cui necessito una semplice risposta.
Se ti viene fuori ad esempio che:
R1 ha dimensioni 301.056x107.374
R2 ha dimensioni 301.701x107.532
R3 ha dimensioni 301.324x107.408

Come vorresti che fossero disegnati i suddetti rettangoli?
Tutti uguali? le minime differenze che fossero visibili? E quanto visibili?

ps. so che questi valori non sono reali dato l'algoritmo ma è per capirci.

[Pompolus]

Originariamente inviato da wizard1993

cambia tutti i double in bigdecimal, ci credo che ti perde precisione con tutti quei calcoli. con bigdecimal andari un po' più piano, ma sicuramente guadagni il precisione.

poi sinceramente non capisco perchè se ti serve un "rettangolo più simile possibile a un quadrato" non prendi direttamente un quadrato

Ho provato a fare un paio di prove ma anche con i BigDecimal non cambia nulla...

Il problema è che posso avere un tipo di dato di una precisione assurda, ma tanto quando devo andare a disegnarlo con le AWT, sempre a intero devo convertirlo e un pixel lo sfora comunque.


Per quanto riguarda il quadrato, non posso prenderlo direttamente perchè Rp e R2 devono avere un lato in comune e R2 deve contenere perfettamente vari elementi. Se facessi diventare direttamente Rp un quadrato, per far sì che R2 abbia un lato in comune con Rp significherebbe riuscire ad avere elementi la cui somma delle aree diano perfettamente R2, il che non è detto (anzi non è quasi mai così visto che gli elementi hanno area casuale).

[Pompolus]

Originariamente inviato da MEMon

Lascia stare i bigdecimal almeno per ora...

Una semplice domanda, cui necessito una semplice risposta.
Se ti viene fuori ad esempio che:
R1 ha dimensioni 301.056x107.374
R2 ha dimensioni 301.701x107.532
R3 ha dimensioni 301.324x107.408

Come vorresti che fossero disegnati i suddetti rettangoli?
Tutti uguali? le minime differenze che fossero visibili? E quanto visibili?

ps. so che questi valori non sono reali dato l'algoritmo ma è per capirci.

Principalemte mi interessa che il Rettangolo R sia suddiviso ESATTAMENTE in un numero di rettangolini pari a quello degli elementi in input.

Se poi per fare questo si debba modificare LEGGERMENTE le aree non è un problema.

Poi per l'esempio che fai tu, se ho capito che intendi ti dico che non ci sarà un controllo per vedere se quei rettangoli sono esattamente delle dimensioni giuste, basta che ad occhio umano siano verosimili.

[MEMon]

Ragioniamoci sopra.
Piccolo esempio pratico: hai un rettangolo di 10x5, che vuoi dividire in 3 rettangoli aventi la medesima area(in 3 parti uguali insomma).
Prendi il lato lungo e lo dividi per 3: 10/3=3.3 periodico.

Se dovessi disgenare questi rettangoli avente lato 3.333 verrebbe fuori un rettangolo 3x5.
Se sommo questi rettangoli, ovvero se li disegno dentro al rettangolo di partenza salta subito all'occhio che rimane dello spazio vuoto, precisamente

Il problema è anche inverso, se il tuo lato fosse stato di 11px allora avresti ottenuto rettangoli con lato di 3.6666 che approssimati sarebbero stati 4 px.
Sommandoli avresti ottenuto una dimensione totale di 12px quindi saresti andato fuori dai bordi(problema che si presenta nel tuo algoritrmo).

Come risolvo questo problema?
Semplice, non si può, a meno che non lo "unisci" ad uno dei 3 rettangoli.

E' possibile però renderlo meno incisivo, ora incide di 1px su 10, se il tuo rettangolo di partenza fosse stato 100x50, avrebbe inciso di 1px su 100, molto meno no?

[Pompolus]

Originariamente inviato da MEMon

Ragioniamoci sopra.
Piccolo esempio pratico: hai un rettangolo di 10x5, che vuoi dividire in 3 rettangoli avente la medesima area(in 3 parti uguali insomma).
Prendi il lato lungo e lo dividi per 3: 10/3=3.3 periodico.

Se dovessi disgenare questi rettangoli avente lato 3.333 verrebbe fuori un rettangolo 3x5.
Se sommo questi rettangoli, ovvero se li disegno dentro al rettangolo di partenza salta subito all'occhio che rimane dello spazio vuoto, precisamente


Come risolvo questo problema?
Semplice, non si può, a meno che non lo "unisci" ad uno dei 3 rettangoli.

E' possibile però renderlo meno incisivo, ora incide di 1px su 10, se il tuo rettangolo di partenza fosse stato 100x50, avrebbe inciso di 1px su 100, molto meno no?

Tutto giusto ma c'è una piccola differenza con il mio problema.

Tu sei partito da un rettangolo e vuoi dividerlo in 3 parti uguali, questo non è detto che si possa.

Io invece parto da un rettangolo di TOT area ed ho tanti altri rettangolini. Se sommiamo le aree di questi rettangolini otteniamo ESATTAMENTE l'area del rettangolo di partenza.

Come faccio a farli entrare perfettamente?

Bisogna però anche tenere conto che i rettangolini sono dati in un certo ordine e che alla fine della suddivisione quell'ordine deve rimanere invariato o comunque si deve poter risalire all'ordine iniziale, ovvero proprio quello che si propone da fare questo algoritmo per le treemaps.

[MEMon]

Non c'è differenza tra quello che vuoi fare tu e quello che ti ho esposto io.
Te ottieni tanti rettangolini ma con dimensioni razionali.
Io ottengo tre rettangoli con dimensioni razionali.
Dove sta la differenza?
Anche nel mio esempio se li sommo ottengo esattamente l'area di partenza, è quando li disegno il problema...proprio come succede nel tuo algoritmo.

Le possibili soluzioni sono due, o aumenti la scala fino ad ottenere una buona approsimazione grafica, o distribuisci l'errore in modo grafico.
Esempio di distribuzione dell'errore:
Caso in DIFETTO
Consideriamo sempre il rettangolo 10x5 da dividire in tre parti, ottieni tre rattngoli di dimensioni 3.33333x5 (3x5).
Calcoli l'errore (3-3.333333)*3=-1px, hai quindi un 1px in difetto di errore, questo pixel lo devi distribuire sui 3 rettangoli, essendo in questo caso 1px il minimo errore non divisibile, lo metti solo su un rettangolo.
Otterrai quindi due rettangoli 3x5 e uno 4x5.

Caso in ECCESSO
Il rettangolo di partenza è 11x5, dividendolo ottieni tre rettangoli 3.66666x5 (4x5).
Calcoli l'errore (4-3.66666)*3=1px, lo distribuisci in questo caso avrai due rettangoli 4x5 e uno 3x5.

[Pompolus]

Originariamente inviato da MEMon

Non c'è differenza tra quello che vuoi fare tu e quello che ti ho esposto io.
Te ottieni tanti rettangolini ma con dimensioni razionali.
Io ottengo tre rettangoli con dimensioni razionali.
Dove sta la differenza?

i rettangolini iniziali, hanno dimensioni intere

[MEMon]

E questo cosa centra?

[Pompolus]

Originariamente inviato da MEMon

Le possibili soluzioni sono due, o aumenti la scala fino ad ottenere una buona approsimazione grafica, o distribuisci l'errore in modo grafico.
Esempio di distribuzione dell'errore:
Caso in DIFETTO
Consideriamo sempre il rettangolo 10x5 da dividire in tre parti, ottieni tre rattngoli di dimensioni 3.33333x5 (3x5).
Calcoli l'errore (3-3.333333)*3=-1px, hai quindi un 1px in difetto di errore, questo pixel lo devi distribuire sui 3 rettangoli, essendo in questo caso 1px il minimo errore non divisibile, lo metti solo su un rettangolo.
Otterrai quindi due rettangoli 3x5 e uno 4x5.

Caso in ECCESSO
Il rettangolo di partenza è 11x5, dividendolo ottieni tre rettangoli 3.66666x5 (4x5).
Calcoli l'errore (4-3.66666)*3=1px, lo distribuisci in questo caso avrai due rettangoli 4x5 e uno 3x5.

non mi è ben chiaro come applucarlo al mio caso, ma ci penso e ti faccio sapere

[Pompolus]

Originariamente inviato da MEMon

E questo cosa centra?

forse nulla, d'altronde i fatti ti danno ragione per ora

Ma non esistono delle librerie per Java che permettano di disegnare rettangoli con dimensioni in DOUBLE?

[MEMon]

Pensandoci un attimo non avrai mai errori maggiori di 1px (a meno che non iteri l'errore ma non mi pare il tuo caso) quindi ti basta applicare l'errore ad uno solo dei rettangoli che trovi.
L'importante, visto che poi da quel che ho capito ripeti il procedimento, è che ti ricordi dove hai messo l'errore.

[MEMon]

Originariamente inviato da Pompolus

forse nulla, d'altronde i fatti ti danno ragione per ora

Ma non esistono delle librerie per Java che permettano di disegnare rettangoli con dimensioni in DOUBLE?

Pensaci, se l'unità grafica più piccola è il pixel, come fai a disegnare una dimensione di 10.83483 dando al pixel il valore di unità? sarebbero 10 pixel e poi cosa?

Devi cambiare scala.