Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C# / VB.NET - Aiuto su algoritmo
Forum - C# / VB.NET - Aiuto su algoritmo

Pagine: [ 1 2 ] Precedente | Prossimo
Avatar
Thejuster (Admin)
Guru^2


Messaggi: 2281
Iscritto: 04/05/2008

Segnala al moderatore
Postato alle 16:33
Martedì, 21/02/2023
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€ :asd: )
Cosa fà in pratica?

https://optimaiberica.es/wp-content/gallery/opty-way/opty-w ...


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

https://optimaiberica.es/wp-content/uploads/2015/09/line-ma ...


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

  1. //area globale  ^m2
  2. int area_w = 3210;
  3. int area_h = 2400;
  4.  
  5. struct data
  6. {
  7.     int w; //larghezza
  8.    int h; //altezza
  9.    int qta; //quantità
  10. }
  11.  
  12.  
  13. List<data> Data = new List<data>();



Poniamo caso di aggiungere alcuni elementi


Codice sorgente - presumibilmente Plain Text

  1. Data.Add(new data() { w = 1400, h = 320, qta = 1}); //misure invertite H al posto di W
  2. Data.Add(new data() { w = 370, h = 1750, qta = 1}); //misura normale
  3. 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

  1. //Primo risultato
  2. 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


https://mire.forumfree.it/ - Mire Engine
C# UI Designer
PM Quote
Avatar
Carlo (Member)
Guru


Messaggi: 1257
Iscritto: 29/01/2018

Segnala al moderatore
Postato alle 23:59
Martedì, 21/02/2023
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.


Carlo ha allegato un file: affiancati.jpg (5233 bytes)
Clicca qui per guardare l'immagine

Ultima modifica effettuata da Carlo il 22/02/2023 alle 0:15


in programmazione tutto è permesso
PM Quote
Avatar
Thejuster (Admin)
Guru^2


Messaggi: 2281
Iscritto: 04/05/2008

Segnala al moderatore
Postato alle 1:34
Mercoledì, 22/02/2023
Per farti capire più o meno,
La tua immagine di 3 rettangoli il programma li dovrebbe disporre piu o meno così

https://i.ibb.co/1ZSQzYP/image.png

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

https://i.ibb.co/TmdJGfL/image.png

o quest'altro

https://i.ibb.co/7g1B2zZ/image.png

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

https://www.optima.it/wp-content/uploads/2020/10/edit-way01 ...


Quello che mi sconsola è proprio questo :rotfl:

( - More than 90 algorithms for best optimization result )



Ultima modifica effettuata da Thejuster il 22/02/2023 alle 10:51


https://mire.forumfree.it/ - Mire Engine
C# UI Designer
PM Quote
Avatar
Thejuster (Admin)
Guru^2


Messaggi: 2281
Iscritto: 04/05/2008

Segnala al moderatore
Postato alle 12:40
Mercoledì, 22/02/2023
Carlo se vuoi fare qualche prova ho tirato giu qualcosa tanto per iniziare

Aggiungo misure temporanee

