algorithm - tutorial - Calcula el rectángulo más grande en un rectángulo girado

programming algorithms

Question

Estoy tratando de encontrar la mejor manera de calcular el rectángulo más grande (en el área) que se puede contener dentro de un rectángulo girado.

Algunas imágenes deberían ayudar (espero) a visualizar lo que quiero decir:

Se da el ancho y la altura del rectángulo de entrada y también el ángulo para girarlo. El rectángulo de salida no está girado ni sesgado.

Voy por la ruta larga, que ni siquiera estoy seguro de si manejará las casillas de esquina (sin juego de palabras). Estoy seguro de que hay una solución elegante para esto. ¿Algun consejo?

EDITAR : Los puntos del rectángulo de salida no necesariamente tienen que tocar los bordes de los rectángulos de entrada. (Gracias al Sr. E)

Answer 1

@Andri no funciona correctamente para la imagen donde width > height como probé. Entonces, arreglé y optimicé su código de esa manera (con solo dos funciones trigonométricas):

calculateLargestRect = function(angle, origWidth, origHeight) {
var w0, h0;
if (origWidth <= origHeight) {
w0 = origWidth;
h0 = origHeight;
}
else {
w0 = origHeight;
h0 = origWidth;
}
// Angle normalization in range [-PI..PI)
var ang = angle - Math.floor((angle + Math.PI) / (2*Math.PI)) * 2*Math.PI;
ang = Math.abs(ang);
if (ang > Math.PI / 2)
ang = Math.PI - ang;
var sina = Math.sin(ang);
var cosa = Math.cos(ang);
var sinAcosA = sina * cosa;
var w1 = w0 * cosa + h0 * sina;
var h1 = w0 * sina + h0 * cosa;
var c = h0 * sinAcosA / (2 * h0 * sinAcosA + w0);
var x = w1 * c;
var y = h1 * c;
var w, h;
if (origWidth <= origHeight) {
w = w1 - 2 * x;
h = h1 - 2 * y;
}
else {
w = h1 - 2 * y;
h = w1 - 2 * x;
}
return {
w: w,
h: h
}
}

ACTUALIZAR

También decidí publicar la siguiente función para el cálculo de recantalización proporcional:

calculateLargestProportionalRect = function(angle, origWidth, origHeight) {
var w0, h0;
if (origWidth <= origHeight) {
w0 = origWidth;
h0 = origHeight;
}
else {
w0 = origHeight;
h0 = origWidth;
}
// Angle normalization in range [-PI..PI)
var ang = angle - Math.floor((angle + Math.PI) / (2*Math.PI)) * 2*Math.PI;
ang = Math.abs(ang);
if (ang > Math.PI / 2)
ang = Math.PI - ang;
var c = w0 / (h0 * Math.sin(ang) + w0 * Math.cos(ang));
var w, h;
if (origWidth <= origHeight) {
w = w0 * c;
h = h0 * c;
}
else {
w = h0 * c;
h = w0 * c;
}
return {
w: w,
h: h
}
}

Answer 2

