¿Cómo calcular la rotación de figuras de manera eficiente?

13

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í:

  1. Recorrer los ángulos de 0 a 45.
  2. Para el ángulo actual, para cada punto de la figura, calcule la ubicación nueva y rotada
  3. 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
  4. 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?

    
pregunta Dusan 11.11.2014 - 22:20

2 respuestas

20

Parece que puedes encontrar el cuadro delimitador mínimo alineado arbitrariamente usando el tiempo lineal Rotating algoritmo de calibradores .

Una vez que tenga el cuadro delimitador, solo necesita determinar el ángulo de rotación calculando la pendiente de uno de los lados.

    
respondido por el Dan Pichelman 11.11.2014 - 22:37
12

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 ser reparado:

  • encuentre el casco convexo del polígono

  • recorre el número finito (!) de ángulos dado por los bordes exteriores del casco convexo

  • ahora aplique los pasos 2 a 4 usando estos ángulos.

Esto funciona porque se puede mostrar que el mínimo rectángulo encerrado debe tocar uno de los bordes exteriores del casco convexo.

    
respondido por el Doc Brown 11.11.2014 - 22:49

Lea otras preguntas en las etiquetas