How to stack rectangles without changing their X positions?

2
votes

I have set of rectangles ( QGraphicsRectItem in QGraphicsScene ) whose X positions are fixed and Y positions can be modified. I want to stack these rectangles if there is any overlapping. The positions of rectangles can be changed dynamically by moving/resizing those rectangles and each time it has to optimize the space such that there is no gaps. The important constraint is that , when we move a specific rectangle it has to stack the rectangles without modifying the X position of any other rectangle.

I have a simple brute force algorithm which traverse through all the rectangles and then gets the collidng rectangles , increment the Y position with some delta value for all colliding rectangles.

Any optimal solution for this problem?

2
c++algorithmqt
Changed dynamically? Is some Tetris-like game? – Matt Phillips
No. It's not like tetris. Imagine each rectangle has a time range. So when I move/resize a specific rectangle it's time range can change , say new width of the rectangle will be from 5 seconds to 10 seconds. Now without touching the time range for other overlapping rectangle it has to stack and optimize the space. There is a timescale and each rectangles are drawn under the timescale, with varying width but fixed height. – RP.

2 Answers

1
votes

You have to assign each rectangle to a level, so that on a given level, no two rectangles overlap. Correct? So allocate an array of levels, leaving room for the worst-case scenario of each level containing only one rectangle:

std::vector<int> LevelFreeAt (nRectangles) ;

As you traverse your list of rectangles, LevelFreeAt[i] will contain the time at which level i becomes free. Now for each rectangle, in order of starting time, simply assign it to the first level that is free at its starting time, and update that level's LevelFreeAt entry accordingly.

1
votes

you could sort the rectangles by Y-Position (minimum y-position). Then you go through the list. The first one will be taken as is, the second in the list has to check if it overlaps with the previous one. If it does, adjust Y-Position to not overlap with the previous one and proceed. Do this for every rectangle in the list. After this, they do not overlap.

Restriction: it does not work if some rectangles are completely inside other rectangles (y-coordinate wise).