Coproc resolvió este problema en otro hilo ( https://.com/a/16778797 ) de una manera simple y eficiente. Además, dio una muy buena explicación y código de pitón allí.

A continuación está mi implementación Matlab de su solución:

function [ CI, T ] = rotateAndCrop( I, ang )
%ROTATEANDCROP Rotate an image ''I'' by ''ang'' degrees, and crop its biggest
% inner rectangle.
[h,w,~] = size(I);
ang = deg2rad(ang);
% Affine rotation
R = [cos(ang) -sin(ang) 0; sin(ang) cos(ang) 0; 0 0 1];
T = affine2d(R);
B = imwarp(I,T);
% Largest rectangle
% solution from https://.com/a/16778797
wb = w >= h;
sl = w*wb + h*~wb;
ss = h*wb + w*~wb;
cosa = abs(cos(ang));
sina = abs(sin(ang));
if ss <= 2*sina*cosa*sl
x = .5*min([w h]);
wh = wb*[x/sina x/cosa] + ~wb*[x/cosa x/sina];
else
cos2a = (cosa^2) - (sina^2);
wh = [(w*cosa - h*sina)/cos2a (h*cosa - w*sina)/cos2a];
end
hw = flip(wh);
% Top-left corner
tl = round(max(size(B)/2 - hw/2,1));
% Bottom-right corner
br = tl + round(hw);
% Cropped image
CI = B(tl(1):br(1),tl(2):br(2),:);

Answer 3

Primero, nos ocupamos del caso trivial donde el ángulo es cero o un múltiplo de pi / 2. Entonces el rectángulo más grande es el mismo que el rectángulo original.

En general, el rectángulo interno tendrá 3 puntos en los límites del rectángulo externo. Si no lo hace, entonces puede moverse de modo que un vértice esté en la parte inferior y un vértice esté a la izquierda. Luego puedes agrandar el rectángulo interno hasta que uno de los dos vértices restantes toque un límite.

Llamamos a los lados del rectángulo exterior R1 y R2. Sin pérdida de generalidad, podemos suponer que R1 <= R2. Si llamamos a los lados del rectángulo interno H y W, entonces tenemos eso

H cos a + W sin a <= R1
H sin a + W cos a <= R2

Como tenemos al menos 3 puntos en los límites, al menos una de estas desigualdades debe ser una igualdad. Usemos el primero. Es fácil ver eso:

W = (R1 - H cos a) / sin a

y entonces el área es

A = H W = H (R1 - H cos a) / sin a

Podemos tomar la derivada wrt. H y requiere que sea igual a 0:

dA/dH = ((R1 - H cos a) - H cos a) / sin a

Resolviendo para H y usando la expresión para W arriba, encontramos que:

H = R1 / (2 cos a)
W = R1 / (2 sin a)

Sustituir esto en la segunda desigualdad se convierte, después de alguna manipulación,

R1 (tan a + 1/tan a) / 2 <= R2

El factor en el lado izquierdo siempre es al menos 1. Si se cumple la desigualdad, entonces tenemos la solución. Si no está satisfecho, entonces la solución es la que satisface tanto las desigualdades como las igualdades. En otras palabras: es el rectángulo el que toca los cuatro lados del rectángulo externo. Este es un sistema lineal con 2 incógnitas que se resuelve fácilmente:

H = (R2 cos a - R1 sin a) / cos 2a
W = (R1 cos a - R2 sin a) / cos 2a

En términos de las coordenadas originales, obtenemos:

x1 = x4 = W sin a cos a
y1 = y2 = R2 sin a - W sin^2 a
x2 = x3 = x1 + H
y3 = y4 = y2 + W

Answer 4

Solo vine aquí buscando la misma respuesta. Después de estremecerme ante la idea de tanta matemática involucrada, pensé que recurriría a una suposición semi-educada. Garabateando un poco llegué a la conclusión (intuitiva y probablemente no del todo exacta) de que el rectángulo más grande es proporcional al rectángulo exterior resultante, y sus dos esquinas opuestas se encuentran en la intersección de las diagonales del rectángulo externo con el lado más largo del rectángulo girado. Para los cuadrados, cualquiera de las diagonales y lados harían ... Supongo que estoy feliz con esto y ahora comenzaré a quitar las telarañas de mis oxidadas habilidades trigonométricas (patético, lo sé).

Actualización menor ... Se las arregló para hacer algunos cálculos trigonométricos. Esto es para el caso cuando la Altura de la imagen es mayor que el Ancho.

Actualizar. Tengo todo funcionando. Aquí hay un código js. Está conectado a un programa más grande, y la mayoría de las variables están fuera del alcance de las funciones, y se modifican directamente desde dentro de las funciones. Sé que esto no es bueno, pero estoy usando esto en una situación aislada, donde no habrá confusión con otros scripts: redactado

Me tomé la libertad de limpiar el código y extraerlo a una función:

function getCropCoordinates(angleInRadians, imageDimensions) {
var ang = angleInRadians;
var img = imageDimensions;
var quadrant = Math.floor(ang / (Math.PI / 2)) & 3;
var sign_alpha = (quadrant & 1) === 0 ? ang : Math.PI - ang;
var alpha = (sign_alpha % Math.PI + Math.PI) % Math.PI;
var bb = {
w: img.w * Math.cos(alpha) + img.h * Math.sin(alpha),
h: img.w * Math.sin(alpha) + img.h * Math.cos(alpha)
};
var gamma = img.w < img.h ? Math.atan2(bb.w, bb.h) : Math.atan2(bb.h, bb.w);
var delta = Math.PI - alpha - gamma;
var length = img.w < img.h ? img.h : img.w;
var d = length * Math.cos(alpha);
var a = d * Math.sin(alpha) / Math.sin(delta);
var y = a * Math.cos(gamma);
var x = y * Math.tan(gamma);
return {
x: x,
y: y,
w: bb.w - 2 * x,
h: bb.h - 2 * y
};
}

Encontré algunos problemas con el gamma -cálculo y lo modifiqué para tener en cuenta en qué dirección la caja original es la más larga.

- Magnus Hoff

Answer 5

Tratando de no romper la tradición poniendo la solución del problema como una imagen :)

Editar: Terceras ecuaciones es incorrecto. El correcto es:

3.w * cos (α) * X + w * sin (α) * Y - w * w * sin (α) * cos (α) - w * h = 0

Para resolver el sistema de ecuaciones lineales puedes usar la regla de Cramer o el método de Gauss .

