# Designer looking for help with an algorithm to calculate layout of rectangles based on some constraints

Let me start off telling you that I spent the better part of high-school in remedial math.

So the problem I'm looking for some help with:

I am working on designing a layout for a graphic design project where I would like to arrange a series of photographs within a frame. While I might normally approach this manually, I was wondering whether an algorithmic solution is possible to achieve the same design.

Here are the specifications:

1. The frame is a rectangle.
2. Each photograph is a rectangle
3. A border must be provided. Each photograph must be at least that distance away from the other photographs and the frame
4. $n$ number of photographs will be provided (where $n > 0$ and say, $n< 20$). The photographs will be in both landscape and portrait orientation.
5. The dimensions of the frame will be provided where the area of the frame must be at least enough to contain the provided photographs at exactly the border width away from each other and the frame.

How do I approach thinking this problem through?

Thank you in advance for your insights,

Shaheeb

-
While I'm not certain if this is the place to ask, nor what a possible answer can be; I am rather certain [general-topology] is a misuse of the tag, and I'm fairly positive the same about [algebraic-geometry]. :) – Asaf Karagila Aug 17 '11 at 2:38
@Asaf: Methinks yes, this is perfectly mathematical. The retag I did should prove attractive to those specialists... – J. M. Aug 17 '11 at 2:43
I'm not the best mathematician, but it reminds me of a tiling problem, which there are algorithms for. From the sound of things, you might even be able to provide additional information such as which pictures should be next to each other. I've found that many times getting as much information as possible (such as knowing each photo's dimensions and orientation) can greatly help. Provided that all we have are your specifications above, a general algorithm might start with placing one photo, and then searching for the best fit for the rest of the photos, one at a time. – Matt Groff Aug 17 '11 at 2:44
I remember seeing a talk speaking about such packing algorithms, it seemed to be a very complex problem to do something apparently very simple. I'd be glad to see a detailed solution if a specialist in packings happens to be around. @Asaf : I don't think the tag [general-topology] is really appropriate here. – Patrick Da Silva Aug 17 '11 at 2:54
I would take a look at this: codeproject.com/KB/web-image/rectanglepacker.aspx – Jackson Jan 14 '12 at 7:48

## 1 Answer

The problem you're dealing with is like a tiling or packing problem in computer science, and the range of thinking goes from fairly simple to as complex as one would like.

Probably the most important aspect of the problem (from a computer science standpoint) is the number of photographs in the frame. This determines the problem size, and the algorithm of choice will be based mainly on it. If there are additional specifications besides those you mentioned, they will come into play, but by far the most important aspect is the problem size, or number of photos.

For small problem sizes (like <25 photos), one can usually proceed fairly simply. A layout can be estimated, and then a search can be conducted to place the photos optimally.

For larger problem sizes, the problem becomes exponentially complex, and often times some sort of artificial intelligence or very complicated, high powered math may be needed to place the photos optimally.

-
CSTheory is intended for grad research questions. This particular question would not be well received there. – GEL Aug 17 '11 at 3:18
Sorry. I guess I got sidetracked. I'd be interesting in getting the answer there and relaying in non-research level terms here. – Matt Groff Aug 17 '11 at 3:24