How is 2D bin packing achieved programmatically?

by

I Googled “bin packing code” and this was my first hit: http://codeincomplete.com/posts/2011/5/7/bin_packing/

Here’s a summary: build a binary tree. Each branch in the tree contains a sprite. Each leaf node represents available space. Initially the tree has just the root node, which represents all available space. To add a sprite to the tree, search the tree for an unoccupied (leaf) node big enough to hold the sprite. Turn that node from a leaf into a branch by setting the sprite as the node’s occupant and giving the node two children. One child represents the remaining space to the right of the sprite; the other represents the remaining space below the sprite and the first child.

The article I linked above explains this much more fully, with diagrams and JavaScript code. It also explains how to dynamically grow the sprite sheet rather than choosing a fixed size in advance.

More Related Contents:

  1. How can I programmatically determine how to fit smaller boxes into a larger package? [closed]
  2. 3 dimensional bin packing algorithms
  3. What does O(log n) mean exactly?
  4. How do I search for a number in a 2d array sorted left to right and top to bottom?
  5. Generate an integer that is not among four billion given ones
  6. Why doesn’t Dijkstra’s algorithm work for negative weight edges?
  7. How to generate Sudoku boards with unique solutions
  8. Time complexity of Euclid’s Algorithm
  9. Quick sort Worst case
  10. How to round floats to integers while preserving their sum?
  11. Modulus power of big numbers
  12. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  13. Fast algorithm implementation to sort very small list
  14. Compute social distance between two users
  15. Efficient algorithm for ordering different types of objects
  16. How to find two most distant points?
  17. Smooth spectrum for Mandelbrot Set rendering
  18. Algorithm to find two repeated numbers in an array, without sorting
  19. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  20. How to split a string into words. Ex: “stringintowords” -> “String Into Words”?
  21. Determining if two line segments intersect? [duplicate]
  22. Mesh generation from points with x, y and z coordinates
  23. How to find distance from the latitude and longitude of two locations?
  24. Algorithm for sampling without replacement?
  25. Randomly choosing from a list with weighted probabilities
  26. Planar Graph Layouts
  27. Round to the nearest power of two
  28. Draw equidistant points on a spiral
  29. How to apply binary search O(log n) on a sorted linked list?
  30. Why is Insertion sort better than Quick sort for small list of elements?

Leave a Comment