Algorithmus um Rechtecke auf einer Fläche zu platzieren

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.

rüdiger

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.

rüdiger

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

life

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

rüdiger

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.

life

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..

rüdiger

life schrieb:

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

argh, mein Kopf ist zu voll mit Rechtecken

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..[/quote]

hmm. Man könnte einfach die Liste der passenden Rechtecke nach Größe sortieren und von unten an Anfangen aufzusummieren, immer bis man 1 erreicht hat oder darüber kommt. Muss ja nicht perfekt sein, aber es soll ja auch nicht zu dicht platziert werden.

life

kingruedi schrieb:

hmm. Man könnte einfach die Liste der passenden Rechtecke nach Größe sortieren und von unten an Anfangen aufzusummieren, immer bis man 1 erreicht hat oder darüber kommt. Muss ja nicht perfekt sein, aber es soll ja auch nicht zu dicht platziert werden.

wie bis man 1 erreicht hat? du kannst natürlich die rechtecke immer rechts neben dem letzten rechteck hängen und wenn du das rechte ende gestoßen bist, fängst in der in der nächsten zeile, direkt unter dem untersten rand aller rechtecke der drüberliegenden ziele, an (immernoch im gleichen slot)...

soll das programm dann auf WIN laufen und alle fenster können sich so anzeigen?
wenn fertig wirst, sagst du es dann? ist es freeware?

newkid schrieb:

soll das programm dann auf WIN laufen und alle fenster können sich so anzeigen?
wenn fertig wirst, sagst du es dann? ist es freeware?

kingruedi und windows? rofl

rüdiger

newkid schrieb:

soll das programm dann auf WIN laufen und alle fenster können sich so anzeigen?
wenn fertig wirst, sagst du es dann? ist es freeware?

Nein, ist für Sawfish und wird in Rep, einem (leider nicht so schönem) Lisp-Dialekt, geschrieben. Sourcecode ist vermutlich frei verwendbar.

kingruedi schrieb:

@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.

Ja, so nennt man es glaube ich auch. Das kannst du verwenden, um zu beweisen, dass dieses Problem schwer ist.

Bye, TGGC (Denken, und gut ist.)