Ich habe ein Panel der Größe X von Y. Ich möchte bis zu N Rechtecke mit zufälliger Größe auf diesem Panel platzieren, aber keines von ihnen soll sich überlappen . Ich muss die X, Y-Positionen für diese Rechtecke kennen.Platziere zufällige, nicht überlappende Rechtecke auf einem Panel
Algorithmus, jemand?
Bearbeiten: Alle N Rechtecke sind von Anfang an bekannt und können in beliebiger Reihenfolge ausgewählt werden. Ändert das den Ablauf?
Sie können dies durch eine Reihe von "freien" Rechtecken modellieren, beginnend mit einem einzelnen mit Koordinaten von 0,0, Größe (x, y). Jedes Mal, wenn Sie ein weiteres Rechteck hinzufügen müssen, wählen Sie eines der verbleibenden "freien" Rechtecke, generieren Sie ein neues Rechteck (mit Koordinaten oben links und Größe, so dass es vollständig enthalten ist) und teilen Sie dieses Rechteck sowie alle anderen überlappenden " frei "Rechteck, so dass Kinder verbleibenden freien Raum auszudrücken. Dies führt zu 0 bis 4 neuen Rechtecken (0, wenn das neue Rechteck genau der Größe des alten freien Rechtecks entspricht; 4, wenn es in der Mitte ist, und so weiter). Im Laufe der Zeit werden Sie immer mehr und mehr freie Bereiche bekommen, also werden Rechtecke, die Sie erstellen, auch kleiner.
Ok, keine sehr ausführliche Erklärung, es ist einfacher, auf Whiteboard zu zeigen. Aber das Modell ist eines, das ich verwendet habe, um den Startort für neu geschnittene, eingefügte GUI-Komponenten zu finden; Es ist einfach, die verfügbaren Bildschirmbereiche zu verfolgen und (zum Beispiel) den linken oder obersten Bereich auszuwählen.
Ich habe dies implementiert und es funktioniert wirklich gut.Ich habe auch das Zusammenführen der freien Rechtecke hinzugefügt, um das kleinere und kleinere Problem zu vermeiden. –
@TomerPintel, wie hast du die freien Rechtecke zusammengeführt? Ich kann es sehr leicht visuell machen, aber ich kann nicht herausfinden, wo ich anfangen soll, es algorithmisch zu tun. – dataduck
@dataduck, für jedes freie Rechteck, gehen Sie über alle anderen freien Rechtecke. Prüfen Sie, ob die Breite, die Breite und die Breite gleich sind und ob die Unterseite der einen der anderen entspricht. Wenn alle wahr sind, bedeutet dies, dass wir zwei freie Rechtecke übereinander haben. Erstellen Sie ein neues Rechteck, das beide Rechtecke mit der gleichen Breite aber mit der kombinierten Höhe der vorhandenen zwei enthält. Entfernen Sie die alten Rechtecke aus der Liste und fügen Sie stattdessen neue hinzu. –
Hier ist ein anständiger Artikel über 2d Packungsalgorithmen: http://www.devx.com/dotnet/Article/36005
Sie werden in der Regel eine Art von Algorithmus wollen Heuristik anständige Ergebnisse zu erzielen. Eine einfache (aber nicht optimale) Lösung wäre der First-Fit-Algorithmus.
Leider scheint dieser Artikel offline zu sein, es gibt einen 404 zurück. Wenn jemand weiß, wie man ein Update findet, editiere bitte die Antwort! – JBCP
Oder pflegen Sie eine Liste der bereits hinzugefügten Rechtecke und erstellen Sie einen Algorithmus, der anhand dieser Liste ermittelt, wo das neue Rechteck platziert werden soll. Sie können eine grundlegende Rectangle-Klasse erstellen, um die Informationen zu Ihren Rechtecken zu speichern.
Sollte nicht so schwierig sein, einen benutzerdefinierten Algorithmus zu erstellen.
Jedes Mal, wenn jemand sagt "sollte nicht so schwer sein", sollten sie Code zeigen. – willc2
Ich habe diese Rectangle Packing algorithm in einer meiner Anwendungen, verfügbar als C# Quelldateien.
Der Algorithmus wird mit der Größe des Panels initialisiert, dann durchlaufen Sie alle Rechtecke und erhalten ihre Position. Die Reihenfolge der Rechtecke kann abhängig vom Packer das Ergebnis beeinflussen.
Ich würde Ihnen empfehlen, StaxMans Vorschlag zu verwenden.
Hier ist meine 2c:
hinzufügen eine ganze Menge Rechtecke zufällig (einander überlappen). überlappende Rechtecke löschen:
for rectangle in list of rectangles:
if rectangle not deleted:
delete all rectangles touching rectangle.
alle Rechtecke finden ein bestimmtes Rechteck berühren, können Sie einen Quad-Baum oder Ungleichheiten auf x1 Basis verwenden, y1 x2, y2 Werte.
Bearbeiten: In der Tat enthalten die meisten Spiel-Engines wie Pygame usw. Kollisionserkennung von Rechtecken, die ein häufiges Problem ist.
http://gamedev.stackexchange.com/questions/6730/how-to-randomly-place-rectangle-inside-a-larger-bounding-rectangle-without-inter –