This project implements the Steinberg algorithm for solving the strip packing problem in Python. (see A. Steinberg, 1997) We also provide two heuristics: ''removing gaps'' and ''dropping hanging rectangles''. See documentation and examples.
Clone the repository and install the dependencies:
git clone https://github.com/yzdxdydz/strip-packing.git
cd strip-packing
pip install -r requirements.txt
To execute the packing algorithm, follow these steps:
- Import the
SteinbergPacking
class from thesrc/steinberg
module.
from src.steinberg import SteinbergPacking
- Create an instance of the
SteinbergPacking
class with the desired parameters. For example for original algorithm.
sp = SteinbergPacking(width=10, without_gaps=False, drop_hanging_element=False)
- Call the
get_packing
method, passing in the list of elements to be packed.
elements = [[1, 1], [1, 1], [10, 8], [3, 1], [9, 1], [2, 1], [1, 1], [3, 1]]
#Optimal height H_opt = 10 can be provided with the packing
# [9, 9], [8, 9], [0, 0], [5, 9], [0, 8], [3, 9], [9, 8], [0, 9].
sp.get_packing(elements)
- Calculate the height, plot the packing and save it to file.
from random import randint
colors = []
for _ in elements:
colors.append('#%06X' % randint(0, 0xFFFFFF))
sp.plot_packing(colors, "figure-1.png")
print("Height: ", sp.max_height())
sp = SteinbergPacking(width=10, without_gaps=True, drop_hanging_element=False)
sp.get_packing(elements)
sp.plot_packing(colors, "figure-2.png")
print("Height: ", sp.max_height())
sp = SteinbergPacking(width=10, without_gaps=True, drop_hanging_element=True)
sp.get_packing(elements)
sp.plot_packing(colors, "figure-3.png")
print("Height: ", sp.max_height())
For detailed information on the algorithm, please refer to the documentation strip-packing.pdf