Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Object Positioning Algorithm

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!

like image 942
Chris Avatar asked Nov 25 '09 20:11

Chris


2 Answers

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.

like image 119
Anna Avatar answered Nov 03 '22 03:11

Anna


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.

like image 30
Larry OBrien Avatar answered Nov 03 '22 04:11

Larry OBrien