Codice sorgente - presumibilmente C++

  1. struct data
  2.         {
  3.             public int pezzi;
  4.             public int Larghezza;
  5.             public int Altezza;
  6.         }
  7.  
  8.         List<data> rect = new List<data>();
  9.  
  10.         //Area di Lavoro
  11.         int area_w = 3210;
  12.         int area_h = 2400;
  13.  
  14.         List<Rectangle> ordPerH = new List<Rectangle>(); //ordinamento per H Decrescente
  15.         List<Rectangle> ordPerL = new List<Rectangle>(); //ordinamento per L Decrescente
  16.         List<Tuple<int, int, int>> percorso = new List<Tuple<int, int, int>>(); //Schema da seguire
  17.         List<Rectangle> posizioni = new List<Rectangle>();
  18.  
  19.  private void Form1_Load(object sender, EventArgs e)
  20.         {
  21.             dataGridView1.Rows.Add(1, 1840, 547, "test");
  22.             dataGridView1.Rows.Add(1, 1647, 473, "test");
  23.             dataGridView1.Rows.Add(1, 1753, 567, "test");
  24.             dataGridView1.Rows.Add(1, 1753, 483, "test");
  25.             dataGridView1.Rows.Add(2, 1275, 370, "test");
  26.         }
  27.  
  28.  
  29.   private void button1_Click(object sender, EventArgs e)
  30.         {
  31.             //Aggiungo gli elementi alla lista
  32.             for (int i = 0; i < dataGridView1.RowCount; i++)
  33.             {
  34.                 data d = new data();
  35.                 d.pezzi = Convert.ToInt16(dataGridView1.Rows[i].Cells[0].Value);
  36.                 d.Altezza = Convert.ToInt16(dataGridView1.Rows[i].Cells[1].Value);
  37.                 d.Larghezza = Convert.ToInt16(dataGridView1.Rows[i].Cells[2].Value);
  38.                 rect.Add(d);
  39.             }
  40.  
  41.  
  42.             Ordina();
  43.             Posizioni1();
  44.  
  45.  
  46.             stampa();
  47.         }
  48.  
  49.  
  50.  
  51. void Ordina()
  52.         {
  53.                        
  54.             var s = rect.OrderBy( x => x.Larghezza).Reverse();
  55.  
  56.             //Ordinamento per Larghezza
  57.             for (int i = 0; i < s.ToList().Count; i++)
  58.             {
  59.  
  60.                 for (int j = 0; j < s.ToList()[i].pezzi; j++)
  61.                 {
  62.                     ordPerL.Add(new Rectangle(0, 0, s.ToList()[i].Larghezza, s.ToList()[i].Altezza));
  63.                 }
  64.             }
  65.        
  66.  
  67.             //ordinamento per Altezza
  68.              s = rect.OrderBy(x => x.Altezza).Reverse();
  69.             for (int i = 0; i < s.ToList().Count; i++)
  70.             {
  71.  
  72.                 for (int j = 0; j < s.ToList()[i].pezzi; j++)
  73.                 {
  74.                     ordPerH.Add(new Rectangle(0, 0, s.ToList()[i].Larghezza, s.ToList()[i].Altezza));
  75.                 }
  76.             }
  77.  
  78.      
  79.         }
  80.  
  81.  
  82.  
  83.  //Calcolo per posizioni1
  84.         void Posizioni1()
  85.         {
  86.             //prendo la Larghezza maggiore disponibile nella lista ordinata
  87.             var attuale = ordPerL[0];
  88.             ordPerL.RemoveAt(0); //rimuovo l'elemento preso
  89.  
  90.             posizioni.Add(attuale);
  91.  
  92.            
  93.             //Provo a recuperare tutti gli altri pezzi con la medesima larghezza o minore a quella attuale
  94.             var list = ordPerL.Where(x => x.Width <= attuale.Width).ToList();
  95.  
  96.             //Dalla variabile list, prendo sempre il primo elemento, e controllo se posso inserirlo sotto
  97.             //se rientra nell'area di lavoro
  98.             if (list[0].Height <= area_h)
  99.             {
  100.                 //Se non supera i margini aggiungo il pezzo allineandolo verso destra, rimanendo uno scarto verso il bordo esterno.
  101.                 Rectangle temp = list[0]; //prendo il pezzo temporaneo
  102.                 int diff = attuale.Width - temp.Width; //Differenza delle misure in larghezza
  103.  
  104.                 //MessageBox.Show(diff.ToString());
  105.  
  106.                 posizioni.Add(new Rectangle(diff, attuale.Height, temp.Width, temp.Height));
  107.                 ordPerL.Remove(temp);
  108.                
  109.             }
  110.  
  111.  
  112.         }
  113.  
  114.  
  115.  
  116.  
  117. void stampa()
  118.         {
  119.  
  120.             int w = area_w;
  121.             int h = area_h;
  122.  
  123.             Bitmap b = new Bitmap(w, h);
  124.             Graphics g = Graphics.FromImage(b);
  125.  
  126.             for (int i = 0; i < posizioni.Count; i++)
  127.             {
  128.                 g.FillRectangle(Brushes.CornflowerBlue, posizioni[i]);
  129.                 g.DrawRectangle(Pens.Red, posizioni[i]);
  130.             }
  131.  
  132.             pictureBox1.SizeMode = PictureBoxSizeMode.CenterImage;
  133.             pictureBox1.Image = b;
  134.             b.Save("test.png");
  135.  
  136.         }




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.


https://mire.forumfree.it/ - Mire Engine
C# UI Designer
PM Quote
Avatar
Carlo (Member)
Guru


Messaggi: 1257
Iscritto: 29/01/2018

Segnala al moderatore
Postato alle 12:53
Mercoledì, 22/02/2023
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.


Carlo ha allegato un file: posizioni esempi.jpg (53680 bytes)
Clicca qui per guardare l'immagine

