Algorithm to layout rectangle windows in 2D display

Question

I'm seeking for an algorithm to layout rectangle windows, the requirements are like below:

1. All windows to be layout can be seen as small rectangles.
2. All windows must be layout in a rectangle 2D display, and the display width and height is given.
3. There are several dozen windows to be layout. Each window has an initial position (x,y) and size (width, height)
4. The layout algorithm will try to separate the windows to avoid overlapping in windows, so that it is easier for the user to see all the windows

5. A global constraint (max_x_offset, max_y_offset) is given so that the relocated new position of each window (new_x, new_y) satisfied the constraint:

   abs(new_x - x) <= max_x_offset and abs(new_y - y) <= max_y_offset
   

6. The global constraint is a hard constraint, which means if there is no such layout can satisfy both 4 and 5, we must satisfy the global constraint and let some window overlap.

7. The algorithm may not get the best possible results, but it should run fast. We're going to use this algorithm in a real-time rendering application

I searched google and wikipedia and some research papers, but still failed to find a suitable algorithm for this task. Any suggestions? Thanks!

Update: Yes I understand this is a 2-D knapsack problem and it is NP-hard. What I want is a fast algorithm to get a good-enough result.

Answer 1

• Here's one
• Better one

Answer 2

You could create a physics-like model, in which windows repel each other, with a force that depends on the distance between them. In each time step, enforce your absolute position constraint. If you don't find an overlap-free solution within a certain number of time steps, abort the algorithm and give the candidate solution found at this point.

Of course, this won't always find a solution if one exists. But I think, in general, that is very hard or even impossible to do efficiently.