Passen Sie ein konvexes Polygon in ein gegebenes Rechteck ein

Question

Ich möchte ein konvexes Polygon nehmen und es durch Drehen und Skalieren in ein gegebenes Rechteck einfügen.

Mein Ansatz ist, das Polygon in kleinen Schritten (wie 1 °) zu drehen und immer den Bruch (maximale horizontale Entfernung/maximale vertikale Entfernung) zu messen, den Bruch zu nehmen (Rechteckbreite/Rechteckhöhe) und skaliere es so, dass es in das Rechteck passt.

Ich frage mich, ob es einen "weniger primitiven" Ansatz gibt. Darüber hinaus könnte es eine bessere Definition von "best fit" geben, als nur die maximale horizontale und vertikale Entfernung zu messen. Mein Ziel ist es, das Polygon "gut aussehen zu lassen", wenn ich es in einer Bilddatei ablege oder es auf einer Seite ausdrucke.

Answer 1

Sie können Methode wie rotating calipers verwenden.

Während rotierende Calipers Algorithmus Paare von antipodalen Vertices mit zwei parallelen Linien findet, benötigen Sie vier senkrechte Linien - Rechteck.

Wählen Sie die erste Scheitelpunkt, finden Sie antipodale Scheitelpunkt für es - es ist das erste Caliper-Paar.
Bauen Sie das zweite Bremssattelpaar senkrecht zum ersten Bremssattelpaar auf.
Drehen Sie beide Bremssattelpaare, bis das nächste antipodische Paar gefunden wird (entweder zwischen den ersten Bremssätteln oder zwischen den zweiten Bremssätteln) - Sie bestimmen den nächsten Extremwinkelpunkt.
Fahren Sie fort, Bremssättel zu drehen.

Die Breite und Höhe des Begrenzungsrechtecks ​​variieren kontinuierlich zwischen den Extrempunkten. Und der Breiten-/Höhenanteil wird auch kontinuierlich sein. Wenn Sie also finden, dass im i-ten Extrempunkt W/H < P und im (i + 1) -ten Extrempunkt W/H> P ist, wobei P die benötigte Proportion ist, dann enthält das Intervall i..i + 1 das benötigte P Wert (Bolzano's theorem).

Wenn Sie das Intervall mit der Lösung gefunden haben (falls vorhanden), berechnen Sie einfach den Anteil der Dicke des Messschiebers in diesem Winkelintervall (trigonometrische Gleichung) und erhalten den genauen Winkelwert. Trigonometrische Gleichung scheint aussehen, als

Sin(A)/Sin(A + Pi/2) = F 
or 
Sin(A)/Cos(A) = Tan(A) = F