CODEWITHSUNDEEP
algorithmmathlanguage-agnosticcluster-analysisbin-packing
Xeoncross
Xeoncross

Reputation: 57244

Algorithm for fitting objects in a space

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.

Upvotes: 17

Views: 7921

Answers (3)

Jayantha Lal Sirisena
Jayantha Lal Sirisena

Reputation: 21376

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.

Upvotes: 0

Petar Ivanov
Petar Ivanov

Reputation: 93050

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

Upvotes: 9

Cybercartel
Cybercartel

Reputation: 12592

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?

Upvotes: 0

Related Questions