Kachel (skalierbarer Stapelalgorithmus)
Hier ist das Problem. Ich habe eine rechteckige Leinwand, die eine Größe von 1 hat. Also habe ich ein Koordinatensystem von (0,0 ... 1,0 - x und 0,0 ... 1,0 - y).
Ich habe auch ein paar Kacheln. Fliesen sind auch Rechtecke. Sie haben unterschiedliche Größe und Anzahl der Kacheln ist eine Variable.
Ich möchte Kacheln im rechteckigen Zeichenbereich von 0,0 bis 1,0 stapeln ( von links nach rechts, von oben nach unten ):
1) Kacheln müssen in Canvas passen (aber so viel Platz wie möglich)
2) Kacheln müssen skaliert werden (wenn sie nicht passen), sollte jede Kachel um den gleichen Betrag skaliert werden (sie müssen die gleichen Proportionen haben).
3) stelle dir vor, dass du diese "Fliesen" in deiner Hand hast und sie nacheinander in diese Leinwand legst
4) es mag fast "TreeMap-Algorithmus" aber - die Form der Kacheln muss identisch sein ( Rechtecke ) und muss ich nicht füllen Der gesamte Bereich der Zeichenfläche
Gibt es jemanden, der mir einen Algorithmus in einer C-ähnlichen Sprache (C, C ++, Java, C #) zeigen kann?
* Ich habe es versucht.
1) ich berechnete Fläche der Kachel, dann berechne ich eine Summe der Kachelflächen (zum Beispiel: ich habe zwei Kacheln, eine haben Fläche von 2, andere Fläche von 1, sie ist meine ich habe Gesamtsumme von 3)
2) Dann berechne ich, welche "Proportion" jede Kachel in "Gesamtsumme der Flächen" hat (zum Beispiel: 2/3 und 1/3)
3) berechne dann die Größe der Rechteckkachel mit Math.sqrt (x) (zum Beispiel: Math.sqrt (2/3))
4) dann ziehe eine Kachel einzeln ...
Aber das geht nicht immer. Manchmal bekomme ich Fliesen aus Leinwand. *
5 Antworten
Wie andere gezeigt haben - die Problembeschreibung ist nicht sehr klar. Aber ich gehe davon aus, dass Sie jede Kachel beliebig skalieren können (zumindest zeigen Ihre Beispiele, dass Kachel-Skalierung möglich ist). Also wird meine Lösung einfach sein (aber vielleicht nicht das, was Sie wollen oder nicht optimal):
- Skaliere jede Kachel um den Faktor:
EDGEspace / (EDGEtile * N ½)
- Platziere jede Kachel in der aktuellen Reihe, wenn die Kachel die Raumgrenzen überschreitet - gehe zur nächsten Reihe.
Hier ist N das nächste perfekte Quadrat , das größer oder gleich der Gesamtanzahl der Kacheln ist.
ps. Wenn Sie einen Abstand zwischen den Kacheln benötigen, machen Sie den obigen Skalierungsfaktor etwas kleiner.
Ich hoffe, das hilft.
Es scheint, dass dies ein Verpackungsproblem ist, wenn wir versuchen, dieses Problem genau so zu lösen, wie es beschrieben wurde. Mit anderen Worten, es gibt keine Lösung, weil es in einer Frage, wie sie beschrieben wird, kein Problem gibt. Wenn wir NUR EINE Kiste und einen festen Satz von Kacheln haben und die Anforderung, dass ALLE in die Kiste passen müssen, gibt es keinen Platz für die Optimierung. Ich kann mehrere verwandte Optimierungsprobleme sehen:
1. Bei einem festen Satz von Fliesen, die in Schachteln gleicher oder unterschiedlicher Größe verpackt werden müssen, wird eine optimale Verpackungsreihenfolge gefunden, so dass eine minimale Anzahl von Schachteln verwendet wird.
2. Bei gegebener Einzelbox einer beliebigen Größe und einem Satz von Kacheln wird ein optimaler (maximaler) Satz von Kacheln gefunden, die in eine Kiste passen.
3. Mit einer Kiste und einer Reihe von Kacheln beantworten Sie die Frage, ob es möglich ist, sie in eine Kiste zu packen oder nicht.
Welche von diesen versuchen Sie zu lösen?
Die Art und Weise, wie das Problem jetzt gestellt wird, ist bedeutungslos, denn egal, in welcher Reihenfolge Sie die Kacheln in die Kiste legen, sie benutzen immer den gleichen Platz, egal wie sie angeordnet sind, sobald sie alle zusammenpassen.
Ich glaube nicht, dass dies ein (bin) -Packungsproblem ist, weil ich einen für das 1D-Bin-Packing-Problem geschrieben habe. Ich denke, dass das Problem hier durch das 2D-Schneidstoffproblem gelöst wird, vielleicht gibt es auch eine 2D-Behälterverpackung. Was Sie wollen, ist das knappsack-Problem zu versuchen. Dieses Problem ist schwer zu lösen (NP) und es gibt keine Lösung. Es ist ein bisschen wie das Travelsalesman-Problem, bei dem die Anzahl der Lösungen exponentiell zur Anzahl der Städte ist. Wenn Sie die Komplexität zu einem 1D-Problem reduzieren können, können Sie meinen bin-Packing-Algorithmus auf phpclasses.org versuchen.
Tags und Links algorithm rectangles tiles