Platz zufällige nicht-überlappende Rechtecke auf einem panel

Habe ich ein panel der Größe X von Y. ich möchte bis zu N Rechtecke der Größe nach dem Zufallsprinzip, auf das panel, aber ich glaube nicht, dass keiner von Ihnen überlappen. Ich muss wissen, die X -, Y-Positionen für diese Rechtecke.

Algorithmus, anyone?

Bearbeiten: Alle N Rechtecke sind bekannt, von Anfang an und können in beliebiger Reihenfolge gewählt werden. Ändert das die Vorgehensweise?

InformationsquelleAutor Scott Evernden | 2009-04-04
  1. 16

    Können Sie dieses Modell durch eine Reihe von "freien" Rechtecke, beginnend mit einzelnen mit den Koordinaten 0,0, size (x, y). Jedes mal, wenn Sie brauchen, um eine weitere hinzuzufügen Rechteck, wählen Sie eine der verbleibenden "frei" - Rechtecke, generieren neue Rechteck (mit der oberen linken Koordinate und die Größe, so dass es vollständig enthalten) und teilen das Rechteck ebenso wie jede andere überlappende "frei" Rechteck", so dass Kinder express verbleibenden freien Speicherplatz. Das Ergebnis 0 zu 4 neue Rechtecke (0, wenn neue Rechteck war genau die Größe des alten free-Rechteck; 4, wenn es in der Mitte und so weiter). Im Laufe der Zeit werden Sie mehr und mehr kleinere und kleinere freie Bereiche, also Rechtecke, die Sie erstellen, wird kleiner sein als gut.

    Ok, nicht sehr aufwändige Erklärung, es ist einfacher zu zeigen, auf die whiteboard. Aber das Modell ist die, die ich für die Suche nach Ausgangspunkt für die neu cut ' N ' eingefügt gui-Komponenten; es ist leicht den überblick zu behalten verfügbaren chunks-Bildschirm, und wählen Sie (zum Beispiel) die linke oder die obersten solcher Bereich.

    • Ich umgesetzt und es funktioniert wirklich gut. Ich habe auch das Zusammenführen der freien Rechtecke zu vermeiden, das kleinere problem.
    • wie hast du das Zusammenführen der freien Rechtecke? Ich kann es optisch sehr leicht, aber nicht wissen, wo Sie anfangen, es zu tun algorithmisch.
    • für jede freie Rechteck, gehen Sie über alle anderen freien Rechtecke. Überprüfen Sie, ob Ihre Links, Breite gleich sind und wenn der Boden eine gleich der Oberseite des anderen - Wenn alle wahr sind, das heißt, wir haben zwei freie Rechtecke eines über dem anderen. Erstellen Sie ein neues Rechteck, das enthält diese beiden Rechtecke mit der gleichen Breite, aber mit der kombinierten Höhe der vorhandenen zwei. Entfernen Sie die alten Rechtecke aus der Liste und fügen Sie neue neue statt.
    InformationsquelleAutor StaxMan
  2. 5

    Hier ist eine anständige Artikel über die 2d-packing-algorithmen: http://www.devx.com/dotnet/Article/36005

    Im Allgemeinen werden Sie wollen eine Art von Algorithmus, Heuristiken zu erreichen gute Ergebnisse. Eine einfache (aber nicht optimale) Lösung wäre der first fit Algorithmus.

    • Leider ist dieser Artikel scheint offline zu sein, gibt es ein 404. Wenn jemand weiß, wie zu finden ein update, bitte editieren Sie die Antwort!
    InformationsquelleAutor Jeremy Stanley
  3. 3

    Habe ich dieses Rechteck-Packing-Algorithmus in einer meiner Anwendungen, erhältlich als C# - Quellcode-Dateien.

    Der Algorithmus wird initialisiert mit der Größe der Platte, dann wird Sie Durchlaufen alle Rechtecke und erhalten Ihre position. Die Reihenfolge der Rechtecke kann das Ergebnis beeinflussen, je nach packer.

    InformationsquelleAutor devio
  4. 0

    Ich würde Ihnen raten, zu verwenden StaxMans Vorschlag.

    Hier meine 2c:

    Fügen Sie eine ganze Menge von Rechtecken nach dem Zufallsprinzip (überlappen).
    löschen überlappende Rechtecke:

    for rectangle in list of rectangles:
    if rectangle not deleted:
        delete all rectangles touching rectangle.

    finden Sie alle Rechtecke berühren eines bestimmten Rechtecks, die Sie verwenden können, ein quad-Baum oder Ungleichheiten aufgrund von x1,y1 x2,y2-Werte.

    Edit: In der Tat, die meisten game-engines wie pygame etc gehören Kollisionserkennung von Rechtecken, die ist ein häufiges problem.

    InformationsquelleAutor robert king
  5. -5

    Oder pflegen Sie eine Liste von Rechtecken, die bereits Hinzugefügt, und erstellen Sie einen Algorithmus, der herausfindet, wo das neue Rechteck basierend auf dieser Liste. Sie können erstellen Sie eine grundlegende Rechteck-Klasse zu halten die Informationen über Ihre Rechtecke.

    Sollte nicht so schwer zum erstellen eines benutzerdefinierten Algorithmus.

    • jedes mal, wenn jemand sagt, "sollte nicht so schwer sein", sollten Sie zeigen-code.
    InformationsquelleAutor Cyril Gupta
Schreibe einen Kommentar