Algorithm for fitting objects in a space

Question

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.

Petrarch

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? – Tanberg

I'd actually settle for either. However, I am more interested in them fitting together well than the final matrix being a certain size. – Petrarch

I think this question is very close to what I need: https://mcmap.net/q/212632/-php-array-performance – Petrarch

I found something in JavaScript so I'm looking to see if I can understand it and convert some of it. – Petrarch

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). – Descartes

There's always 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 – Bela

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. – Frequentative

In Java, there's 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). – Otho

@Geoffrey: I already did 1d-bin-packing in php but not open source. You can download it at phpclasses.org (bin-packing). – Kerguelen

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? – Moslemism

@LordTorgamus, I'm not sure, but that feature sounds very close. – Petrarch

Answer 1

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

Hoopes

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. – Grimm

Answer 2

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?

Kerguelen

I found a PHP-version of the knapsack-problem, but I'm not sure how it relates to a 2D area to fill yet. – Petrarch

@Xeon: At least you have an algorithm with 2 variables, weight and cost. Maybe you can modify it? Another app is drools-planer. – Kerguelen

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). – Petrarch

@Xeon: I see, did you tried a Floyd-Warshall algorithm or Edmond's maximum matching algorithm? – Kerguelen

@Xeon: Maybe a spatial-index or a quadtree? A si reduces the 2d complexity to a 1d complexity. – Kerguelen

@Xeon: You want to look into Nick's spatial index quadtree hilbert curve blog. – Kerguelen

Answer 3

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.

Panhellenic