17

I have a collection of different sized squares and rectangles that I want to fit together using PHP into one large square/rectangle. The squares are usually images that I want to make into a montage - but sometimes they are simply math objects.

Are there any PHP algorithms for this and what is this type of thing called?

Update: After more searching I think what I want is called the bin packing problem. However, I would also like to add a certain amount of randomization for certain types of packing problems (like images) to allow human interest.

Fabio
  • 18,856
  • 9
  • 82
  • 114
Xeoncross
  • 55,620
  • 80
  • 262
  • 364
  • Are these objects fixed in size... i.e. You want to find the range of images that will fit into a defined "box". Or are you wanting to scale these images (retaining aspect) into a pre-defined box? – diagonalbatman Jul 13 '11 at 16:06
  • I'd actually settle for either. However, I am more interested in them fitting together well than the final matrix being a certain size. – Xeoncross Jul 13 '11 at 16:07
  • 1
    I think this question is very close to what I need: http://stackoverflow.com/questions/4904049/php-array-performance – Xeoncross Jul 13 '11 at 16:25
  • I found something in [JavaScript](http://codeincomplete.com/posts/2011/5/7/bin_packing/example/) so I'm looking to see if I can understand it and convert some of it. – Xeoncross Jul 13 '11 at 16:36
  • 4
    There are algorithms, and there are implementations of these algorithms for specific languages, like PHP. I suggest making this question language-agnostic because it's QI (quite interesting). – Karoly Horvath Jul 13 '11 at 20:25
  • 3
    There's always [math.stackexchange.com](http://math.stackexchange.com/) to get some mathemagicians into it. Apparently they have ben talking about this for a while as well: [math.stackexchange.com search for the bin packing problem](http://math.stackexchange.com/search?q=bin+packing+problem) – Andresch Serj Jul 15 '11 at 10:45
  • 1
    Look to the garment industry where fitting oddly sized pattern pieces optimally on yardage of cloth is a priority, plus the lumber industry who fit cuts into logs. – Patrick Hughes Jul 16 '11 at 02:45
  • In Java, there's [Drools Planner](http://www.jboss.org/drools/drools-planner): maybe you can port some of the construction heuristics (first fit decreasing, best fit decreasing, ...) and metaheuristics (tabu search, simulated annealing) to PHP (as it's open source under ASL license). – Geoffrey De Smet Jul 17 '11 at 15:06
  • @Geoffrey: I already did 1d-bin-packing in php but not open source. You can download it at phpclasses.org (bin-packing). – Micromega Jul 18 '11 at 02:09
  • It seems to me like you want to recreate Mac OS X's show-all-windows feature, Exposé. Am I not understanding your problem correctly? – Pops Sep 21 '11 at 05:21
  • @LordTorgamus, I'm not sure, but that feature sounds very close. – Xeoncross Sep 21 '11 at 19:48

3 Answers3

9

2D Bin packing is NP-hard problem. There are however approximation algorithms.

Look at this code (and explanation). It contains multiple algorithms and there is a GUI:

Solving the 2D Packing Problem

Petar Ivanov
  • 91,536
  • 11
  • 82
  • 95
  • 5
    Sorry for the -1 but the linked site requires you register and login to view it, which isnt normally a problem but they require address.. company, company size.. ect. Shouldnt have to provide that for an answer. – Loktar Aug 05 '11 at 16:58
0

I have a wrote a 1d bin-packing algorithm in php. You want to look for best-fit, first-fit, and so on. But it's not for a 2d problem, maybe you want to look for the knapsack-problem?

Micromega
  • 12,486
  • 7
  • 35
  • 72
  • I found a [PHP-version of the knapsack-problem](http://rosettacode.org/wiki/Knapsack_problem/0-1#PHP), but I'm not sure how it relates to a 2D area to fill yet. – Xeoncross Jul 15 '11 at 20:17
  • @Xeon: At least you have an algorithm with 2 variables, weight and cost. Maybe you can modify it? Another app is drools-planer. – Micromega Jul 15 '11 at 20:46
  • The problem is that formula uses only one constraint and one priority. So it's just a glorified 1D algorithm. I need something that handles 2 constraints (with an optional priority). – Xeoncross Jul 15 '11 at 23:18
  • @Xeon: I see, did you tried a Floyd-Warshall algorithm or Edmond's maximum matching algorithm? – Micromega Jul 15 '11 at 23:25
  • @Xeon: Maybe a spatial-index or a quadtree? A si reduces the 2d complexity to a 1d complexity. – Micromega Jul 15 '11 at 23:35
  • @Xeon: You want to look into Nick's spatial index quadtree hilbert curve blog. – Micromega Jul 16 '11 at 00:02
0

I think you can use Semulated Annealing algorithm. I have used it to fill rectangular newspaper pages by rectangular advertisements. As you said you can start it by randomized solution and then you can slowly reach to a good solution. See here http://codetuner.blogspot.com/2010/03/simulated-annealing-approach-to.html. I have used it to solve pagination problem. I think you can use it for you r requirement too.

Jayantha Lal Sirisena
  • 21,216
  • 11
  • 71
  • 92