Berechnung der Eckpunkte eine Rechtecks

[Azatoth]

Hallo zusammen,
ich habe folgendes Problem:
Stellt euch ein beliebiges Zeichen als gerade Linien in einem zwei Dimensionalen Koordinatensystem vor. Das Zeichen kann um einen beliebigen Winkel gedreht und an einer beliebigen Koordinate positioniert sein. Im Vorfeld gegeben hat man die Minimal- und Maximalwerte zu X und Y (Unausgefüllte rote Kreise in der Grafik), den Mittelpunkt (Ausgefüllter Kreis in der Grafik)und den Winkel um wie viel Grad das Zeichen gedreht ist.

Meine Frage lautet nun: Kann man sich anhand dieser Werte die Eckpunkte eines umschließenden Rechtecks berechnen (Gestrichelte grüne Linien in der Grafik)?

Zur besseren Vorstellung:

 

[sheel]

Hi

muss es das kleinstögliche Rechteck sein? (nach Fläche oder Umfang?)
Muss es die unausgefüllten Punkte alle berühren?
Darf es auch andere Drehwinkel als das Zeichen haben?

 

[alxy]

Ist glaub ich nicht immer möglich.... Manchmal sind zB durch Mittelpunkt plus zwei maximalpunkte auch verschiedene rechtecke möglich (wenn ich das im kopf mal so drehe)

 

[Azatoth]

Es sollte das kleinstmögliche Rechteck sein (genau mit allen "Vektoren" abschließen) und denselben Drehwinkel wie das Zeichen besitzen.

 

[HonniCilest]

Ich habe mir mal im Kopf verschiedene Möglichkeiten überlegt wie ich das Rechteck um die 4 konstruieren würde und alleine hier kamen in meinem Kopf mehrere verschiedene Rechtecke zum Vorschein. Ganz einfaches Beispiel gegenüber deinem:
Nehme die 4 Extreme (Höchster, niedrigster, linkester, rechtester Punkt) und verwende nur Linien, welche parallel zur Koordinatenachse liegen. Du kommst so auch zu einem Rechteck, es ist nur nicht so optimal wie das abgebildete.

Optimalste Variante ist aber vermutlich diese (Achtung 2 Lösungen):
Ergänze deine Figur durch imaginäre Linien so, dass ein beliebiges Viereck entsteht in deinem obigen Bild wären das 3 Linien. Zusätzlich hast du 2 Verbindungslinien e & f der jeweils gegenüberliegenden Punkte. Jetzt musst du dich für e oder f entscheiden. Ich nehme nun e. Du kannst von 2 Eckpunkten (B, D) ein Lot auf e fällen, d.h. h von 2 Dreiecken --> h1 und h2. Wenn du nun h1 und h2 als Vektoren betrachtest (Richtung von Verbindungslinie auf Eckpunkte B, D) und e die Verbindungslinie vom Punkt A und C ist, dann sind die Eckpunkte: A+h1, A+h2, C+h1 und C+h2.

Bitte um Korrektur, falls ich mit dieser Ausfühung irgendwo falsch liegen sollte

Beispiel für die Berechnung der benötigten Elemente gibt es unzählige im Netz.

 

[Yaslaw]

Es sollte das kleinstmögliche Rechteck sein (genau mit allen "Vektoren" abschließen) und denselben Drehwinkel wie das Zeichen besitzen.

Denselben Drehwinkel.
Naja, Das Koordinatensystem drehen (den Winkel hast du ja) Min/max x/y ermitteln, Die Schnittpunkte ermitteln und alles wieder zurückdrehen. Fertig.

 

[Azatoth]

Danke für die Antworten ich werde sie morgen gleich ausprobieren.

 

[mermshaus]

Ich versuche mal, den Ansatz mit linearer Algebra noch etwas auszuführen:

Definitionen:

  P[] := Punkte der Figur
  D   := Mittelpunkt/Drehpunkt
  w   := Winkel (im Bogenmaß)

Rotationsmatrix A mit Drehpunkt D um Winkel w:

      ( 1  0  D.x )     ( cos(-w)  -sin(-w)  0 )     ( 1  0  -D.x ) 
  A = ( 0  1  D.y )  *  ( sin(-w)   cos(-w)  0 )  *  ( 0  1  -D.y )
      ( 0  0    1 )     (       0         0  1 )     ( 0  0     1 )

Das sind zwei Translationsmatrizen, um das Koordinatensystem in den Drehpunkt zu verschieben (und wieder zurück), und in der Mitte die eigentliche Rotationsmatrix um den Ursprung.

Für jeden Punkt X in P (X ist dabei ein Vektor (x, y, 0)T):

  X' = A * X

Die minimalen/maximalen x- und y-Koordinaten aller X' sind die Punkte der umrahmenden Box. Die müssen dann noch mit B multipliziert werden, um sie zurückzudrehen:

      ( 1  0  D.x )     ( cos(w)  -sin(w)  0 )     ( 1  0  -D.x ) 
  B = ( 0  1  D.y )  *  ( sin(w)   cos(w)  0 )  *  ( 0  1  -D.y )
      ( 0  0    1 )     (      0        0  1 )     ( 0  0     1 )

B ist wie A nur mit positivem Winkel.

Die so entstehenden Koordinaten sind die, die du suchst.

(Zwei Translationen kann man sich vielleicht sparen. Meine Matrizen sind recht explizit als „Rotation um Punkt“-Matrizen angelegt.)

PS: Eine PHP-Implementierung hätte ich da, weil ich für diesen Thread das Zeugs erst kürzlich mal zusammengepackt habe.

 

[Azatoth]

Ich habe es nun mit der Methode die Yaslaw beschrieben hat gemacht. Funktioniert einwandfrei, danke nochmal an alle für die schnelle Hilfe.

Für alle die es interessiert hier noch ein Screenshot (für diesen Fall habe ich es benötigt)


Es ging darum die einzelnen Zeichen richtig am Kreisbogen auszurichten. Vorher hatte ich immer einen leichten Versatz was die Zeichen in den Kreis hineinlaufen lies. Mit der Ermittlung der Eckpunkte der einzelnen Zeichen konnte ich mir den Mittelpunkt der Linie errechnen die dem Kreisbogen zugewandt ist. Mit der Hilfe dieses Mittelpunkts und des Kreisbogenwinkels kam ich dann auf einen Offset, der es mir ermöglicht hat jedes einzelne Zeichen korrekt auszurichten...