3. Algorithmus um Rechtecke auf einer Fläche zu platzieren

Algorithmus um Rechtecke auf einer Fläche zu platzieren

  • L

    versuchs doch mal mit nem genetischen algorithmus. Könntest dann als mutationsmöglichkeit z.b. skalierung einiger Rechtecke eines Individuums einbauen. Müsstest dir nur ne schlaue bewertungsfunktion ausdenken (z.b. möglichst wenig unverbrauchter platz)..

    edit: hier hab ich ein beispiel für ein genetischen algorithmus für ein packproblem gefunden http://rfhs8012.fh-regensburg.de/~saj39122/vhb/NN-Script/script/gen/k040402.html

    0
  • R

    @kingruedi

    kommt es dir dabei auf schnelligkeit oder auf ein möglichst perfektes resultat an?

    rapso->greets();

    0
  • R

    rapso schrieb:

    kommt es dir dabei auf schnelligkeit oder auf ein möglichst perfektes resultat an?

    Also bei bis zu 40 Rechtecken sollte das in Echtzeit ablaufen, also weniger als 1 sec auf einem üblichen PC. Ein perfektes Ergebnis ist natürlich auch nicht schlecht.

    Aber ich hab jetzt neben expocity noch einige andere OpenSource Projekte gefunden, die Expose nachahmen: Skippy

    Ich schau mir gerade an, wie die das machen. Hier schonmal ein Kommentar aus expocity

    /* Computes a layout for the thumbnail windows and returns the total size of
 * the layout.
 * The algorithm works like this:
 * For n elements, you will have ceil(sqrt(n)) elements per line.
 * Elements are arranged in slots from left to right, top to bottom.
 * A slot can contain several elements arranged vertically, if the line still
 * has space left for additional elements.
 * The highest element in a line determines the space available for the line.
 */

    Skippy macht das noch ein bisschen anders.

    0
  • R

    Hmm, Skippy und Expocity erzeugen erst Minifenster, die dann platziert werden. Das ist nicht ganz das was Expose macht.

    Schade.

    0

  • Falls Breite/Höhe gegeben sind, ist das IMHO eine Variation des Knappsack Problems. IIRC NP hart.

    Bye, TGGC (Denken, und gut ist.)

    0
  • R

    da ich sowas für texturen öfters mal machen muss (z.b. für fonts), geh ich folgender massen vor.

    1. ich sortiere die liste der rechtecke nach der größe absteigend.
    2. das erste element der liste wird in die page eingefügt, wobei es zwei möglichkeiten gibt es einzufügen die davon abhängt ob rect->DeltaX()>rect->DeltaY() ist.

    die eine möglichkeit ist zeilenweise, die andere ist reihenweise.

    die dX>dY werden nun untereinander bis die reihe voll ist 'gestapelt' die dX<=dY werden nebeneinander bis die zeile voll ist 'gestappelt'. danach fängt man in einer neuen zeile/reihe an.

    auf diese weise hat man oft einen sehr kleinen 'verschleiss' und somit eine möglichst optimale ausnutzung.

    eine wirklich optimale ausnutzung kann man heutzutage leider nur bruteforce durchführen und das klappt oft nur bis ca <=14 elemente. (ist wie das problem des handelsreisenden ;D)

    rapso->greets();

    0
  • R

    @TGGC
    Also die Breite und die Höhe sind gegeben.

    Knappsackproblem == Rucksackproblem?

    Das hab ich mir schonmal angeguckt. Also direkt fällt mir nicht ein, wie ich es verwenden kann.

    @rapso
    so ähnlich macht das auch Skippy. Das Problem ist nur, dass ich dann am Ende da stehe und die Rechtecke skalieren muss, wenn zu wenig Platz da ist und dann fällt nacher die Skalierung zu extrem aus.

    Aber so langsam entwickel ich eine Idee.

    0
  • R

    kingruedi schrieb:

    Das Problem ist nur, dass ich dann am Ende da stehe und die Rechtecke skalieren muss, wenn zu wenig Platz da ist und dann fällt nacher die Skalierung zu extrem aus.

    Aber so langsam entwickel ich eine Idee.

    schau wieviel fläsche übrig bleibt im verhältniss zu der fläche die du unterbringen kannst und dann damit skalieren.

    rapso->greets();

    0
  • L

    rapso schrieb:

    eine wirklich optimale ausnutzung kann man heutzutage leider nur bruteforce durchführen und das klappt oft nur bis ca <=14 elemente. (ist wie das problem des handelsreisenden ;D)

    rapso->greets();

    genetische algorithmen finden zumeist optimale lösungen, sofern man den lösungsdruck nicht übertrieben hoch treibt. Da es hier aber echtzeit laufen soll, würde man wahrscheinlich auch nur eine "gute" lösung finden..

    0
  • R

    ich hab gerade eine grobe Idee entworfen und arbeite die jetzt aus:

    (A) Die Fläche wird in so viele Quadrate aufgeteilt, wie Rechtecke verteilt werden müssen.
    Jedes Quadrat entspricht einem Slot.
