Вычислить наибольший прямоугольник во вращающемся прямоугольнике

Ответ 1

Я просто пришел сюда, чтобы найти тот же ответ. После того, как я содрогнулся от мысли о столь большой вовлеченности в математику, я подумал, что прибегну к полуобразованной догадке. Doodling немного я пришел к (интуитивному и, вероятно, не совсем точно) выводу, что наибольший прямоугольник пропорционален внешнему результирующему прямоугольнику, а два его противоположных угла лежат на пересечении диагоналей внешнего прямоугольника с самой длинной стороной повернутый прямоугольник. Для квадратов любая из диагоналей и сторон будет... Я думаю, что я достаточно доволен этим и теперь начну чистить паутину от моих ржавых триггерных навыков (жалко, я знаю).

Незначительное обновление... Управляется выполнением некоторых триггерных вычислений. Это относится к случаю, когда высота изображения больше ширины.

Update. Всё работает. Вот несколько js-кодов. Он связан с более крупной программой, и большинство переменных выходит за рамки функций и изменяется непосредственно из функций. Я знаю, что это нехорошо, но я использую это в изолированной ситуации, где не будет путаницы с другими сценариями: redacted

Я взял на себя ответственность за очистку кода и извлечение его из функции:

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
    };
}

Я столкнулся с некоторыми проблемами с gamma -калькуляцией и изменил его, чтобы учесть, в каком направлении исходный блок является самым длинным.

- Магнус Хофф

Ответ 2

Попытка не нарушать традицию, ставя решение проблемы как картины:)

Edit: Третьи уравнения неверны. Правильный:

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

Чтобы решить систему линейных уравнений, вы можете использовать правило Cramer или Гаусс.

Ответ 3

Сначала мы позаботимся о тривиальном случае, когда угол равен нулю или кратен pi/2. Тогда самый большой прямоугольник совпадает с исходным прямоугольником.

В общем случае внутренний прямоугольник будет иметь 3 точки на границах внешнего прямоугольника. Если это не так, то его можно перемещать так, чтобы одна вершина была внизу, а одна вершина - слева. Затем вы можете увеличить внутренний прямоугольник, пока одна из двух оставшихся вершин не достигнет границы.

Мы называем стороны внешнего прямоугольника R1 и R2. Без ограничения общности можно считать, что R1 <= R2. Если мы будем называть стороны внутреннего прямоугольника H и W, то мы имеем, что

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

Поскольку на границах имеется не менее 3 точек, по крайней мере одно из этих неравенств должно фактически быть равенством. Позвольте использовать первый. Легко видеть, что:

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

и поэтому область

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

Мы можем взять производную по. H и потребовать, чтобы оно равнялось 0:

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

Решая для H и используя выражение для W выше, получаем, что:

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

Подставляя это во второе неравенство, становится после некоторых манипуляций

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

Коэффициент в левой части всегда не меньше 1. Если выполняется неравенство, то мы имеем решение. Если это не выполняется, то решение является тем, которое удовлетворяет обеим неравенствам как равенствам. Другими словами: это прямоугольник, который касается всех четырех сторон внешнего прямоугольника. Это линейная система с двумя неизвестными, которые легко решаются:

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

В терминах исходных координат получаем:

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

Ответ 4

Изменить. Мой ответ Mathematica ниже неверен - я решал немного другую проблему, чем то, что, как я думаю, вы действительно спрашиваете.

Чтобы решить проблему, которую вы действительно задаете, я бы использовал следующий алгоритм (ы):

О проблеме максимального пустого прямоугольника

Используя этот алгоритм, обозначим конечное количество точек, которые образуют границу вращающегося прямоугольника (возможно, около 100 или около того, и обязательно включите углы) - это будет набор S, описанный в документе.

.

.

.

.

.

Для потомков я оставил свой оригинальный пост ниже:

Внутренний прямоугольник с наибольшей площадью всегда будет прямоугольником, где нижний средний угол прямоугольника (угол около альфы на вашей диаграмме) равен половине ширины внешнего прямоугольника.

Я как бы обманул и использовал Mathematica для решения алгебры для меня:

Отсюда видно, что максимальная площадь внутреннего прямоугольника равна 1/4 ширины ^ 2 * косеканта угла, умноженного на секущий угла.

Теперь мне нужно выяснить, что такое значение x нижнего угла для этого оптимального условия. Используя функцию Solve в математике по формуле моей области, я получаю следующее:

Что показывает, что координата x нижнего угла равна половине ширины.

Теперь, чтобы убедиться, я буду эмпирически проверять наш ответ. С приведенными ниже результатами вы можете видеть, что действительно самая высокая область всех моих тестов (определенно не исчерпывающая, но вы получаете точку), - это когда нижний угол x = половина ширины внешнего прямоугольника.

Ответ 5

@Andri работает неправильно для изображения, где width > height, как я тестировал. Итак, я исправил и оптимизировал его код таким образом (только с двумя тригонометрическими функциями):

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
    }
}

UPDATE

Также я решил опубликовать следующую функцию для пропорционального вычисления прямоугольника:

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
    }
}

Ответ 6

извините за то, что вы не дали никакого вывода, но я решил эту проблему в Mathematica несколько дней назад и придумал следующую процедуру, которую люди, не относящиеся к Mathematica, должны иметь возможность читать. Если у вас есть сомнения, обратитесь к http://reference.wolfram.com/mathematica/guide/Mathematica.html

Приведенная ниже процедура возвращает ширину и высоту прямоугольника с максимальной площадью, которая помещается в другой прямоугольник ширины w и высоты h, который был повернут альфа.

CropRotatedDimensionsForMaxArea[{w_, h_}, alpha_] := 
With[
  {phi = [email protected][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]}]
  ]
]

Ответ 7

Вот самый простой способ сделать это...:)

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);

Ответ 8

Coproc решила эту проблему в другом потоке (fooobar.com/info/121230/...) простым и эффективным способом. Кроме того, он дал очень хорошее объяснение и код python.

Ниже моя реализация Matlab его решения:

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 /info/121230/rotate-image-and-crop-out-black-borders/741827#741827

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),:);