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

Question

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

Некоторые картинки должны помочь (я надеюсь) в визуализации того, что я имею в виду:

Задана ширина и высота входного прямоугольника, а также угол его поворота. Выходной прямоугольник не повернут и не перекошен.

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

РЕДАКТИРОВАТЬ : Точки выходного прямоугольника не обязательно должны касаться краев входных прямоугольников. (Спасибо мистеру Э)

Answer 1

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

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

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

---

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

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

- Магнус Хофф

Answer 2

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

---

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

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

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

Answer 3

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

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

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

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. Если неравенство выполнено, то у нас есть решение. Если оно не выполняется, то решение является тем, которое удовлетворяет обоим неравенствам как равенствам. Другими словами: это прямоугольник, который касается всех четырех сторон внешнего прямоугольника. Это линейная система с 2 неизвестными, которая легко решается:

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

Answer 4

@ Андри не работает правильно для изображения, где 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
    }
}

Answer 5

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

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

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

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

.

.

.

.

.

Ради потомков я оставил свой первоначальный пост ниже:

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

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

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

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

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

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

Answer 6

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

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

Answer 7

Копрок решил эту проблему в другом потоке (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([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 8

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

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

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