Ultima modifica effettuata da Carlo il 22/02/2023 alle 12:57


in programmazione tutto è permesso
PM Quote
Avatar
Thejuster (Admin)
Guru^2


Messaggi: 2281
Iscritto: 04/05/2008

Segnala al moderatore
Postato alle 15:18
Mercoledì, 22/02/2023
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.


Thejuster ha allegato un file: immagine.png (69920 bytes)
Clicca qui per guardare l'immagine

Ultima modifica effettuata da Thejuster il 22/02/2023 alle 15:21


https://mire.forumfree.it/ - Mire Engine
C# UI Designer
PM Quote
Avatar
Carlo (Member)
Guru


Messaggi: 1257
Iscritto: 29/01/2018

Segnala al moderatore
Postato alle 20:00
Mercoledì, 22/02/2023
Ok capito.
Il risultato del tuo esempio in C# l'avevo visto facendo girare il tuo codice.


in programmazione tutto è permesso
PM Quote
Avatar
Thejuster (Admin)
Guru^2


Messaggi: 2281
Iscritto: 04/05/2008

Segnala al moderatore
Postato alle 22:36
Mercoledì, 22/02/2023
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#

  1. /// <summary>
  2.         /// Questo algoritmo parte posizionando elementi da
  3.         /// Sinistra verso destra e poi andando in basso
  4.         /// </summary>
  5.         void Pass1()
  6.         {
  7.             bool under_add = false; //bool per sapere se l'algoritmo ha aggiunto un pezzo in basso
  8.  
  9.             //Recupero primo elemento
  10.             var attuale = ordPerL.FirstOrDefault();
  11.  
  12.             ordPerL.Remove(attuale); //Rimuovo l'elemento recuperato
  13.  
  14.             //Aggiungo alle posizioni finali l'elemento
  15.             posizioni.Add(new Rectangle(work_x, work_y, attuale.Width, attuale.Height));
  16.  
  17.  
  18.  
  19.             //-- verifica in basso
  20.             var next = ordPerL.FirstOrDefault();
  21.  
  22.             //Verifico se il prossimo elemento non è più grande dell'area
  23.             //di lavoro
  24.             if(attuale.Height + next.Height < area_h)
  25.             {
  26.                 //Se il pezzo rientra, cerco di accostarlo verso destra in modo
  27.                 //da realizzare sempre una retta verticale
  28.                 int diff = attuale.Width - next.Width;
  29.  
  30.                 posizioni.Add(new Rectangle(work_x + diff, work_y + attuale.Height, next.Width, next.Height));
  31.  
  32.                 //aggiunto il pezzo
  33.                 ordPerL.Remove(next); //rimuovo quello aggiunto nelle posizioni
  34.  
  35.                 under_add = true;
  36.             }
  37.  
  38.  
  39.             //Se il pezzo non può essere aggiunto sotto
  40.             if(!under_add)
  41.             {
  42.                 //Segno come scarto
  43.                 scarti.Add(new Rectangle(work_x, work_y + attuale.Height, attuale.Width, attuale.Height));
  44.  
  45.             }
  46.  
  47.             //Aggiorno la posizione di lavoro su X
  48.             //All'ultimo pezzo recuperato
  49.             work_x = work_x + attuale.Width;
  50.             work_y = 0;
  51.  
  52.             if (ordPerL.Count > 0)
  53.                 Pass1();
  54.  
  55.         }



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

https://i.ibb.co/SPJHT3D/test.png

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


Thejuster ha allegato un file: Cattura.JPG (41227 bytes)
Clicca qui per guardare l'immagine

Ultima modifica effettuata da Thejuster il 22/02/2023 alle 22:47


https://mire.forumfree.it/ - Mire Engine
C# UI Designer
PM Quote
Avatar
Thejuster (Admin)
Guru^2


Messaggi: 2281
Iscritto: 04/05/2008

Segnala al moderatore
Postato alle 15:30
Venerdì, 24/02/2023
Dunque facendo un po' di ricerche sembra che la situazione non sia delle più semplici.

Per iniziare serve un algoritmo di nesting.

Un po' simile alla mia soluzione, ma va implementato con ulteriori passaggi e movimenti.

Penso di strutture il tutto con classi e metodi.
Vediamo cosa tiro fuori.



https://mire.forumfree.it/ - Mire Engine
C# UI Designer
PM Quote
Pagine: [ 1 2 ] Precedente | Prossimo