Joel Verhagen

a computer programming blog

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


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


Say... you wanna try it out? Check out the source code below and build it.


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