Wie berechnet man effizient die Rotation der Figur?

13

Bild 1 Bild 2

Ich habe eine Figur durch eine Matrix von Bytes (Bitmap-ähnliche Matrix) dargestellt. Beispiel Abbildung ist auf dem Bild zu sehen Picture 1.

Das Ziel ist es, den besten Drehwinkel einer bestimmten Figur zu finden . Wenn die Figur um den besten Winkel gedreht wird, hat das Rechteck, das parallel zur X- und Y-Achse verläuft und die Figur beschriftet, die kleinste Fläche.

Rechtecke, die die Figur beschriften, sind auf den Bildern hellgrau dargestellt. In der Picture 2ist zu sehen, dass die ideale Drehung der Figur etwa 30 Grad im Uhrzeigersinn beträgt.

Nun, ich weiß Algorithmus, wie man diesen Winkel findet, aber es scheint mir, dass das sehr ineffizient ist. Es geht so:

  1. Schleife durch Winkel von 0 bis 45.
  2. Berechnen Sie für den aktuellen Winkel für jeden Zahlenpunkt eine neue, gedrehte Position
  3. Finden Sie die Grenzen des Rechtecks, das die Figur enthält (minimales und maximales x, y) und registrieren Sie es, wenn dies die beste Übereinstimmung bisher ist
  4. Nächster Winkel

Dies ist eine Art Brute-Force-Methode und funktioniert für die kleinen Figuren gut und relativ schnell. Ich muss jedoch mit Zahlen arbeiten, die bis zu 10 Millionen Punkte enthalten, und mein Algorithmus wird langsam.

Was wäre ein guter Algorithmus für dieses Problem?

Dusan
quelle

Antworten:

20

Es sieht so aus, als könnten Sie den beliebig ausgerichteten minimalen Begrenzungsrahmen mithilfe des Algorithmus für die lineare Zeitdrehung der Bremssättel finden .

Sobald Sie den Begrenzungsrahmen haben, müssen Sie nur den Drehwinkel bestimmen, indem Sie die Neigung einer der Seiten berechnen.

Dan Pichelman
quelle
Dies ist eine großartige Lösung, sehr gute.
InformedA
Toll, da ich bereits Punkte nach x und y sortiert habe, kann ich mit diesem en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/… eine konvexe Hülle finden und einen vorhandenen Algorithmus mit Hüllenpunkten verwenden.
Dusan
12

Der erste Schritt Ihres Ansatzes ist fehlerhaft - es gibt unendlich viele reelle Werte zwischen 0 und 45, daher macht es keinen Sinn, sie "durchzugehen". Ihr Algorithmus kann jedoch repariert werden:

  • Finden Sie die konvexe Hülle des Polygons

  • Schleife durch die endliche (!) Anzahl von Winkeln, die durch die Außenkanten der konvexen Hülle gegeben sind

  • Wenden Sie nun die Schritte 2 bis 4 mit diesen Winkeln an.

Dies funktioniert, weil gezeigt werden kann, dass das minimale umschließende Rechteck eine der Außenkanten der konvexen Hülle berühren muss.

Doc Brown
quelle
Ja, genau das werde ich tun, bereits mit Hilfe der Antwort des Dan herausgefunden. Vielen Dank.
Dusan
@Dusan: Ich bin mir nicht sicher, ob die andere Antwort den gleichen Ansatz beschreibt, daher habe ich versucht, die Lösung auf einfachere Weise zu beschreiben, hoffentlich ein bisschen klarer. Eine Beschreibung finden Sie hier: cgm.cs.mcgill.ca/~orm/maer.html
Doc Brown
Ja, Sie haben Recht, Ihr Ansatz ist viel konkreter, einfacher und klarer, aber ich habe denselben Ansatz selbst mit den in Dans Antwort gegebenen Hinweisen abgeschlossen und ihm daher zugestimmt. Ich hoffe, Ihre Antwort wird viel mehr positive Stimmen erhalten. Keine harten Gefühle. Prost!
Dusan