Algorithmus um Rechtecke auf einer Fläche zu platzieren
-
@newkid
Dein Algorithmus ist so wie ich das sehe erstmal nur ein Teilschritt von meinem Algorithmus.
-
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
-
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.
-
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..
-
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.
-
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
-
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.)