Hallo alle zusammen!

Ich suche einen Algorithmus zum berechnen eines Rechtecks, welches den maximalen Flächeninhalt zweier übereinanderliegenden Rechtecke hat.

Beispiel:

2 Rechtecke der selben Größe (ja, immer der selben Größe), liegen anfangs genau aufeinander. Wenn ich den Algorithmus nun anwende, sollte dieser mir ein Rechteck von der Größe der anderen beiden zurückgeben.
Jetzt drehe ich eines der beiden Rechtecke um X Grad um den Mittelpunkt von sich selbst.
Nun soll der Algorithmus mir die Koordinaten eines Rechtecks zurückgeben. Dieses Rechteck darf nur aus einer Fläche bestehen, welche das gedrehte Ursprungsrechteck vollständig enthält (wird also kleiner bis zu einem bestimmten Winkel).


Eines der beiden Rechtecke ist immer gerade.(x-werte der linken/rechten punkte sind jeweils gleich)
Gegeben sind die Punkte der Ursprungsrechtecke (ungedreht,gedreht).
Das Zielrechteck liegt auch waagerecht im Koordinatensystem

Hat jemand schon mal so etwas gemacht?
Wie kann ich da rangehen?
Das kann man sicher irgendwie als Extremwertaufgabe lösen. Ist aber schon zu lange her, als das ich mich erinnern würde.

Hallo,

Wie hast du denn die Rechtecke gegeben? Und soll das umschließende Rechteck immer Achsenorientiert sein? Wenn beides mal ja, dann brauchst du dir aus den 8 Punkten nur den kleinsten bzw größten Wert für X und Y suchen, das sind dann die Begrenzungen für das umschließende Rechteck.

Ansonst gibts eine ganze Reihe von Algorithmen die man meistens unter dem Begriff "Bounding Boxes" findet. Sind zwar meist 3D Algorithmen, lassen sich aber im Normalfall mit ein bisschen Mathematika auch auf 2D bringen.

Also, ich habe mal eine Grafik angehangen, die das Problem beschreibt.

Die 2 scharzen Rechtecke sind gegeben und ich möchte das Rote (das ist eine Skizze, also ist es nicht 100% maßstabgenau , aber ich denke das Problem wird dadurch klar) errechnen.

Hier meine Lösung:

Neues Rechteck erstellen, welches das gedrehte Rechteck vollständig umschliesst. Somit hat man schonmal ein neues Seitenverhältnis.
Dieses neu erstellte Rechteck in Richtung Mittelpunkt in gleichem Verhältnis verkleinern. Dies tut man nun so lange bis alle Punkte des verkleinerten Rechtecks in dem gedrehten enthalten sind. Bei Fragen PM!