Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Salve ragazzi,
Stavolta sono io a chiedere dei consigli o pareri sul da farsi.
Credo che avere più consigli da diversi fronti che provare a fare tutto da soli sia meglio.
Quello che sto cercando di fare ù un algoritmo di packing.
Ma non il solito e classico algoritmo. quello è abbastanza semplice da realizzare e ci sono in giro
diversi sorgenti al riguardo.
Ma quello che cerco di fare io è un tantino diverso.
Si tratta di sfruttare al meglio possibile l'area di lavoro per avere meno scarto possibile.
Uno dei miglior prodotti in circolazione è Optima ( Ma costa anche 10.000€ )
Cosa fà in pratica?
Guardate esempio la prima parte in alto in a sinistra, ha dei ricavi bianci sopra e a destra.
Ciò significa che quei ricavi bianchi sono scarti quindi materiale inutilizzabile.
Ma sotto se vedete, ha attaccato due rettangoli senza scarto.
Quello che fà in pratica e accostare più quadrati / rettangoli possibili e in casi estremi, aggiungere gli scarti laterlamente.
Unica regola da rispettare, e il taglio verticale o orizzontale.
Non può fermarsi creando una sorta di Zig-zag ma deve essere una linea retta per tutta l'area.
ora che sia in orizzontale o in verticale l'importante è dover allineare tutti i rettangoli in modo da ottenere un taglio verticale o orizzontale netto.
come esempio in quest'altra screen
se notate bene, ogni porzione è ritagliata da un'unica retta
Un classico bin-packing non va bene, e non funzionerebbe al mio caso perché il bin packing fa in modo di accostare rettangoli e quadrati senza badare alla retta obbligatoria che a me serve.
Avevo pensanto di agire in questo modo.
Codice sorgente - presumibilmente C++
//area globale ^m2
int area_w =3210;
int area_h =2400;
struct data
{
int w;//larghezza
int h;//altezza
int qta;//quantità
}
List<data> Data =new List<data>();
Poniamo caso di aggiungere alcuni elementi
Codice sorgente - presumibilmente Plain Text
Data.Add(new data() { w = 1400, h = 320, qta = 1}); //misure invertite H al posto di W
Data.Add(new data() { w = 370, h = 1750, qta = 1}); //misura normale
Data.Add(new data() { w = 470, h = 135, qta = 1}); //normale
Fatto questo, da qui in poi sto pensando a come potrei agire.
Ovvero, prendere la misura più grande disponibile e poi via via sempre a quella più piccola tipo
Codice sorgente - presumibilmente C# / VB.NET
//Primo risultato
var res = Data.OrderBy( x => x.w).Reverse();
facendo così ottengo la lista dalla largheza piu largha a stringere via via.
Il problema ora è appunto come potrei posizionarli?
ho dato ovviamente a tutti i rect X e Y = 0 non sapendo dove piazziarli.
Escludo a priori il processo per-pixel (calcolo o verifica per pixel )
Estremamente lento già con il paking su 320 x 240 pixel figuramoci su 3200 x 2400
Consigli su come potrei agire?
So che è abbastanza complicato da ricreare un qualcosa genere.
Non pretendo di fare lo stesso algoritmo, ma avviciniarmi per un uso privato.
Ultima modifica effettuata da Thejuster il 21/02/2023 alle 16:40
Mi fai vedere come disporresti a mano e in modo corretto i tre rettangoli dati nell'area data?
In allegato jpg con i rettangoli affiancati e riscalati /10. La puoi modificare con Photoshop per farmi vedere come dovrebbero essere disposti, serve per definire delle regole.
I rettangoli neri, sono lo scarto ovvero spazio che deve esserci, perché come spiegato prima,
l'unica regola e che deve esserci una retta obbligatoria per tutto il perimetro che divide l'area da scarto / recupero
da quella utilizzata.
Quindi se quegli spazi sono vuoti, il programma dovra aggiungere dei rettangoli per riempire l'area vacante (detti scarti)
Te l'ho segnata in rossa la retta per farti capire.
Ovviamente il programma può ruotare i rettangoli per cercare di creare meno scarto possibile.
L'unica cosa che mi viene in mente e quella di prendere come partenza la larghezza o altezza più grande.
Ma ovviamente esistono diverse soluzioni.
uhm..
Magari, si potrebbe creare una sorta punteggio.
Del tipo in questa soluzione c'è uno scarto di 35 int, l'altra di 130 int.
Quindi la soluzione di 35 int è la migliore, e conserva quello schema.
Quel programma nella screen, fà diversi cicli e diverse ottimizzazioni.
Mostrando all'utente quale secondo lui è la migliore.
Ho tirato giu giusto un esempio iniziale che è quello che dovrebbe fare.
Penso che devo rendere il void Posizioni1 di tipo ciclo
magari inserendo label e goto o quant'altro.
Hai postato mentre scrivevo, ora leggo, non so se la richiesta qui sotto è ancora valida.
Ok. però nelle tue foto i rettangoli più grandi hanno il lato lungo uguale, mentre nella tua proposta no: 1400 e 1750
Nella foto allegata i tre rettangoli dati, i tagli continui in verticale o orizzontale si possono ottenere ma non contemporaneamente!!!
Per l'approcio da usare ancora non mi sono fatto un'idea perché non ho chiari i vincoli.
Però usare più algoritmi e poi misurare l'area con sperco minore mi sembra perseguibile.
Ok cerco di spiegare basandomi sulle screen e scrivendoci sopra
Basandomi sui tuoi esempi il programma dovrebbe correggere in questo modo
Correggere in che senso,
Nel senso di aggiungere rettangoli vuoti per fare in modo da creare una singola retta completa per tutta l'avanzata del taglio
come puoi ben notare, in tutte e quattro sezioni di esempi c'è una retta rossa che parte dall'alto fino alla fine.
ora che esca in orizzontale o in verticale l'importante è poter separare tutto correttamente.
le dimensioni che vedi come esempio che ho scritto, sono riferite in millimetri ovvero
1840 equivale a 1 metro e 84 cm
475 = 47 centimetri e mezzo.
per accostare gli elementi, avevo fatto un piccolo esperimento.
ovvero:
Ho due pezzi di quale
1 = 1840 x 470 ( A )
1 = 1750 X 370 ( B )
avevo fatto
differenza = A.Larghezza - B.Larghezza;
A [ X , Y ] = 0 , 0;
A seguire
B [ X, Y ] = differenza + B.Larghezza , A.Y;
e così via....
dovrebbe essere più o meno un ciclo che ho pensato per accostare lateralmente i pezzi verso destra
così da creare una retta dall'alto verso il basso.
Il codice di esempio che avevo scritto sopra mi ha dato un risultato così
https://i.ibb.co/rkJ0cGW/test.png ho aggiunto semplicemente 2 misure.
Ho fatto un'altro tentativo mentre avevo 5 min di pausa
per ottenere questo
Diciamo che come secondo tentativo potrebbe pure passare come inizio.
Ma in seguito serve un modo per ruotare i pezzi è provare a metterli sotto per recuperare
più spazio sprecato possibile.
Lo spazio sprecato è di colore marrone.
Ho usato questo primo algoritmo di prova
Codice sorgente - presumibilmente C#
/// <summary>
/// Questo algoritmo parte posizionando elementi da
/// Sinistra verso destra e poi andando in basso
/// </summary>
void Pass1()
{
bool under_add = false;//bool per sapere se l'algoritmo ha aggiunto un pezzo in basso
Nono magari un void di tipo Pass2() che potrebbe spostare gli elementi in basso
ed allinearli in modo da recuperare più materiale
In questo esempio fatto a mano,
ho spostato i vari elementi per togliere un pezzo da destra, ruotarlo in basso
e recuperare un bel pò di materiale in altezza facendo piccoli scarti inutili
Tipo nella screen allegata, avrò del tipo come ricavo a destra dello schermo una 40 di centimetri.
spostando quel pezzo in basso e ruotandolo, ne recupero 80 a destra,
poi ovviamente bisognerebbe calcolare la quantità di scarto ma è giusto per fare un esempio