Newsgroup: it.comp.lang.c++
Titolo: Algoritmo (quasi) impossibile

Gente, innanzitutto mi presento, in quanto nuovo di questo newsgroup: sono
AG 5° F e conosco c++ come autodidatta da circa 2 anni.
E' un bel pò di tempo che mi batte la testa sulla creazione di un algoritmo
che però non mi soddisfa mai abbastanza... se volete un bel (anche se vi
auguro di trovarlo semplice) rompicapo, ecco il mio problema:
Abbiamo una collezione di rettangoli, le cui dimensioni sono specificate
dall'utente prima dell'elaborazione.
L'utente può specificare per ogni rettangolo qualunque dimensione, purchè
intera (ma anche se fosse reale non credo che la cosa cambierebbe di molto),
e può inserire quanti rettangoli desidera.
L'algoritmo deve disporre i vari rettangoli all'interno di un'area il più
possibile piccola.
Vi faccio un esempio pratico, così capite a cosa mi serve l'algoritmo in
questione...
Devo realizzare un motore grafico 2D, e devo inserire più immagini possibili
all'interno della superficie più piccola possibile (per risparmiare
memoria). Chiaramente non è un'operazione che ho intenzione di svolgere a
run-time durante il gioco, per cui stò realizzando un editor che carica le
diverse immagini da file preesistenti o da memoria e poi le salva
all'interno di un'unica bitmap, disponendole nel modo migliore possibile e
nascondendo il lavoro all'utente, la cui unica preoccupazione deve essere
cercare immagini buone per gli sprite, senza curarsi di come queste vengono
memorizzate.
Credo che il problema sia abbastanza chiaro... ora vorrei fare un piccolo
chiarimento sullo spirito di questo messaggio: non l'ho scritto perchè
voglio lavarmi le mani da un problema che non sò risolvere... la mia "etica"
di programmatore autodidatta mi impone di perseverare su un problema il più
possibile, poichè il mio obiettivo primario quando programmo è imparare
nuove tecniche e cimentarmi in nuove sfide. A dimostrazione del fatto che
finora non sono stato a girarmi i pollici, vi propongo la soluzione a cui
sono giunto, ma che ancora non mi soddisfa più di tanto...
Concludo dicendo che SONO UN PROGRAMMATORE 18ENNE ISOLATO: non mi interessa
creare un gioco 2D da solo, poichè avrei di fronte una mole di lavoro troppo
grande; tuttavia desidero imparare il più possibile prima di cominciare a
"fare sul serio", nel caso riuscissi a metter su un gruppo di programmatori
che mi aiuti nello sviluppo del progetto.
AG5F
P.S.: sono un novellino dei newsgroup... qualcuno mi spiega come si fà a
fare un reply su un argomento utilizzando Outlook Express? spero di riuscire
ad inserire il mio algoritmo all'interno di un reply, altrimenti lo vedrete
solo soletto come messaggio isolato...

 problema:
http://www.google.com/search?q=packaging+algorithm
e' uno dei problemi piu' sviscerati

