Rechtecke zu moeglichst groesseren Rechtecken kombinieren?

[sirbender]

Hi,

ich will ein grosse Anzahl an Rechtecken zu groesseren kombinieren. Rechtecke die nebeneinander liegen koennen kombiniert werden wenn die Seite wo sie sich beruehren gleichlang ist. Sollte es mehrere Moeglichkeiten geben Rechtecke zu kombinieren sollte die Moeglichkeit gewaehlt werden die zum groesseren Rechteck fuehrt.

Alles was ich habe ist eine Liste mit Rechtecken. Die sind jetzt nicht so geordnet dass die die nebeneinander liegen auch aufeinander in der Liste folgen. Bin leider totaler Anfaenger, deswegen steh ich gerade auf dem Schlauf. Bestimmt kann jemand hier im Form schnell die 20 Zeilen code zeigen damit ich verstehe wie es am Besten geht.

Danke,
sb

 

[Sonecc]

Wird nur niemand tun.

Hast du schon ansätze?

 

[SlaterB]

ist es nicht die Optimierungsaufgabe, ein möglichst kleines umfassendes Rechteck zu finden?

 

[sirbender]

ist es nicht die Optimierungsaufgabe, ein möglichst kleines umfassendes Rechteck zu finden?

Mein Ziel aus 1000 Rechtecken eine Liste von sagen wir 400 Rechtecken zu machen indem ich benachbarte Rechtecke zu einem groesseren Rechteck zusammenfasse. Ich verstehe nicht ganz was du mit "kleines umfassendes Rechteck" meinst?

 

[SlaterB]

schau dir dein Beispielbild an, da ist oben links ein Recheck quasi mit weißen Rand,
dieses Rechteck könnte man dort wo es ist wegnehmen und stattdessen ganz links mittig ranhängen,

dann wäre das komplette umschließende Recheck, derzeit genau das Bild (553x403 groß) viel größer, vielleicht 600x403

ist das besser oder schlechter, soll das umschließende Rechteck groß oder klein sein oder gibts andere Kriterien?
oder widerspricht eine Regel dem Anschließen des Rechtecks ganz links

 

[sirbender]

Die Rechtecke sollen nicht ihre Position veraendern. Uebrigens sind die Rechtecke die Gelben Dinger. Das Weisse ist der Hintergrund.

Ich will benachbarte Rechtecke zusammenfassen wenn dies geht. Mehr nicht.

 

[SlaterB]

mein 'weißer Rand' diente nur zur Verdeutlichung, welches Rechteck ich meinte, dass das gelbe die Rechtecke sind war schon klar,

aber gut, durch deine Antwort wird es bisschen klarer, ich dachte eher an Lego-Steine unterschiedlicher Größe, die man beliebig anordnen kann,
du hast aber die Positionen wie in deinem Bild fest vorgegeben und das maximale Recheck wären hier die drei mittleren Rechtecke (untereinander) zusammen, richtig?

> Die sind jetzt nicht so geordnet dass die die nebeneinander liegen auch aufeinander in der Liste folgen.

wäre für einen zweidimensionalen Raum in einer eindimensionalen Liste auch schwierig, aber kein Problem, man kann die Daten ja beliebig verarbeiten

paar Ansatz-Ideen habe ich noch, Rechteck als Klasse, mit Verknüpfungen 'linker Nachbar' usw., aus der Liste ein Netz machen,
dann per Tiefensuche/ Backtracking von überall aus starten, alle denkbaren Kombinationen prüfen,

viel mehr kann ich persönlich noch nicht beitragen, ist deine Aufgabe,
geht übrigens Richtung 300 Zeilen statt 20

 

[sirbender]

Ok danke. Ich versuch es nochmal. Bisher hatte ich vor allem mit Arrays rumgewurschtelt. Vielleicht sind Klassen fuer jedes Rechteck besser.