C# / VB.NET - Aiuto su algoritmo

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?

optimaiberica.es/wp-content/gallery/opty-way/…


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

optimaiberica.es/wp-content/uploads/2015/09/…


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.

//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

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

//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.

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.

Per farti capire più o meno,
La tua immagine di 3 rettangoli il programma li dovrebbe disporre piu o meno così

i.ibb.co/1ZSQzYP/…

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.

Oppure un altro esempio potrebbe essere

i.ibb.co/TmdJGfL/…

o quest'altro

i.ibb.co/7g1B2zZ/…

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.

Da qui si vede meglio

optima.it/wp-content/uploads/2020/10/…


Quello che mi sconsola è proprio questo

( - More than 90 algorithms for best optimization result )

Carlo se vuoi fare qualche prova ho tirato giu qualcosa tanto per iniziare

Aggiungo misure temporanee

struct data
        {
            public int pezzi;
            public int Larghezza;
            public int Altezza;
        }

        List<data> rect = new List<data>();

        //Area di Lavoro
        int area_w = 3210;
        int area_h = 2400;

        List<Rectangle> ordPerH = new List<Rectangle>(); //ordinamento per H Decrescente
        List<Rectangle> ordPerL = new List<Rectangle>(); //ordinamento per L Decrescente
        List<Tuple<int, int, int>> percorso = new List<Tuple<int, int, int>>(); //Schema da seguire
        List<Rectangle> posizioni = new List<Rectangle>();

 private void Form1_Load(object sender, EventArgs e)
        {
            dataGridView1.Rows.Add(1, 1840, 547, "test");
            dataGridView1.Rows.Add(1, 1647, 473, "test");
            dataGridView1.Rows.Add(1, 1753, 567, "test");
            dataGridView1.Rows.Add(1, 1753, 483, "test");
            dataGridView1.Rows.Add(2, 1275, 370, "test");
        }


  private void button1_Click(object sender, EventArgs e)
        {
            //Aggiungo gli elementi alla lista
            for (int i = 0; i < dataGridView1.RowCount; i++)
            {
                data d = new data();
                d.pezzi = Convert.ToInt16(dataGridView1.Rows[i].Cells[0].Value);
                d.Altezza = Convert.ToInt16(dataGridView1.Rows[i].Cells[1].Value);
                d.Larghezza = Convert.ToInt16(dataGridView1.Rows[i].Cells[2].Value);
                rect.Add(d);
            }


            Ordina();
            Posizioni1();


            stampa();
        }



void Ordina()
        {
                       
            var s = rect.OrderBy( x => x.Larghezza).Reverse();

            //Ordinamento per Larghezza
            for (int i = 0; i < s.ToList().Count; i++)
            {

                for (int j = 0; j < s.ToList()[i].pezzi; j++)
                {
                    ordPerL.Add(new Rectangle(0, 0, s.ToList()[i].Larghezza, s.ToList()[i].Altezza));
                }
            }
        

            //ordinamento per Altezza
             s = rect.OrderBy(x => x.Altezza).Reverse();
            for (int i = 0; i < s.ToList().Count; i++)
            {

                for (int j = 0; j < s.ToList()[i].pezzi; j++)
                {
                    ordPerH.Add(new Rectangle(0, 0, s.ToList()[i].Larghezza, s.ToList()[i].Altezza));
                }
            }

     
        }



 //Calcolo per posizioni1
        void Posizioni1()
        {
            //prendo la Larghezza maggiore disponibile nella lista ordinata
            var attuale = ordPerL[0];
            ordPerL.RemoveAt(0); //rimuovo l'elemento preso

            posizioni.Add(attuale);

            
            //Provo a recuperare tutti gli altri pezzi con la medesima larghezza o minore a quella attuale
            var list = ordPerL.Where(x => x.Width <= attuale.Width).ToList();

            //Dalla variabile list, prendo sempre il primo elemento, e controllo se posso inserirlo sotto
            //se rientra nell'area di lavoro
            if (list[0].Height <= area_h)
            {
                //Se non supera i margini aggiungo il pezzo allineandolo verso destra, rimanendo uno scarto verso il bordo esterno.
                Rectangle temp = list[0]; //prendo il pezzo temporaneo
                int diff = attuale.Width - temp.Width; //Differenza delle misure in larghezza

                //MessageBox.Show(diff.ToString());

                posizioni.Add(new Rectangle(diff, attuale.Height, temp.Width, temp.Height));
                ordPerL.Remove(temp);
                
            }


        }




void stampa()
        {

            int w = area_w;
            int h = area_h;

            Bitmap b = new Bitmap(w, h);
            Graphics g = Graphics.FromImage(b);

            for (int i = 0; i < posizioni.Count; i++)
            {
                g.FillRectangle(Brushes.CornflowerBlue, posizioni[i]);
                g.DrawRectangle(Pens.Red, posizioni[i]);
            }

            pictureBox1.SizeMode = PictureBoxSizeMode.CenterImage;
            pictureBox1.Image = b;
            b.Save("test.png");

        }

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ì
i.ibb.co/rkJ0cGW/…
ho aggiunto semplicemente 2 misure.

Ok capito.
Il risultato del tuo esempio in C# l'avevo visto facendo girare il tuo codice.

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

/// <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

            //Recupero primo elemento
            var attuale = ordPerL.FirstOrDefault();

            ordPerL.Remove(attuale); //Rimuovo l'elemento recuperato

            //Aggiungo alle posizioni finali l'elemento
            posizioni.Add(new Rectangle(work_x, work_y, attuale.Width, attuale.Height));



            //-- verifica in basso
            var next = ordPerL.FirstOrDefault();

            //Verifico se il prossimo elemento non è più grande dell'area
            //di lavoro
            if(attuale.Height + next.Height < area_h)
            {
                //Se il pezzo rientra, cerco di accostarlo verso destra in modo
                //da realizzare sempre una retta verticale
                int diff = attuale.Width - next.Width;

                posizioni.Add(new Rectangle(work_x + diff, work_y + attuale.Height, next.Width, next.Height));

                //aggiunto il pezzo
                ordPerL.Remove(next); //rimuovo quello aggiunto nelle posizioni

                under_add = true;
            }


            //Se il pezzo non può essere aggiunto sotto
            if(!under_add)
            {
                //Segno come scarto
                scarti.Add(new Rectangle(work_x, work_y + attuale.Height, attuale.Width, attuale.Height));

            }

            //Aggiorno la posizione di lavoro su X
            //All'ultimo pezzo recuperato
            work_x = work_x + attuale.Width;
            work_y = 0;

            if (ordPerL.Count > 0)
                Pass1();

        }

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

i.ibb.co/SPJHT3D/…

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