Auslegen von sich überlappenden Rechtecken

Question

Ich versuche, eine Reihe von überlappenden Rechtecken zu layouten, die wie folgt beginnen:

Alt-Text http://img690.imageshack.us/img690/209/picture1bp.png

Der 2-Pass-Algorithmus, den ich mir ausgedacht habe, ist ungefähr so:

// 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;
   }
}

Dies führt (wahrscheinlich) dazu, dass die Rechtecke wie folgt angeordnet sind: Alt-Text http://img685.imageshack.us/img685/9963/picture2bc.png

Das ist ästhetisch nicht sehr ansprechend, also dachte ich an einen zweiten Durchgang, bei dem ich sie alle nach links verschieben würde, wobei ich wieder mit dem obersten Punkt beginnen würde:

// 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;
        }
    }
}

Ich denke, das sollte am Ende so aussehen wie unten (sieht in der Praxis genau richtig aus):

Alt-Text http://img511.imageshack.us/img511/7059/picture3za.png

Ich stehe diesem Algorithmus jedoch skeptisch gegenüber, da ich nicht sicher bin, ob er in allen Fällen korrekt funktioniert und möglicherweise sehr langsam ist. Glauben Sie, dass dieser Algorithmus funktionieren kann? Können Sie Vorschläge für einen besseren Algorithmus machen?

Answer 1

Ich denke, dass dieses Problem polynomial komplex ist. Wenn man davon ausgeht, dass die in Ihrem Beispiel genannte Einschränkung, dass sich nur zwei Rechtecke an einem bestimmten Punkt überlappen, keine echte Einschränkung des Problems ist, müssten Sie jede mögliche Reihenfolge der Überlappung der Rechtecke nach rechts ausprobieren, um das optimale (am wenigsten breite) Ergebnis zu erzielen. Dies ist eine Form des Platzfüllungsproblems, und die sind schwer zu lösen, es sei denn, Ihr Datensatz ist klein genug für Brute-Force.

Eine kleine Verbesserung Ihres Pseudocodes ist jedoch möglich, die die Leistung in vielen Fällen verbessern würde.

Betrachten Sie das gewünschte Endergebnis:

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

(wobei alle vier Zeichen eines Zeichens ein einziges Rechteck bilden)

Im ersten Durchgang würde alles außer A nach rechts verschoben, so dass eine Treppe entsteht. Im zweiten Durchlauf würde Ihr Code es dann ablehnen, B an den linken Rand zu verschieben, da der erste Versuch, es zu verschieben, sich mit E überschneiden würde. Sie müssen am linken Rand beginnen und prüfen, an welche Position ganz links Sie jedes Rechteck in Durchlauf 2 verschieben können.

Pseudocode:

// 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

Sie könnten einen physikbasierten Ansatz verwenden, bei dem die Blöcke starre Körper sind und nach links fallen:

Nein, das würde nicht immer das beste Ergebnis liefern, aber nachdem ich Ihren Screencast gesehen habe, denke ich, dass es sehr intuitiv in einem interaktiven Programm zu verwenden wäre und es könnte geeignet sein :)