Ho una Figura rappresentata attraverso una matrice di byte (matrice bitmap).
Esempio Figura è mostrato in Picture 1 .
L'obiettivo è trovare il miglior angolo di rotazione di alcuni dati Figura . Quando la figura viene ruotata secondo l'angolo migliore, il rettangolo parallelo agli assi X e Y e inscrive la Figura ha l'area più piccola.
I rettangoli che indicano la figura sono mostrati in grigio chiaro sulle immagini.
In Picture 2 , puoi vedere che la rotazione ideale della figura è di circa 30 gradi in senso orario.
Ora, conosco l'algoritmo come trovare questo angolo, ma mi sembra che sia molto inefficiente. Funziona così:
- Passa attraverso gli angoli da 0 a 45.
- Per l'angolo corrente, per ogni punto della figura calcola la nuova posizione ruotata
- Trova i limiti del rettangolo che contiene la figura (minima e massima x, y) e registrala se è la migliore corrispondenza fino ad ora
- Angolo successivo
Questo è un tipo di metodo a forza bruta e funziona bene e abbastanza velocemente per le piccole figure. Tuttavia, ho bisogno di lavorare con figure che contengano fino a 10 milioni di punti, e il mio algoritmo diventa lento.
Quale sarebbe un buon algoritmo per questo problema?