incise.org: 2D bin packing with javascript and <canvas>

This is a demonstration of a 2D bin packing algorithm, operating on a continuously randomly-generated set of rectangles. Credit for this algorithm goes to Jim Scott. I don't think he invented it, but he made it easy to understand. Read his page to learn how it works.

I don't claim this to be any sort of optimal implementation. Ideally, you would have a pre-generated set of rectangles you want to pack into a certain area. You could then pre-sort them in different ways to find more efficient packing arrangements. There are also completely different algorithms for accomplishing this task. This is merely one. Bin packing is an NP-hard problem, meaning that the only way to find the best result is to try every possible combination in a brute force manner, which becomes computationally impractical or impossible when you have many items to pack together. Thus, algorithms like this one merely achieve an acceptable balance between packing efficiency and computation speed.

Fork it on github!

Speed: fastest faster slower

Piece size: bigger smaller smallest

% full ( pixels to go)

Next piece:



comments


Nick Welch <nick@incise.org> · github · twitter