Tengo una Figura representada a través de una matriz de bytes (matriz de mapa de bits).
El ejemplo Figura se muestra en el Picture 1 .
El objetivo es encontrar el mejor ángulo de rotación de una Figura dada. Cuando la Figura se gira por el mejor ángulo, el rectángulo que es paralelo a los ejes X e Y e inscribe la Figura tiene el área más pequeña.
Los rectángulos que inscriben la figura se muestran en gris claro en las imágenes.
En el Picture 2 , puede ver que la rotación ideal de la figura es aproximadamente 30 grados en el sentido de las agujas del reloj.
Ahora, sé el algoritmo de cómo encontrar este ángulo, pero me parece que es muy ineficiente. Funciona así:
- Recorrer los ángulos de 0 a 45.
- Para el ángulo actual, para cada punto de la figura, calcule la ubicación nueva y rotada
- Busque los límites del rectángulo que contiene la figura (mínimo y máximo x, y) y regístrela si es la mejor coincidencia hasta ahora
- Siguiente ángulo
Este es un tipo de método de fuerza bruta que funciona bien y es razonablemente rápido para las figuras pequeñas. Sin embargo, necesito trabajar con cifras que contengan hasta 10 millones de puntos, y mi algoritmo se vuelve lento.
¿Cuál sería un buen algoritmo para este problema?