------------------------------------
NOTA: ho avuto problemi ad inviare il post poichè lo inviavo in formato
HTML... mi scuso x il ritardo e ve lo invio in formato solo testo.
------------------------------------
Ecco il migliore algoritmo che sono riuscito ad elaborare.
Notate che cerco un algoritmo con un rapporto (qualità/tempo di esecuzione)
accettabile... un tempo di esecuzione che non superi i pochi secondi per
circa 20-30 rettangoli (e badate che ho un P1 a 233MHz).
L'algoritmo non è esattamente così: ci sono alcune ottimizzazioni (ad
esempio riguardo i vettori e il sistema di riconoscimento dei rettangoli già
posizionati), ma l'importante è che capiate come colloca le immagini.
DATI:
vector<RECT>  data;       // contenente le dimensioni dei rettangoli nei
membri right e bottom (cui mi riferirò come width e height)
vector<RECT*> unused;  // contenente i puntatori ai rettangoli ancora non
posizionati
vector<RECT*> used;      // contenente i puntatori ai rettangoli già
posizionati
RECT               maxrect; // utilizzato per tenere traccia del rettangolo
di area massima ottenuto al momento
STATO INIZIALE:
data:      contiene le dimensioni inserite dall'utente
unused:  contiene data.size() puntatori, ognuno dei quali punta al
corrispettivo rettangolo di data
used:      vuoto
maxrect  = { 0, 0, 0, 0 };
ESECUZIONE:
- calcola la media aritmetica di tutte le width e di tutte le height, e
ricerca il rettangolo (o l'unione di più rettangoli) le cui dimensioni più
si avvicinano a questi valori
- colloca il rettangolo trovato nel punto (0,0) impostando i suoi valori
left e top
- rimuovi il puntatore al rettangolo trovato dalla lista unused ed
inseriscilo nella lista used
- maxrect = rettangolo trovato
while (unused.size()>0) {
- cerca all'interno di unused il rettangolo (o la somma di rettangoli) la
cui width si avvicini il più possibile a maxrect.width
- cerca all'interno di unused il rettangolo (o la somma di rettangoli) la
cui height si avvicini il più possibile a maxrect.height
- se il primo rettangolo trovato si avvicina a maxrect.width più di quanto
il secondo si avvicini a maxrect.height, considera il primo rettangolo,
altrimenti considera il secondo
- colloca il rettangolo considerato a sinistra (primo caso) o sotto (secondo
caso) il rettangolo maxrect
- elimina il puntatore a questo rettangolo dalla lista unused e inseriscilo
in used
- fra tutti i rettangoli presenti in used, ricerca il valore di left+width
(ovvero right) più grande; stesso dicasi per i valori di top+height (ovvero
bottom): questi valori costituiranno le nuove dimensioni di maxrect
}
FINE
Qui avevo inserito un immagine che poteva chiarirvi le idee... ma non la
riesco ad inviare.
Potete reperirla all'indirizzo 
http://digilander.iol.it/agquartof/rects.gif
.
COMMENTO ALL'IMMAGINE
I rettangoli sono numerati secondo l'ordine in cui sono stati inseriti. I
rettangoli 6a 6b e 6c sono un esempio di come una somma di rettangoli possa
sostituirsi ad un rettangolo singolo, purchè non vi siano grosse differenze
nella seconda dimensione (in questo caso la height).
L'algoritmo cerca sempre di costruire rettangoli che sprechino la minore
area possibile, tuttavia non tiene conto del numero dei rettangoli: infatti
se fosse esistito un rettangolo 7 di dimensioni simili al rettangolo 1, si
sarebbe sprecato un sacco di spazio. In pratica, questo algoritmo è ottimo
all'inizio ma molto inefficace nella sua fase finale.
CONCLUDO
Questo è il meglio che sono riuscito a fare, a parte considerare TUTTE le
diverse possibili disposizioni dei rettangoli e poi considerare la migliore:
funziona sicuramente bene ma è troppo laborioso (e denota una certa mancanza
di stile)... tuttavia non ho mai effettuato una prova in questo senso,
quindi può darsi che i tempi di elaborazione siano più brevi di quanto mi
sembrino...
Sono aperto ad ogni soluzione, anche la più fantasiosa, purchè si mantenga
il senso del limite (non mi và di scomodare reti neurali o altri tipi di
intelligenze artificiali per un problema così banale!)... ricordate quanto
ho detto riguardo lo spirito del mio post: non voglio una soluzione veloce
per un mio problema pratico, ma bensì aprire una discussione su un algoritmo
che mi è sembrato una sfida interessante, e che un giorno potrebbe servire a
ciascuno di voi...

Porca paletta! E io che mi dicevo "Forse ho esagerato a chiamare il post
<Algoritmo (quasi) impossibile>!"...
Beh in effetti avevo esagerato, ma nell'ottimismo... Altro che cambiare il
termine "impossibile"! Qui si tratta di eliminare il termine "(quasi)"!!!!
A questo punto non so se sia il caso di continuare a discutere sul
problema... cmq ringrazio Paolo x i links e chiunque altro si sia
interessato al mio post per il suo impegno...
Tnx&Byez

Gente, purtroppo questo è un problema NP!!!
Tnx cmq x la collaborazione... ho ricevuto molte e-mail xsonali.

 wrote in message
news:Ne%O8.22967$
j65.5...@twister1.libero.it
Ciao volevo sapere se è possibile ruotare i rettangoli?
Fammi sapere!
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG