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:
- Schleife durch Winkel von 0 bis 45.
- Berechnen Sie für den aktuellen Winkel für jeden Zahlenpunkt eine neue, gedrehte Position
- 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
- 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?
quelle
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.
quelle