Tengo una figura representada a través de una matriz de bytes (matriz similar a un mapa de bits). La figura de ejemplo se muestra en el Picture 1.
El objetivo es encontrar el mejor ángulo de rotación de alguna figura dada . Cuando la Figura se gira con el mejor ángulo, el rectángulo que es paralelo a los ejes X e Y e inscribe que la Figura tiene el área más pequeña.
Los rectángulos que inscriben la figura se muestran como gris claro en las imágenes. En el Picture 2, puede ver que la rotación ideal de la Figura es de aproximadamente 30 grados en el sentido de las agujas del reloj.
Ahora, conozco el algoritmo de cómo encontrar este ángulo, pero me parece que es muy ineficiente. Dice así:
- Recorre los ángulos de 0 a 45.
- Para el ángulo actual, para cada punto de la figura, calcule la ubicación nueva, girada
- Encuentre los límites del rectángulo que contiene la figura (mínimo y máximo x, y) y regístrelo si es la mejor coincidencia hasta ahora
- Ángulo siguiente
Este es un tipo de método de fuerza bruta y funciona bien y 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?
fuente
El primer paso de su enfoque es defectuoso: hay un número infinito de valores reales entre 0 y 45, por lo que no tiene sentido "recorrerlos". Sin embargo, su algoritmo puede repararse:
encontrar el casco convexo del polígono
recorre el número finito (!) de ángulos dados por los bordes exteriores del casco convexo
ahora aplique los pasos 2 a 4 usando estos ángulos.
Esto funciona porque se puede demostrar que el rectángulo mínimo envolvente debe tocar uno de los bordes exteriores del casco convexo.
fuente