CODEWITHSUNDEEP
algorithm
user899205
user899205

Reputation:

An algorithm to arrange random sized squares on a surface?

The question is really simple, i have an array of random sized squares (width, height) and a fixed width surface. What's the best efficient algorithm to arrange squares on this surface? There must be no useless gap between squares. Is it possible at all? Without using AI or heavy processing?

Something similar to this picture, but assume that my surface is not bounded at bottom, its a fixed-width and unbounded height surface.

Upvotes: 2

Views: 1832

Answers (3)

Branimir
Branimir

Reputation: 4367

This type of optimization problems are known as Linear programming (linear optimization). The bad news is it's complex.

Take a look at Simplex algorithm algebraic method, there are more general numeric methods, search for interior point methods.

There are free libraries like: LP_SOLVE

Upvotes: 0

npinti
npinti

Reputation: 52185

For such thing you could either use a variation of the Bin Packing Problem, where you try to pack as many squares as possible in your sheet or else use the (what probably seems more appropriate) Cutting Stock Algorithm.

Note however, that in both cases, it is highly unlikely that you will have no gaps between your squares.

Upvotes: 0

Ben Ruijl
Ben Ruijl

Reputation: 5123

This problem is called 2d bin packing. Here's a way to tackle it:

http://codeincomplete.com/posts/2011/5/7/bin_packing/

Upvotes: 6

Related Questions