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

Algorithmus um Rechtecke auf einer Fläche zu platzieren

  • R

    Hallo,
    ich hab folgendes Problem: Ich habe N Rechtecke, jedes Rechteck hat eine bestimmte Größe (breite[tief]n[/tief], höhe[tief]n[/tief]). Nun will ich alle N Rechtecke auf einer Fläche mit der Größe (breite[tief]Fläche[/tief],höhe[tief]Fläche[/tief]) so platzieren, dass sich kein Rechteck überlappt. Dafür kann ich die Rechtecke verschieben und skalieren. Wobei verschieben bevorzugt werden sollte und nur wenn es anders nicht geht sollte verkleinert werden.

    Hat irgend jemand Hinweise oder Ideen zu einem Algorithmus, der so etwas machen kann?

    0
  • W

    Wow, ist auf den ersten Blick echt eine kniffelige Sache. Könnte mir vorstellen, dass man da einen Ansatz über dynamische Programmierung finden kann, dazu müsste es dir aber gelingen das große Problem in mehrere kleinere Probleme zu unterteilen. Vielleicht kommt mir im Laufe des Tages noch eine zündende Idee 🙂 .

    Ich habe es nur kurz überflogen, aber ich habe ein Paper gefunden in dem möglicherweise hilfreiche Informationen stehen könnten die zur Lösung deines Problems beitragen...
    http://csdl.computer.org/comp/proceedings/date/2004/2085/01/208510744.pdf

    0
  • R

    Ja, dass sieht schon mal gut aus. Ich werd es mir mal durchlesen (und ich hoffe, dass ich es auch kapiere *g*)

    Aber für weitere Informationen bin ich immer offen. Achso noch als Zusatzinformation. Der Algorithmus sollte möglichst 10-40 Rechtecke in Echtzeit platzieren können und lieber viele Rechtecke ein bisschen verkleinern, anstelle ein einzelnes extrem zu verkleinern.

    Und bei den Rechtecken handelt es sich eigentlich um GUI Fenster und die Fläche ist der Computer Desktop. Ich will nämlich so etwas ähnliches wie MacOS Xs Expose basteln.

    0
  • H

    Hey das ist doch mal eine gute Idee!

    Schau mal hier, das ist eine abgewandelte Version des Metacity WMs mit Expose ähnlichem Support -habs aber noch nicht getestet

    0
  • 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
Anmelden zum Antworten