¿Existe una fuente/lib de C++ para resolver el bin bin 2D con un contenedor rectangular (no cuadrado) y rotación?

Question

Como el título ya dice Necesito C/C++ código fuente o una biblioteca que puedo utilizar para resolver el problema Bin Packing con formas rectangulares 2D donde el contenedor también es rectangular y los rectángulos también se rotan en ángulos de 90 ° para adaptarse mejor . Ya tengo todos los valores requeridos, así que no necesito ningún algoritmo de empaquetado en línea.

Solo encontré una lib que trata con un contenedor cuadrado y sin rotación que no es lo suficientemente eficiente para mis necesidades.

Realmente apreciaría cualquier cosa C/C++ que maneje una bandeja rectangular y la rotación.

Gracias.

PD: El tiempo requerido para el cálculo no es importante, solo el resultado es.

PPS: Tiene que ser C o C++, y no se encontró nada útil stackoverflow búsqueda ...

Answer 1

http://clb.demon.fi/files/RectangleBinPack.pdf es clave. Eso es la referencia en 2d bin packing.

Es posible que pueda modificar uno de los algoritmos para satisfacer sus necesidades. Dudo que se necesite la rotación, los algoritmos están bastante avanzados como están.

Esto (https://github.com/Lalaland/PixelPacker/blob/master/src/algoMaxRects.cpp) es un ejemplo de cómo implementar el algoritmo MaxRects.

La modificación que probablemente tendría que hacer es en la parte superior del algoritmo, al seleccionar el siguiente rectángulo para usar. Simplemente tenga también que ver la diferente orientación de los rectángulos junto con el ciclismo a través de toda la lista.

Answer 2

yo encontramos este hilo hace unas semanas, después descremada leer el PDF en la respuesta, y jugando un poco con el código autores, hice una re-escribir la que más se adapte a mis necesidades (textura de embalaje Atlas)

Si alguien más está interesado ... https://github.com/chris-stones/BinPack2D

• permite al usuario distribuir una estructura de datos con rectángulos presentados (nombre de archivo, etc) orig
• paquete de múltiples compartimientos (para 2d gama Atlas textura - GL_EXT_texture_array)

Además, en vez de rastrear y unir rectángulos libres, rastreo y ordeno las esquinas superiores libres de la izquierda. Me pareció mucho más fácil de implementar, con resultados igualmente buenos.

No hay documentación, consulte ExampleProgram() en la parte superior del archivo de encabezado.