(B) Das Verhältniss der Fläche jedes Rechtecks zu der Fläche jedes Slots wird berechnet.
(C) Die Rechtecke werden so sortiert, dass alle Rechtecke, die in ein Slot passen in Gruppen sortiert werden, die zusammen ein Slot belegen können.
(D) Die Gruppen werden in die Slots eingefügt
(E) Die Größe der freien Fläche wird erneut berechnet und
    wenn noch Rechtecke vorhanden sind bei A angefangen.
    Außer es gab im letzten durchlauf keine neuen einsortierungen.
(F) Die übrigen Rechtecke werden auf die Slots die am ehesten passen skaliert
    0
  • L

    versteh ich net. könnteste bitte nochmal Punkt C näher erläutern?

    0
  • R

    Bei Punkt C geht es eben darum, dass du dir mehrere Rechtecke schnappst, die zusammen in ein Slot passen und diese dann in den Slot einfügst.

    Angenommen, du hast ein Slot der Größe 10x10 und zwei Rechtecke der Größe 5x10, dann passen die ja wunderbar nebeneinander in das Slot.

    (Verhältnis 1/2x1)

    Naja, das ist ja erstmal nur der Ansatz. Die einzelnen Schritte arbeite ich jetzt aus.

    0
  • L

    Also folgende probleme fallen mir auf:

    A) kann Probleme machen, da man nicht unbedingt die ganze Fläche nutzen kann, wenn man sie versucht in Quadrate mit konstanter größe aufzuteilen (z.b. wenn du 3 rechtecke hast). Insbesondere macht das Probleme, wenn du keine rechteckigen Fläche mehr hast nach dem ersten Durchlauf..

    Und C) ist auch nicht so einfach. Woher willste wissen welche rechtecke zusammengelegt werden können in 1 slot? Alle möglichkeiten ausprobieren?

    Dann kann es dir sehr leicht passieren, dass es zu keiner gruppenbildung mehr kam (nach dem ersten durchlauf wahrscheinlich schon gar nicht mehr) und damit das programm sofort zu F springt

    Bei F) werden dann alle runterskaliert, was dazu führt, dass du einerseits die super geordneten gruppen von C hast, wo praktisch keine lücken sind, und auf der anderen seiten die rechtecke, die keine gruppe gefunden habe und große abstände zu den nächsten rechtecken aufweisen. Daher haste wahrscheilich eine merkwürdige clusterbildung oo

    Außerdem vermute ich, dass höhstens 50% der rechtecke von A-E erwischt werden und daher die übrigen rechtecke einfach runterskaliert werden (und teilweise sehr stark, wenn du pech hast). Es kann dir auch passieren, dass es nur noch zu F kommt, wenn es einfach zuviele rechtecke waren und damit die eigentlich großen rechtecke nachher auch nur noch minirechtecke sind (wie alle andern)..

    0
  • ?

    wie wärst mit einer switch anweisung? je nachdem wieviel rechtecke du hast

    hier z.b. etwas "triviales" du kannst aber gerne kleine abstände nehmen als
    9,16,25,36,42

    du nimmst die momentane bildschirmauflösung z.b. 1280*1024 dann nimmst du noch was weg ( platz zw. rechtecken, die toolbar ) dann z.b. 1200*980
    sprich du nimmst momentane bildschirmauflösung von x und teilst dann durch 3,4 usw

    3x3 = 9 = ein rechteck = 400326
    4    4
    55
    6    6
    7*6 = 42 Rechtecke = ein rechteck = 171*163

    dann bringst du jedes fenster ( recheck ) in die grösse und platzierst sie auf den screen

    sprich

    anzahl =get_rechtecke();

dann die switch
case kleiner oder gleich 9
case ...
case 

in dem case fällen berechnest du dann x_neu und y_neu pro window