Answer 6

disculpe por no dar una derivación aquí, pero resolví este problema en Mathematica hace unos días y se me ocurrió el siguiente procedimiento, que personas que no son de Mathematica deberían poder leer. En caso de duda, consulte http://reference.wolfram.com/mathematica/guide/Mathematica.html

El siguiente procedimiento devuelve el ancho y la altura de un rectángulo con un área máxima que se ajusta a otro rectángulo de ancho wy alto h que ha sido rotado alfa.

CropRotatedDimensionsForMaxArea[{w_, h_}, alpha_] :=
With[
{phi = Abs@Mod[alpha, Pi, -Pi/2]},
Which[
w == h, {w,h} Csc[phi + Pi/4]/Sqrt[2],
w > h,
If[ Cos[2 phi]^2 < 1 - (h/w)^2,
h/2 {Csc[phi], Sec[phi]},
Sec[2 phi] {w Cos[phi] - h Sin[phi], h Cos[phi] - w Sin[phi]}],
w < h,
If[ Cos[2 phi]^2 < 1 - (w/h)^2,
w/2 {Sec[phi], Csc[phi]},
Sec[2 phi] {w Cos[phi] - h Sin[phi], h Cos[phi] - w Sin[phi]}]
]
]

Answer 7

Editar : Mi respuesta de Mathematica a continuación es incorrecta: estaba resolviendo un problema ligeramente diferente de lo que creo que realmente está preguntando.

Para resolver el problema que realmente está preguntando, usaría el (los) siguiente (s) algoritmo (s):

En el problema de rectángulo vacío máximo

Usando este algoritmo, denote una cantidad finita de puntos que forman el límite del rectángulo girado (tal vez un 100 o así, y asegúrese de incluir las esquinas) - estos serían el conjunto S descrito en el documento.

.

.

.

.

.

Por posteridad, he dejado mi publicación original a continuación:

El rectángulo interior con el área más grande siempre será el rectángulo donde la esquina media inferior del rectángulo (la esquina cercana al alfa en su diagrama) es igual a la mitad del ancho del rectángulo externo.

De alguna manera hice trampa y usé Mathematica para resolver el álgebra para mí:

De esto se puede ver que el área máxima del rectángulo interno es igual a 1/4 de ancho ^ 2 * cosecante del ángulo multiplicado por la secante del ángulo.

Ahora necesito averiguar cuál es el valor x de la esquina inferior para esta condición óptima. Usando la función Solve en mathematica en mi fórmula de área, obtengo lo siguiente:

Lo que muestra que la coordenada x de la esquina inferior es igual a la mitad del ancho.

Ahora solo para asegurarme, voy a probar nuestra respuesta empíricamente. Con los resultados a continuación puede ver que, de hecho, el área más alta de todas mis pruebas (definitivamente no es exhaustiva pero obtiene el punto) es cuando el valor x de la esquina inferior es la mitad del ancho del rectángulo externo.

Answer 8

Aquí está la forma más fácil de hacer esto ... :)

Step 1
//Before Rotation
int originalWidth = 640;
int originalHeight = 480;
Step 2
//After Rotation
int newWidth = 701; //int newWidth = 654; //int newWidth = 513;
int newHeight = 564; //int newHeight = 757; //int newHeight = 664;
Step 3
//Difference in height and width
int widthDiff ;
int heightDiff;
int ASPECT_RATIO = originalWidth/originalHeight; //Double check the Aspect Ratio
if (newHeight > newWidth) {
int ratioDiff = newHeight - newWidth;
if (newWidth < Constant.camWidth) {
widthDiff = (int) Math.floor(newWidth / ASPECT_RATIO);
heightDiff = (int) Math.floor((originalHeight - (newHeight - originalHeight)) / ASPECT_RATIO);
}
else {
widthDiff = (int) Math.floor((originalWidth - (newWidth - originalWidth) - ratioDiff) / ASPECT_RATIO);
heightDiff = originalHeight - (newHeight - originalHeight);
}
} else {
widthDiff = originalWidth - (originalWidth);
heightDiff = originalHeight - (newHeight - originalHeight);
}
Step 4
//Calculation
int targetRectanleWidth = originalWidth - widthDiff;
int targetRectanleHeight = originalHeight - heightDiff;
Step 5
int centerPointX = newWidth/2;
int centerPointY = newHeight/2;
Step 6
int x1 = centerPointX - (targetRectanleWidth / 2);
int y1 = centerPointY - (targetRectanleHeight / 2);
int x2 = centerPointX + (targetRectanleWidth / 2);
int y2 = centerPointY + (targetRectanleHeight / 2);
Step 7
x1 = (x1 < 0 ? 0 : x1);
y1 = (y1 < 0 ? 0 : y1);