Anordnung 2D Flächen

zeusosc

Hi,..

sagt mal, ich habe ne vorgegebene Fläche F und n Flächen in M,..
Alle Flächen aus M sind rechtwinklige Vierecke...
Nun möchte ich F mit Elementen aus M füllen, wobei der Abstand zwischen
zwei Elementen aus M in F 5 Einheiten groß ist, als ein Abstand d existert.

Wie könnte der Algo aussehen? Vlt. Lösbar mit dem Rucksagproblem?

Seid gegrüßt und habt dank
----------------------------------
Edit:
btw. Die elemente aus M dürfen dabei nicht rotiert oder transformiert werden,.. und der algo sollte mir sozusagen ausgeben, welches Element an position x landen sollte,...

grüüße

ich bräuchte auch einen algo... weil es besteht ein problem, ein unverständnis u
und der algo sollte mir sozusagen ausgeben, was der zeusosc so sagen wollte oder sollte,...

Was um alles in der Welt ist der "zeusosc"?

zeusosc

Hi,

was genau versteht Ihr an diesem Problem nicht?

Nochmal:
Ich habe eine rechtwinklige Viereckige Fläche F mit Dimensionen Breite b
und Höhe h.

Diese Fläche soll mit einer Menge Flächen "abgedeckt" werden, wobei diese
aber alle einen Abstand d zueinander haben sollen.

Die Frage lautet nun, wie macht man das, bzw. wie macht man das Effizient...

Meine Idee war zuerst:

suche die größte Fläche aus M, die in F mit gegebenen abstand d zum Rand
hinein passt. Zerteile die freie Fläche aus F so, das die Teilfflächen
aus F wieder rechtwinklige Vierecke sind.. Fange diese wieder an zu Füllen

grüße

knivil

was genau versteht Ihr an diesem Problem nicht?

Alles.

Ich habe eine rechtwinklige Viereckige Fläche F mit Dimensionen Breite b
und Höhe h.

Also ein Rechteck. Ist schon anders als

ich habe ne vorgegebene Fläche F

Diese Fläche soll mit einer Menge Flächen "abgedeckt" werden, wobei diese
aber alle einen Abstand d zueinander haben sollen.

Und hier hoert es schon wieder auf. Abstand? Wie wird der Abstand denn zwischen zwei abdeckenden FLaechen gemessen?

Mach 'ne Skizze! Versteht sonst keiner.

Bashar

Ich habe eine rechtwinklige Viereckige Fläche F mit Dimensionen Breite b
und Höhe h.

Also ein Rechteck F.

Diese Fläche soll mit einer Menge Flächen "abgedeckt" werden, wobei diese
aber alle einen Abstand d zueinander haben sollen.

Das sind auch Rechtecke, hast du im Ausgangsposting geschrieben.

Die Frage lautet nun, wie macht man das, bzw. wie macht man das Effizient...

Erstmal würde ich die Abstände loswerden. Dazu vergrößerst du alle Seitenlängen um d. Es wurde nicht ganz klar, ob die inneren Rechtecke zur Innenseite des äußeren Rechtecks auch einen Abstand d haben müssen; je nachdem müsstest du die Seiten von F entweder um d verkleinern oder vergrößern.

Das Anordnen der Rechtecke ohne Abstände hört sich schon viel mehr nach einem Standardproblem an. Vielleicht kannst du hiermit was anfangen, das ist ein verwandtes Problem: http://en.wikipedia.org/wiki/Packing_problem#Different_rectangles_in_a_rectangle

Mit deiner zweiten Frage kommen wir der Sache schon näher.

Welchen Abstand meinst du? Welche Form haben die kleinen Flächen? (wurde schon beides nachgefragt).

Ich frage noch: Kannst du die kleinen Flächen beliebig (kontinuierlich) verschieben, oder müssen sie auf einem Raster (wie auf einem Karopapier) liegen?

Sind die kleinen Flächen alle gleichartig?

zeusosc

Hey,..

danke für die Antworten. Ich kann im Moment zwar nicht Antworten
(bin auf Arbeit) werde ich heute Abend aber nachholen.

Der Link der Wikipage auf Codeproject sieht vielversprechend aus...

Bis nachher und dank

zeusosc

Hi,

also die "abdeckenden" Flächen haben alle einen Abstand d zueinander,
es soll also etwas Platz bleiben.

Die kleinen Formen (Flächen) sind auch Rechtecke und können auf der Fläche F,
ich nenne diese jetzt mal Grundfläche, beliebig verschoben werden. Dennoch
wird durch den Abstand d ein Raster gebildet, also keine überdeckende Fläche
ist näher oder weiter enternt zu einer anderen Fläche (Form) als d.

Zur innenseite des äußeren Rechteckes muss kein Abstand sein.

Habe ich eine Frage vergessen?

Grüße

zeusosc

Also,

ich habe mir mal das von Codeproject angesehen,
und es ist der von vorhin geposteten Idee ähnlich.

Also einfach eins Reinpacken und die Grundfläche wieder
in Rechtecke teilen...

Korf hat wohl das ganze noch ein bisschen Performanter gemacht
http://www.aaai.org/Papers/ICAPS/2003/ICAPS03-029.pdf
und die restliche unbedeckte Fläche minimiert,..

mal gucken..

Danke an Euch