nachdem du das hast rufst du die fkt "make_all_windows_passend(x_neu,y_neu)" und dann "plaziere_windows()

    jetzt hast du halt grosse abstände du kannst aber auch

    12 =2
    2    2=4
    23=6
    3    3=9
    4*3=12
    usw nehmen
    dann hast du kleinere "lücken"

    was meinst du zu dem vorschlag?

    0
  • ?

    ok dass "dumme" ist
    wenn du case "1"hast sprich 2 windows und eines ist sehr gross dan andere sehr klein dann sind beide gleich gross.
    hmmm obwohl das manchmal auch nicht schlecht ist bei browser fenster z.b.

    was auch ganz nett ist ( soll ich mir die idea patentieren lassen?)

    du hast eine grosse freie fläche in der mitte und drumherunm die kleinen rechtecke. wenn man dann auf ein kleines klickt, erscheint es vergrössert in der mitte

    je nachdem wieviel rechtecke du hast hast du auch drumherum

    z.b. 2 oben 2 unten 2 rechts 2 links und das grosse in der mitte
    oder 3,3,3,3 und 1 in der mitte
    4,4,4,4 und 1 in der mitte

    ich glaub sowas gibts noch nicht, so ist halt gerade das gross und bequem zum bearbeiten was man braucht, die andern sind klein aber genug um zu sehen was es ist und ob sich was verändert hat.

    0
  • R

    life schrieb:

    A) kann Probleme machen, da man nicht unbedingt die ganze Fläche nutzen kann, wenn man sie versucht in Quadrate mit konstanter größe aufzuteilen (z.b. wenn du 3 rechtecke hast). Insbesondere macht das Probleme, wenn du keine rechteckigen Fläche mehr hast nach dem ersten Durchlauf..

    ja, die weiteren durchläufe werden problematisch. In dem Paper zu dem MaSTaH einen Link gepostet hat, wird ein ähnliches Problem mittels eines Staircase-Modells gelöst. Das werd ich mir nochmal angucken. Die Konstruktion sollte relativ leicht verlaufen, da man ja einfach Zeilenweise von Oben alles abdeckt und sieht, wie viel Platz eine Zeile noch bis zum Flächenrand hat.

    Und C) ist auch nicht so einfach. Woher willste wissen welche rechtecke zusammengelegt werden können in 1 slot? Alle möglichkeiten ausprobieren?

    einfach schauen, in welchem Verhältniss die Länge oder Breite zur Slot Länge oder Breite passen und wenn dann Verhältniss_Breite0+Verhältniss_Breite1<=1 und Verhältniss_Höhe0+Verhältniss_Höhe1<=1 ist, dann passen die in eine Gruppe.

    Dann kann es dir sehr leicht passieren, dass es zu keiner gruppenbildung mehr kam (nach dem ersten durchlauf wahrscheinlich schon gar nicht mehr) und damit das programm sofort zu F springt

    Bei F) werden dann alle runterskaliert, was dazu führt, dass du einerseits die super geordneten gruppen von C hast, wo praktisch keine lücken sind, und auf der anderen seiten die rechtecke, die keine gruppe gefunden habe und große abstände zu den nächsten rechtecken aufweisen. Daher haste wahrscheilich eine merkwürdige clusterbildung oo

    Außerdem vermute ich, dass höhstens 50% der rechtecke von A-E erwischt werden und daher die übrigen rechtecke einfach runterskaliert werden (und teilweise sehr stark, wenn du pech hast). Es kann dir auch passieren, dass es nur noch zu F kommt, wenn es einfach zuviele rechtecke waren und damit die eigentlich großen rechtecke nachher auch nur noch minirechtecke sind (wie alle andern)..

    Ich hoffe mal, dass mir bei der Verteilung das Staircase-Modell zur Hilfe kommt.

    0
  • R

    @newkid
    Dein Algorithmus ist so wie ich das sehe erstmal nur ein Teilschritt von meinem Algorithmus.

    0
  • L

    einfach schauen, in welchem Verhältniss die Länge oder Breite zur Slot Länge oder Breite passen und wenn dann Verhältniss_Breite0+Verhältniss_Breite1<=1 und [richtig: oder] Verhältniss_Höhe0+Verhältniss_Höhe1<=1 ist, dann passen die in eine Gruppe.

    dann haste aber immer nur maximal 2 in einer gruppe. Könnt ja auch sein, dass gleich 10 in eine gruppe passen würden 😉

    0
  • R

    Das war ja nur ein Beispiel. Dafür sollte es aber Algorithmen geben, um Flächen ideal füllen zu können. Also in dem Fall eben n Werte zwischen ]0;1[ so zu kombinieren, dass möglichst viele Werte nahe an 1 rauskommen.

    btw. und ist schon richtig, die Rechtecke dürfen ja nicht über den Slot gucken.

    0
  • L

    btw. und ist schon richtig, die Rechtecke dürfen ja nicht über den Slot gucken.

    nein ist nicht richtig. Siehe dein Beispiel 10x10 slot und 2x 5x10 rechtecke breite+breite <= 10 passt, aber höhe+höhe <= 10 passt nicht und trotzdem passen beide in den slot 😉

    Dafür sollte es aber Algorithmen geben, um Flächen ideal füllen zu können

    glaub nicht (außer bruteforce (reicht hier wahrscheinlich))..

    Also in dem Fall eben n Werte zwischen ]0;1[ so zu kombinieren, dass möglichst viele Werte nahe an 1 rauskommen.

    btw. und ist schon richtig, die Rechtecke dürfen ja nicht über den Slot gucken.

    so einfach ist es ja nicht. Es sind ja rechtecke und keine Linien und wenn du davon ausgehst, dass du z.b. 10 rechtecke in 1 slot packen könntest, ist das ganz und garnicht trivial 🙂
    Wenn du es natürlich darauf beschränkst, dass du sagst, dass mehr als 2 rechtecke eh nicht in eine gruppe dürfen, ist es recht einfach..

    0
Anmelden zum Antworten