Joel Verhagen

a computer programming blog

Jim Scott's Packing Algorithm in C++ and SFML

Description

I recently stumbled across a fun little programming problem called the 2D bin packing problem (a subset of the larger Packing Problem). Basically the idea is that you have a rectangular 2D "bin" in which you can store smaller rectangles. The programmer's job is to fit those smaller rectangles into the larger rectangles in the most efficient way possible.

Quite a bit of work has been done on the subject (as evident by the Wikipedia page about the packing problem). One approach I really like is Jim Scott's algorithm. It uses a binary tree structure to keep track of open spots to put incoming rectangles. He doesn't provide any working code for the algorithm (his description is in pseudocode).

Another guy, Iván Montes, wrote an implementation of Jim Scott's algorithm in JavaScript. Very cool! Since I have been playing with SFML recently, I thought it would be cool to write an implementation of the algorithm in C++.

Download

Say... you wanna try it out? First, you'll need to download and install the Microsoft Visual C++ 2010 Redistributable Package (download link). After you have that installed, all you need to do is download and extract the program itself.

Click the link below to download the .zip file containing the program.

2D Bin Packing 1.0

Source

I have set up a GitHub repository for the code, if you're interested. If you don't want to bother with the source code, take a look at a screenshot below:

2D bin packing preview image