Cálculo del rectángulo delimitador en un ángulo de un polígono

Question

Tengo la necesidad de determinar el rectángulo delimitador para un polígono en un ángulo arbitrario. Esta imagen ilustra lo que tengo que hacer:

alt text http://kevlar.net/RotatedBoundingRectangle.png

El rectángulo de color rosa es lo que necesito para determinar con diversos ángulos de polígonos 2D simples.

¡Todas las soluciones son muy apreciadas!

Editar:

Gracias por las respuestas, lo tengo trabajo una vez me dieron las puntos centrales correcta. Ustedes son increíbles!

Answer 1

Para obtener un cuadro delimitador con un cierto ángulo, gire el polígono al revés en ese ángulo. Luego puede usar las coordenadas min/max x/y para obtener un cuadro delimitador simple y rotarlo por el ángulo para obtener el resultado final.

Según su comentario, parece que tiene problemas para obtener el punto central del polígono. El centro de un polígono debe ser el promedio de las sumas de coordenadas de cada punto. Así que para los puntos P1, ..., PN, calcular:

xsum = p1.x + ... + pn.x; 
ysum = p1.y + ... + pn.y; 
xcenter = xsum/n; 
ycenter = ysum/n; 

Para que esto sea completa, también agrego algunas fórmulas para la rotación en cuestión. Para girar un punto (x, y) en torno a un punto central (cx, cy), haga lo siguiente:

// Translate center to (0,0) 
xt = x - cx; 
yt = y - cy; 
// Rotate by angle alpha (make sure to convert alpha to radians if needed) 
xr = xt * cos(alpha) - yt * sin(alpha); 
yr = xt * sin(alpha) + yt * cos(alpha); 
// Translate back to (cx, cy) 
result.x = xr + cx; 
result.y = yr + cx; 

Answer 2

estoy interpretando su pregunta en el sentido de "Para un polígono 2D dado, ¿cómo se calcula la posición de un rectángulo delimitador para el cual el ángulo de orientación está predeterminado? "

Y lo haría rotando el polígono contra el ángulo de orientación, luego uso una búsqueda simple de sus puntos máximos y mínimos en los dos puntos cardinales utilizando cualquier algoritmo de búsqueda que sea apropiado para la estructura en que se encuentran los puntos del polígono almacenado en. (En pocas palabras, debe encontrar los valores X más altos y más bajos, y los valores Y más altos y más bajos.)

Luego, los mínimos y máximos definen su rectángulo.

Puede hacer lo mismo sin girar primero el polígono, pero su búsqueda de puntos mínimo y máximo tiene que ser más sofisticada.

Answer 3

Para obtener el rectángulo más pequeño, debe obtener el ángulo correcto. Esto puede lograrse mediante un algoritmo utilizado en la detección de colisiones: cuadros orientativos orientados. Los pasos básicos:

obtener todos los vértices cordinates
Construir una matriz de covarianza
Encuentra los valores propios
proyecto todos los vértices en el valor propio espacio
Búsqueda máximo y mínimo en cada espacio de valores propios.

Para obtener más información sólo Google OBB "detección de colision"

Sal: Si acaba de proyectar todos los vértices y encontrar (cuadro delimitador eje alineado) máximo y mínimo que está haciendo AABB. Es más fácil y requiere menos esfuerzo computacional, pero no garantiza la caja mínima.

Answer 4

Para obtener un rectángulo con un área mínima que encierra un polígono, puede usar el algoritmo a rotating calipers.

La clave es que (a diferencia de su imagen de muestra, entonces supongo que en realidad no necesita un área mínima), cualquier rectángulo mínimo es colineal con al menos un borde del casco convexo del polígono .