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

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

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

Обновить. Всё работает. Вот несколько js-кодов. Он связан с более крупной программой, и большинство переменных выходит за frameworks функций и изменяется непосредственно из функций. Я знаю, что это плохо, но я использую это в изолированной ситуации, где не будет путаницы с другими сценариями: 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 калькуляцией и изменил ее, чтобы учесть, в каком направлении исходный ящик является самым длинным.

- Магнус Хофф

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

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

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

Для решения системы линейных уравнений вы можете использовать правило Крамера или метод Гаусса .

Во-первых, мы позаботимся о тривиальном случае, когда угол равен нулю или кратен 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 = HW = 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 

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

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

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

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

,

,

,

,

,

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

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

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

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

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

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

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

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

ОБНОВИТЬ

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

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

Вот самый простой способ сделать это … 🙂

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

извините за то, что я не дал здесь никакого вывода, но несколько дней назад я решил эту проблему в 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]}] ] ] 

Coproc решила эту проблему на другом streamе ( https://stackoverflow.com/a/16778797 ) простым и эффективным способом. Кроме того, он дал очень хорошее объяснение и код 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 https://stackoverflow.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([wh]); 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),:);