Esiste un sorgente/lib di C++ per risolvere l'imballaggio bidimensionale con bidone rettangolare (non quadrato) e rotazione?

Question

Come dice il titolo già ho bisogno di C/C++ codice sorgente o di una libreria che posso usare per risolvere il problema bin packing con forme rettangolari 2D in cui il bidone è anche rettangolare e rettangoli sono inoltre in fase di ruotare di angoli di 90 ° per adattarsi meglio . Ho già tutti i valori richiesti, quindi non ho bisogno di un algoritmo di imballaggio online.

ho trovato solo un lib che si occupa di un contenitore quadrato e senza rotazione, che in realtà non è abbastanza efficace per le mie esigenze.

Vorrei davvero apprezzare qualsiasi cosa C/C++ gestire un bidone rettangolare e la rotazione.

Grazie.

PS: il tempo richiesto per il calcolo non è importante, solo il risultato è.

PPS: Deve essere C o C++, e non ho trovato nulla di utile StackOverflow ricerca ...

Answer 1

http://clb.demon.fi/files/RectangleBinPack.pdf è la chiave. Quello è il riferimento su imballaggio bidimensionale.

Potresti essere in grado di modificare uno degli algoritmi presenti per soddisfare le tue necessità. Dubito che la rotazione sia necessaria, gli algoritmi sono abbastanza avanzati così come sono.

Questa (https://github.com/Lalaland/PixelPacker/blob/master/src/algoMaxRects.cpp) è un esempio di come implementare l'algoritmo MaxRects.

La modifica si sarebbe probabilmente dovuto fare è in cima dell'algoritmo, quando si seleziona il rettangolo accanto ad utilizzare. Basta guardarlo anche al diverso orientamento dei rettangoli e scorrere l'intera lista.

Answer 2

ho trovato questa discussione qualche settimana fa, dopo aver scremato la lettura del PDF nella risposta, e giocando con il codice autori, ho fatto una ri-scrittura che più adatta alle mie esigenze (tessitura atlante imballaggio)

Se qualcun altro è interessato ... https://github.com/chris-stones/BinPack2D

• Permette all'utente di riunire una struttura di dati con i rettangoli presentate (orig nome del file, ecc)
• confezione multipla bidoni (per 2d serie Atlas texture - GL_EXT_texture_array)

Inoltre, invece di tracciare scissione e unirsi rettangoli liberi, a monitorare e angoli superiori sinistro sorta liberi. Ho trovato molto più semplice da implementare, con risultati ugualmente buoni.

Non c'è documentazione, vedere ExampleProgram() nella parte superiore del file di intestazione.