Rechteck zerlegen ?

[kutta]

Nabend Leute !
Wie kann man ein Rechteck in viele Zufallsrechtecke zerlegen . Dabei sollen die erzeugten Rechtecke eine gewisse Fläche nicht über- oder unterschreiten und die Eckpunkte benachbarter Rechtecke sollen sich nicht überlagern.(geht das überhaupt zum schluss bleibt mE doch immer ein zu kleiner verschnitt)
Hab schon mal gegoogelt und nicht richtiges gefunden, vielleicht hat ja jemand n link oder einen theoretischen ansatz wie man da am besten rangeht um es performant zu gestalten ? Oder wie nennt sich das Problem überhaupt ?
Danke fürn Tritt in die richtige Richtung !

[Kaeru Gaman]

ich bin der meinung das geht nicht.
den verschnitt kannst du nur vermeiden, wenn benachbarte rechtecke gleiche dimensionen haben,
oder wenn die größenbegrenzungen so weit gefasst sind,
dass ein rechteck so breit werden kann wie zwei andere zusammen.
also, mit "zufall" ist da garnichts.

[ZeHa]

Also ich hatte das jetzt so verstanden:



Sowas ist schon zufällig möglich (hab das ja jetzt selber auch nur zufällig gezeichnet), allerdings gibt es immer ein paar Punkte, die sich natürlich überlagern (vor allem die ganz am Rand). Das läßt sich wohl kaum vermeiden.

[Kaeru Gaman]

...und dort wären die größenbedingungen so weit gefasst,
dass das größte 5x so lang und breit sein kann wie das kleinste....

[Captn. Jinguji]

Hört sich nach Operations Research -> Optimierungsrechnung -> Lineare Programmierung -> Verschnittminimierung an.

[kutta]

Also ich hatte das jetzt so verstanden:



Sowas ist schon zufällig möglich (hab das ja jetzt selber auch nur zufällig gezeichnet), allerdings gibt es immer ein paar Punkte, die sich natürlich überlagern (vor allem die ganz am Rand). Das läßt sich wohl kaum vermeiden.

ja so ähnlich soll es schon aussehen ..
nur die überlagerungen
dadurch bilden benachbarte rechtecke durchgehende linien, rand ist rand da muss es natürlich so sein naja ich grübel weiter

[Kaeru Gaman]

achSO, du meinst durchgehende Schnitte...
das nennt man nicht Überlagerungen.

wie willst du ohne durchgehende schnitte in rechtecke aufteilen...

das geht vielleicht mit ganz präzise bemessenen identischen rechtecken.

oder mit verschiedenen regelmäßigen vielecken, schau dir mal die Arbeiten von M.C.Escher an.

[kutta]

achSO, du meinst durchgehende Schnitte...
das nennt man nicht Überlagerungen.

wie willst du ohne durchgehende schnitte in rechtecke aufteilen...

das geht vielleicht mit ganz präzise bemessenen identischen rechtecken.

oder mit verschiedenen regelmäßigen vielecken, schau dir mal die Arbeiten von M.C.Escher an.

nunja ich meine auf der skizze von zeha
-die beiden großen rechtecke (links)sind benachtbart trotzdem liegen die eckpunkte nicht nebeneinader
- hingegen die 3 rechtecke 2te reihe v. rechts oben jeweils 2 eckpunkte teilen (sich überlagern)

eigentlich denke ich müsste man die gesamtfläche wie eine summe in zufällige summanden zerlegen, daraus rechtecke mit zufälligen seitenlängen erzeugen
Aber lassen sie sich dann auch anders zusammensetzen und ergeben trotzdem die ursprüngliche form ???

[Kaeru Gaman]

nuja... als du von "nicht überlagern" sprachst, dachte ich erst,
dass du meinst dass ein rechteck nicht in ein anderes hineinragt.

also z.b. Box(40,50,60,70) und Box(80,90,100,110) überlagern / überschneiden sich in Box(80,90,20,30)

aber du hast ja "punkte überlagern" geschrieben, vielleicht sollte ich sorgfältiger lesen.

also, das ist definitiv nicht möglich.

setze vier beliebige rechtecke zusammen,
so dass sie sich keine eckpunkte teilen und zwischen ihnen keine lücke entsteht.
jetzt hast du außen vier Innenecken, wo jeweils ein punkt eines rechtecks liegt,
die du aber mit dem punkt eines weiteren dazukommenden
rechtecks belegen musst um die fläche lückenlos zu füllen.

regelmäßige Flächenfüllungen basieren darauf, dass die Vielecke sich Eckpunkte teilen.
Vielecke aneinander zu legen, ohne dass in den meisten punkten
mindestens zwei eckpunkte aufeinanderliegen, halte ich für unlösbar.


> Aber lassen sie sich dann auch anders zusammensetzen und ergeben trotzdem die ursprüngliche form ???

http://de.wikipedia.org/wiki/Tangram

[kutta]

nuja... als du von "nicht überlagern" sprachst, dachte ich erst,
dass du meinst dass ein rechteck nicht in ein anderes hineinragt.

also z.b. Box(40,50,60,70) und Box(80,90,100,110) überlagern / überschneiden sich in Box(80,90,20,30)

aber du hast ja "punkte überlagern" geschrieben, vielleicht sollte ich sorgfältiger lesen.

also, das ist definitiv nicht möglich.

setze vier beliebige rechtecke zusammen,
so dass sie sich keine eckpunkte teilen und zwischen ihnen keine lücke entsteht.
jetzt hast du außen vier Innenecken, wo jeweils ein punkt eines rechtecks liegt,
die du aber mit dem punkt eines weiteren dazukommenden
rechtecks belegen musst um die fläche lückenlos zu füllen.

regelmäßige Flächenfüllungen basieren darauf, dass die Vielecke sich Eckpunkte teilen.
Vielecke aneinander zu legen, ohne dass in den meisten punkten
mindestens zwei eckpunkte aufeinanderliegen, halte ich für unlösbar.


> Aber lassen sie sich dann auch anders zusammensetzen und ergeben trotzdem die ursprüngliche form ???

http://de.wikipedia.org/wiki/Tangram

du hast recht ...
musste mir das grad selbst hinmalen ums zu verstehn
muss ich wohl zehas lösung anstreben