5
$\begingroup$

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

  • 0
    This is definitely box packing, which is NP-complete. It's a problem that chip designers tackle daily. If the count of pictures is small enough, you may be able to find a solution. IIRC this is generally handled using Integer Linear Programming. In those cases however, the rectangles are fixed in size. Resizeable rectangles will complicate things.2013-05-02

1 Answers 1

1

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.

  • 0
    Sorry. I guess I got sidetracked. I'd be interesting in getting the answer there and relaying in non-research level terms here.2011-08-17