выложив перекрывающиеся прямоугольники

Question

Я пытаюсь макет кучи перекрывающихся прямоугольников, которые начинаются вот так:

alt text http://img690.imageshack.us/img690/209/picture1bp.png

2-проход алгоритма я придумал также грубо:

// Pass 1 - Move all rectangles to the right until they do not overlap any other rectangles 
rects = getRectsSortedOnTopLeft(); // topmost first, all rects same size 
foreach(rect in rects) 
{ 
    while(rect.collidingRects().size() != 0) 
    { 
     rect.x += RECT_SIZE; 
    } 
} 

Это (вероятно) заканчивается прямоугольниками, выложенными как: alt text http://img685.imageshack.us/img685/9963/picture2bc.png

Это не эстетично, поэтому Я подумал о втором проходе которые движутся бы их все еще раз налево, начиная с самого верхнего:

// Pass 2 
foreach(rect in rects) 
{ 
    while(rect.x >= LEFT_MARGIN) 
    { 
     assert(rect.collidingRects().size() == 0); 
     rect.x -= RECT_WIDTH; 
     if(rect.collidingRects().size() != 0) 
     { 
      rect.x += RECT_WIDTH; 
      break; 
     } 
    } 
} 

Я думаю, что это должно в конечном итоге выглядит, как показано ниже (выглядит точно правильно на практике):

alt text http://img511.imageshack.us/img511/7059/picture3za.png

Тем не менее, я с осторожностью отношусь к этому алгоритму, потому что не уверен, правильно ли он будет правильно отображаться во всех случаях, и он может быть очень медленным. Как вы думаете, этот алгоритм может работать? Можете ли вы сделать несколько предложений по лучшему алгоритму?

Answer 1

Я думаю, что эта проблема имеет полиномиальную сложность. Предполагая, что ограничение вашего примера только на два прямоугольника, перекрывающихся в любой заданной точке, не является истинным ограничением проблемы, вам нужно попробовать каждый возможный порядок наложения прямоугольников вправо, чтобы получить оптимальный (наименее широкий) результат. Это форма проблемы уплотнения пространства, и они жесткие, если ваш набор данных не является достаточно малым для принудительной работы.

Однако возможно небольшое улучшение вашего псевдокода, что во многих случаях улучшит его производительность.

Рассмотрим этот желаемый конечный результат:

A 
A C 
A C E 
A C E 
B C E 
B D E 
B D F 
B D F 
    D F 
    F 

(где все четыре из одного символа представляют собой единый прямоугольник)

Ваш первый проход будет двигаться все, кроме А справа, образуя лестницу. Затем во втором проходе ваш код будет отклоняться, чтобы переместить B в левое поле, потому что первая попытка его перемещения будет перекрываться с E. Что вам нужно сделать, это начать с левого поля и проверить крайнее левое положение, на которое вы можете перемещать каждый прямоугольник в проходе 2.

псевдокод:

// Pass 1 - Move all rectangles to the right until they do not overlap any other rectangles 
rects = getRectsSortedOnTopLeft(); // topmost first, all rects same width 
foreach(rect in rects) 
    while(rect.collidingRects()) 
     rect.x += RECT_WIDTH; 
// Pass 2 - Move all rectangles to the leftmost position in which they don't overlap any other rectangles 
foreach(rect in rects) 
    for(i=LEFT_MARGIN; i+=RECT_WIDTH; i<rect.x) 
    { 
     o = rect.x; 
     rect.x = i; 
     if(rect.collidingRects()) 
      rect.x = o; 
    } 

Answer 2

Вы можете использовать подход основанных на физику, где блоки являются твердыми телами падения влево:

нет, это не будет все время получается лучший результат, но, наблюдая за своим скринкастом, я думаю, что было бы очень интуитивно понятно использовать в интерактивной программе, t подходит)