Object Positioning Algorithm

Question

I'm wondering if there is an "optimal" solution for this problem:

I have a n x m (pixel) sized space with p preexisting rectangled - objects in various sizes on it. Now I want to place q (same sized) new objects in this space without any overlapping.

The algorithm I came up with:

1. Create array A[][] with the size [(n)/(size_of_object_from_q)]x[(n)/(size_of_object_from_q)]

2. Iterate all Elements from p and for each:

   mark all fields in A[][] as occupied, where the element "lies"

3. Place all elements from q in the according places where the fields in A[][] are not marked

(Boy, I hope I could make that understandable...)

Is there any better way to do this? Any help would really be appreciated!

Answer 1

I know this isn't a specific answer to your question, but it may be useful to research and/or dig into the graphviz source code. graphviz offers a number of layout models, including neato, which attempts to minimize a global energy function.

Wikipedia has some pseudo-code for force-base algorithms.

Answer 2

If I understand the question, it sounds like you are looking for an "optimal" bin packing algorithm (aka the Knapsack Problem). That's an NP-Complete problem, although your description sounds like you can probably brute-force your way to an optimal solution.

Answer 3

From a brief search in the internet, it seems that optimal rectangle packing is an NP-hard problem. I would guess that smart people in the academia found some approximation algorithms for that, so it is an option for googling.

But I would try to make the simple method work first:

1. Divide your objects into sizes according to their width
2. Try placing them line-by-line from the largest to the smallest.

My guess is that in many cases this naive solution will work.