python - une - Faire pivoter l'image et rogner les bordures noires



rogner une video (6)

Mon application: J'essaye de faire pivoter une image (en utilisant OpenCV et Python)

En ce moment j'ai développé le code ci-dessous qui fait tourner une image d'entrée, en la tapissant de bordures noires, en me donnant A. Ce que je veux, c'est B - la plus grande fenêtre de recadrage possible dans l'image pivotée. J'appelle cela la boîte bornée alignée sur l'axe.

C'est essentiellement la même chose que Rotate et recadrer , mais je ne peux pas obtenir la réponse à cette question pour travailler. De plus, cette réponse n'est apparemment valable que pour les images carrées. Mes images sont rectangulaires.

Code pour donner A:

import cv2
import numpy as np


def getTranslationMatrix2d(dx, dy):
    """
    Returns a numpy affine transformation matrix for a 2D translation of
    (dx, dy)
    """
    return np.matrix([[1, 0, dx], [0, 1, dy], [0, 0, 1]])


def rotateImage(image, angle):
    """
    Rotates the given image about it's centre
    """

    image_size = (image.shape[1], image.shape[0])
    image_center = tuple(np.array(image_size) / 2)

    rot_mat = np.vstack([cv2.getRotationMatrix2D(image_center, angle, 1.0), [0, 0, 1]])
    trans_mat = np.identity(3)

    w2 = image_size[0] * 0.5
    h2 = image_size[1] * 0.5

    rot_mat_notranslate = np.matrix(rot_mat[0:2, 0:2])

    tl = (np.array([-w2, h2]) * rot_mat_notranslate).A[0]
    tr = (np.array([w2, h2]) * rot_mat_notranslate).A[0]
    bl = (np.array([-w2, -h2]) * rot_mat_notranslate).A[0]
    br = (np.array([w2, -h2]) * rot_mat_notranslate).A[0]

    x_coords = [pt[0] for pt in [tl, tr, bl, br]]
    x_pos = [x for x in x_coords if x > 0]
    x_neg = [x for x in x_coords if x < 0]

    y_coords = [pt[1] for pt in [tl, tr, bl, br]]
    y_pos = [y for y in y_coords if y > 0]
    y_neg = [y for y in y_coords if y < 0]

    right_bound = max(x_pos)
    left_bound = min(x_neg)
    top_bound = max(y_pos)
    bot_bound = min(y_neg)

    new_w = int(abs(right_bound - left_bound))
    new_h = int(abs(top_bound - bot_bound))
    new_image_size = (new_w, new_h)

    new_midx = new_w * 0.5
    new_midy = new_h * 0.5

    dx = int(new_midx - w2)
    dy = int(new_midy - h2)

    trans_mat = getTranslationMatrix2d(dx, dy)
    affine_mat = (np.matrix(trans_mat) * np.matrix(rot_mat))[0:2, :]
    result = cv2.warpAffine(image, affine_mat, new_image_size, flags=cv2.INTER_LINEAR)

    return result

https://src-bin.com


Answer #1

Rotation et recadrage dans TensorFlow

J'avais personnellement besoin de cette fonction dans TensorFlow et merci pour Aaron Snoswell, je pourrais mettre en œuvre cette fonction.

def _rotate_and_crop(image, output_height, output_width, rotation_degree, do_crop):
    """Rotate the given image with the given rotation degree and crop for the black edges if necessary
    Args:
        image: A `Tensor` representing an image of arbitrary size.
        output_height: The height of the image after preprocessing.
        output_width: The width of the image after preprocessing.
        rotation_degree: The degree of rotation on the image.
        do_crop: Do cropping if it is True.
    Returns:
        A rotated image.
    """

    # Rotate the given image with the given rotation degree
    if rotation_degree != 0:
        image = tf.contrib.image.rotate(image, math.radians(rotation_degree), interpolation='BILINEAR')

        # Center crop to ommit black noise on the edges
        if do_crop == True:
            lrr_width, lrr_height = _largest_rotated_rect(output_height, output_width, math.radians(rotation_degree))
            resized_image = tf.image.central_crop(image, float(lrr_height)/output_height)    
            image = tf.image.resize_images(resized_image, [output_height, output_width], method=tf.image.ResizeMethod.BILINEAR, align_corners=False)

    return image

def _largest_rotated_rect(w, h, angle):
    """
    Given a rectangle of size wxh that has been rotated by 'angle' (in
    radians), computes the width and height of the largest possible
    axis-aligned rectangle within the rotated rectangle.
    Original JS code by 'Andri' and Magnus Hoff from 
    Converted to Python by Aaron Snoswell
    Source: http://.com/questions/16702966/rotate-image-and-crop-out-black-borders
    """

    quadrant = int(math.floor(angle / (math.pi / 2))) & 3
    sign_alpha = angle if ((quadrant & 1) == 0) else math.pi - angle
    alpha = (sign_alpha % math.pi + math.pi) % math.pi

    bb_w = w * math.cos(alpha) + h * math.sin(alpha)
    bb_h = w * math.sin(alpha) + h * math.cos(alpha)

    gamma = math.atan2(bb_w, bb_w) if (w < h) else math.atan2(bb_w, bb_w)

    delta = math.pi - alpha - gamma

    length = h if (w < h) else w

    d = length * math.cos(alpha)
    a = d * math.sin(alpha) / math.sin(delta)

    y = a * math.cos(gamma)
    x = y * math.tan(gamma)

    return (
        bb_w - 2 * x,
        bb_h - 2 * y
    )

Si vous avez besoin de plus d'implémentation de l'exemple et de la visualisation dans TensorFlow, vous pouvez utiliser ce référentiel . J'espère que cela pourrait être utile à d'autres personnes.


Answer #2

Ainsi, après avoir étudié de nombreuses solutions revendiquées, j'ai finalement trouvé une méthode qui fonctionne; La réponse par Andri et Magnus Hoff sur Calculer le plus grand rectangle dans un rectangle tourné .

Le code Python ci-dessous contient la méthode d'intérêt - largest_rotated_rect - et une courte démo.

import math
import cv2
import numpy as np


def rotate_image(image, angle):
    """
    Rotates an OpenCV 2 / NumPy image about it's centre by the given angle
    (in degrees). The returned image will be large enough to hold the entire
    new image, with a black background
    """

    # Get the image size
    # No that's not an error - NumPy stores image matricies backwards
    image_size = (image.shape[1], image.shape[0])
    image_center = tuple(np.array(image_size) / 2)

    # Convert the OpenCV 3x2 rotation matrix to 3x3
    rot_mat = np.vstack(
        [cv2.getRotationMatrix2D(image_center, angle, 1.0), [0, 0, 1]]
    )

    rot_mat_notranslate = np.matrix(rot_mat[0:2, 0:2])

    # Shorthand for below calcs
    image_w2 = image_size[0] * 0.5
    image_h2 = image_size[1] * 0.5

    # Obtain the rotated coordinates of the image corners
    rotated_coords = [
        (np.array([-image_w2,  image_h2]) * rot_mat_notranslate).A[0],
        (np.array([ image_w2,  image_h2]) * rot_mat_notranslate).A[0],
        (np.array([-image_w2, -image_h2]) * rot_mat_notranslate).A[0],
        (np.array([ image_w2, -image_h2]) * rot_mat_notranslate).A[0]
    ]

    # Find the size of the new image
    x_coords = [pt[0] for pt in rotated_coords]
    x_pos = [x for x in x_coords if x > 0]
    x_neg = [x for x in x_coords if x < 0]

    y_coords = [pt[1] for pt in rotated_coords]
    y_pos = [y for y in y_coords if y > 0]
    y_neg = [y for y in y_coords if y < 0]

    right_bound = max(x_pos)
    left_bound = min(x_neg)
    top_bound = max(y_pos)
    bot_bound = min(y_neg)

    new_w = int(abs(right_bound - left_bound))
    new_h = int(abs(top_bound - bot_bound))

    # We require a translation matrix to keep the image centred
    trans_mat = np.matrix([
        [1, 0, int(new_w * 0.5 - image_w2)],
        [0, 1, int(new_h * 0.5 - image_h2)],
        [0, 0, 1]
    ])

    # Compute the tranform for the combined rotation and translation
    affine_mat = (np.matrix(trans_mat) * np.matrix(rot_mat))[0:2, :]

    # Apply the transform
    result = cv2.warpAffine(
        image,
        affine_mat,
        (new_w, new_h),
        flags=cv2.INTER_LINEAR
    )

    return result


def largest_rotated_rect(w, h, angle):
    """
    Given a rectangle of size wxh that has been rotated by 'angle' (in
    radians), computes the width and height of the largest possible
    axis-aligned rectangle within the rotated rectangle.

    Original JS code by 'Andri' and Magnus Hoff from 

    Converted to Python by Aaron Snoswell
    """

    quadrant = int(math.floor(angle / (math.pi / 2))) & 3
    sign_alpha = angle if ((quadrant & 1) == 0) else math.pi - angle
    alpha = (sign_alpha % math.pi + math.pi) % math.pi

    bb_w = w * math.cos(alpha) + h * math.sin(alpha)
    bb_h = w * math.sin(alpha) + h * math.cos(alpha)

    gamma = math.atan2(bb_w, bb_w) if (w < h) else math.atan2(bb_w, bb_w)

    delta = math.pi - alpha - gamma

    length = h if (w < h) else w

    d = length * math.cos(alpha)
    a = d * math.sin(alpha) / math.sin(delta)

    y = a * math.cos(gamma)
    x = y * math.tan(gamma)

    return (
        bb_w - 2 * x,
        bb_h - 2 * y
    )


def crop_around_center(image, width, height):
    """
    Given a NumPy / OpenCV 2 image, crops it to the given width and height,
    around it's centre point
    """

    image_size = (image.shape[1], image.shape[0])
    image_center = (int(image_size[0] * 0.5), int(image_size[1] * 0.5))

    if(width > image_size[0]):
        width = image_size[0]

    if(height > image_size[1]):
        height = image_size[1]

    x1 = int(image_center[0] - width * 0.5)
    x2 = int(image_center[0] + width * 0.5)
    y1 = int(image_center[1] - height * 0.5)
    y2 = int(image_center[1] + height * 0.5)

    return image[y1:y2, x1:x2]


def demo():
    """
    Demos the largest_rotated_rect function
    """

    image = cv2.imread("lenna_rectangle.png")
    image_height, image_width = image.shape[0:2]

    cv2.imshow("Original Image", image)

    print "Press [enter] to begin the demo"
    print "Press [q] or Escape to quit"

    key = cv2.waitKey(0)
    if key == ord("q") or key == 27:
        exit()

    for i in np.arange(0, 360, 0.5):
        image_orig = np.copy(image)
        image_rotated = rotate_image(image, i)
        image_rotated_cropped = crop_around_center(
            image_rotated,
            *largest_rotated_rect(
                image_width,
                image_height,
                math.radians(i)
            )
        )

        key = cv2.waitKey(2)
        if(key == ord("q") or key == 27):
            exit()

        cv2.imshow("Original Image", image_orig)
        cv2.imshow("Rotated Image", image_rotated)
        cv2.imshow("Cropped Image", image_rotated_cropped)

    print "Done"


if __name__ == "__main__":
    demo()

Placez simplement cette image (recadrée pour montrer qu'elle fonctionne avec des images non carrées) dans le même répertoire que le fichier ci-dessus, puis exécutez-la.


Answer #3

Félicitations pour le bon travail! Je voulais utiliser votre code dans OpenCV avec la bibliothèque C ++, donc j'ai fait la conversion qui suit. Peut-être que cette approche pourrait être utile à d'autres personnes.

#include <iostream>
#include <opencv.hpp>

#define PI 3.14159265359

using namespace std;

double degree_to_radian(double angle)
{
    return angle * PI / 180;
}

cv::Mat rotate_image (cv::Mat image, double angle)
{
    // Rotates an OpenCV 2 image about its centre by the given angle
    // (in radians). The returned image will be large enough to hold the entire
    // new image, with a black background

    cv::Size image_size = cv::Size(image.rows, image.cols);
    cv::Point image_center = cv::Point(image_size.height/2, image_size.width/2);

    // Convert the OpenCV 3x2 matrix to 3x3
    cv::Mat rot_mat = cv::getRotationMatrix2D(image_center, angle, 1.0);
    double row[3] = {0.0, 0.0, 1.0};
    cv::Mat new_row = cv::Mat(1, 3, rot_mat.type(), row);
    rot_mat.push_back(new_row);


    double slice_mat[2][2] = {
        {rot_mat.col(0).at<double>(0), rot_mat.col(1).at<double>(0)},
        {rot_mat.col(0).at<double>(1), rot_mat.col(1).at<double>(1)}
    };

    cv::Mat rot_mat_nontranslate = cv::Mat(2, 2, rot_mat.type(), slice_mat);

    double image_w2 = image_size.width * 0.5;
    double image_h2 = image_size.height * 0.5;

    // Obtain the rotated coordinates of the image corners
    std::vector<cv::Mat> rotated_coords;

    double image_dim_d_1[2] = { -image_h2, image_w2 };
    cv::Mat image_dim = cv::Mat(1, 2, rot_mat.type(), image_dim_d_1);
    rotated_coords.push_back(cv::Mat(image_dim * rot_mat_nontranslate));


    double image_dim_d_2[2] = { image_h2, image_w2 };
    image_dim = cv::Mat(1, 2, rot_mat.type(), image_dim_d_2);
    rotated_coords.push_back(cv::Mat(image_dim * rot_mat_nontranslate));


    double image_dim_d_3[2] = { -image_h2, -image_w2 };
    image_dim = cv::Mat(1, 2, rot_mat.type(), image_dim_d_3);
    rotated_coords.push_back(cv::Mat(image_dim * rot_mat_nontranslate));


    double image_dim_d_4[2] = { image_h2, -image_w2 };
    image_dim = cv::Mat(1, 2, rot_mat.type(), image_dim_d_4);
    rotated_coords.push_back(cv::Mat(image_dim * rot_mat_nontranslate));


    // Find the size of the new image
    vector<double> x_coords, x_pos, x_neg;
    for (int i = 0; i < rotated_coords.size(); i++)
    {
        double pt = rotated_coords[i].col(0).at<double>(0);
        x_coords.push_back(pt);
        if (pt > 0)
            x_pos.push_back(pt);
        else
            x_neg.push_back(pt);
    }

    vector<double> y_coords, y_pos, y_neg;
    for (int i = 0; i < rotated_coords.size(); i++)
    {
        double pt = rotated_coords[i].col(1).at<double>(0);
        y_coords.push_back(pt);
        if (pt > 0)
            y_pos.push_back(pt);
        else
            y_neg.push_back(pt);
    }


    double right_bound = *max_element(x_pos.begin(), x_pos.end());
    double left_bound = *min_element(x_neg.begin(), x_neg.end());
    double top_bound = *max_element(y_pos.begin(), y_pos.end());
    double bottom_bound = *min_element(y_neg.begin(), y_neg.end());

    int new_w = int(abs(right_bound - left_bound));
    int new_h = int(abs(top_bound - bottom_bound));

    // We require a translation matrix to keep the image centred
    double trans_mat[3][3] = {
        {1, 0, int(new_w * 0.5 - image_w2)},
        {0, 1, int(new_h * 0.5 - image_h2)},
        {0, 0, 1},
    };


    // Compute the transform for the combined rotation and translation
    cv::Mat aux_affine_mat = (cv::Mat(3, 3, rot_mat.type(), trans_mat) * rot_mat);
    cv::Mat affine_mat = cv::Mat(2, 3, rot_mat.type(), NULL);
    affine_mat.push_back(aux_affine_mat.row(0));
    affine_mat.push_back(aux_affine_mat.row(1));

    // Apply the transform
    cv::Mat output;
    cv::warpAffine(image, output, affine_mat, cv::Size(new_h, new_w), cv::INTER_LINEAR);

    return output;
}

cv::Size largest_rotated_rect(int h, int w, double angle)
{
    // Given a rectangle of size wxh that has been rotated by 'angle' (in
    // radians), computes the width and height of the largest possible
    // axis-aligned rectangle within the rotated rectangle.

    // Original JS code by 'Andri' and Magnus Hoff from 

    // Converted to Python by Aaron Snoswell (https://.com/questions/16702966/rotate-image-and-crop-out-black-borders)
    // Converted to C++ by Eliezer Bernart

    int quadrant = int(floor(angle/(PI/2))) & 3;
    double sign_alpha = ((quadrant & 1) == 0) ? angle : PI - angle;
    double alpha = fmod((fmod(sign_alpha, PI) + PI), PI);

    double bb_w = w * cos(alpha) + h * sin(alpha);
    double bb_h = w * sin(alpha) + h * cos(alpha);

    double gamma = w < h ? atan2(bb_w, bb_w) : atan2(bb_h, bb_h);

    double delta = PI - alpha - gamma;

    int length = w < h ? h : w;

    double d = length * cos(alpha);
    double a = d * sin(alpha) / sin(delta);
    double y = a * cos(gamma);
    double x = y * tan(gamma);

    return cv::Size(bb_w - 2 * x, bb_h - 2 * y);
}

// for those interested in the actual optimum - contributed by coproc
#include <algorithm>
cv::Size really_largest_rotated_rect(int h, int w, double angle)
{
  // Given a rectangle of size wxh that has been rotated by 'angle' (in
  // radians), computes the width and height of the largest possible
  // axis-aligned rectangle within the rotated rectangle.
  if (w <= 0 || h <= 0)
    return cv::Size(0,0);

  bool width_is_longer = w >= h;
  int side_long = w, side_short = h;
  if (!width_is_longer)
    std::swap(side_long, side_short);

  // since the solutions for angle, -angle and pi-angle are all the same,
  // it suffices to look at the first quadrant and the absolute values of sin,cos:
  double sin_a = fabs(math.sin(angle)), cos_a = fabs(math.cos(angle));
  double wr,hr;
  if (side_short <= 2.*sin_a*cos_a*side_long)
  {
    // half constrained case: two crop corners touch the longer side,
    // the other two corners are on the mid-line parallel to the longer line
    x = 0.5*side_short;
    wr = x/sin_a;
    hr = x/cos_a;
    if (!width_is_longer)
      std::swap(wr,hr);
  }
  else
  { 
    // fully constrained case: crop touches all 4 sides
    double cos_2a = cos_a*cos_a - sin_a*sin_a;
    wr = (w*cos_a - h*sin_a)/cos_2a;
    hr = (h*cos_a - w*sin_a)/cos_2a;
  }

  return cv::Size(wr,hr);
}

cv::Mat crop_around_center(cv::Mat image, int height, int width)
{
    // Given a OpenCV 2 image, crops it to the given width and height,
    // around it's centre point

    cv::Size image_size = cv::Size(image.rows, image.cols);
    cv::Point image_center = cv::Point(int(image_size.height * 0.5), int(image_size.width * 0.5));

    if (width > image_size.width)
        width = image_size.width;

    if (height > image_size.height)
        height = image_size.height;

    int x1 = int(image_center.x - width  * 0.5);
    int x2 = int(image_center.x + width  * 0.5);
    int y1 = int(image_center.y - height * 0.5);
    int y2 = int(image_center.y + height * 0.5);


    return image(cv::Rect(cv::Point(y1, x1), cv::Point(y2,x2)));
}

void demo(cv::Mat image)
{
    // Demos the largest_rotated_rect function
    int image_height = image.rows;
    int image_width = image.cols;

    for (float i = 0.0; i < 360.0; i+=0.5)
    {
        cv::Mat image_orig = image.clone();
        cv::Mat image_rotated = rotate_image(image, i);

        cv::Size largest_rect = largest_rotated_rect(image_height, image_width, degree_to_radian(i));
        // for those who trust math (added by coproc):
        cv::Size largest_rect2 = really_largest_rotated_rect(image_height, image_width, degree_to_radian(i));
        cout << "area1 = " << largest_rect.height * largest_rect.width << endl;
        cout << "area2 = " << largest_rect2.height * largest_rect2.width << endl;

        cv::Mat image_rotated_cropped = crop_around_center(
                    image_rotated,
                    largest_rect.height,
                    largest_rect.width
                    );

        cv::imshow("Original Image", image_orig);
        cv::imshow("Rotated Image", image_rotated);
        cv::imshow("Cropped image", image_rotated_cropped);

        if (char(cv::waitKey(15)) == 'q')
            break;
    }

}

int main (int argc, char* argv[])
{
    cv::Mat image = cv::imread(argv[1]);

    if (image.empty())
    {
        cout << "> The input image was not found." << endl;
        exit(EXIT_FAILURE);
    }

    cout << "Press [s] to begin or restart the demo" << endl;
    cout << "Press [q] to quit" << endl;

    while (true)
    {
        cv::imshow("Original Image", image);
        char opt = char(cv::waitKey(0));
        switch (opt) {
        case 's':
            demo(image);
            break;
        case 'q':
            return EXIT_SUCCESS;
        default:
            break;
        }
    }

    return EXIT_SUCCESS;
}

Answer #4

Il existe un moyen facile de prendre soin de ce problème qui utilise un autre module appelé PIL (utile seulement si vous acceptez de ne pas utiliser opencv)

Le code ci-dessous fait exactement la même chose et fait pivoter n'importe quelle image de telle manière que vous n'obtiendrez pas les pixels noirs

from PIL import Image

def array_to_img(x, scale=True):
    x = x.transpose(1, 2, 0) 
    if scale:
        x += max(-np.min(x), 0)
        x /= np.max(x)
        x *= 255
    if x.shape[2] == 3:
        return Image.fromarray(x.astype("uint8"), "RGB")
    else:
        return Image.fromarray(x[:,:,0].astype("uint8"), "L")



def img_to_array(img):
    x = np.asarray(img, dtype='float32')
    if len(x.shape)==3:
        # RGB: height, width, channel -> channel, height, width
        x = x.transpose(2, 0, 1)
    else:
        # grayscale: height, width -> channel, height, width
        x = x.reshape((1, x.shape[0], x.shape[1]))
    return x



if __name__ == "__main__":
    # Calls a function to convert image to array
    image_array = img_to_array(image_name)
    # Calls the function to rotate the image by given angle
    rotated_image =  array_to_img(random_rotation(image_array, rotation_angle))

    # give the location where you want to store the image
    rotated_image_name=<location_of_the_image_>+'roarted_image.png'
    # Saves the image in the mentioned location
    rotated_image.save(rotated_image_name)

Answer #5

Les maths derrière cette solution / implémentation sont équivalentes à cette solution d'une question analogue , mais les formules sont simplifiées et évitent les singularités. C'est du code python avec la même interface que largest_rotated_rect de l'autre solution, mais donnant une plus grande surface dans presque tous les cas (toujours l'optimum prouvé):

def rotatedRectWithMaxArea(w, h, angle):
  """
  Given a rectangle of size wxh that has been rotated by 'angle' (in
  radians), computes the width and height of the largest possible
  axis-aligned rectangle (maximal area) within the rotated rectangle.
  """
  if w <= 0 or h <= 0:
    return 0,0

  width_is_longer = w >= h
  side_long, side_short = (w,h) if width_is_longer else (h,w)

  # since the solutions for angle, -angle and 180-angle are all the same,
  # if suffices to look at the first quadrant and the absolute values of sin,cos:
  sin_a, cos_a = abs(math.sin(angle)), abs(math.cos(angle))
  if side_short <= 2.*sin_a*cos_a*side_long or abs(sin_a-cos_a) < 1e-10:
    # half constrained case: two crop corners touch the longer side,
    #   the other two corners are on the mid-line parallel to the longer line
    x = 0.5*side_short
    wr,hr = (x/sin_a,x/cos_a) if width_is_longer else (x/cos_a,x/sin_a)
  else:
    # fully constrained case: crop touches all 4 sides
    cos_2a = cos_a*cos_a - sin_a*sin_a
    wr,hr = (w*cos_a - h*sin_a)/cos_2a, (h*cos_a - w*sin_a)/cos_2a

  return wr,hr

Voici une comparaison de la fonction avec l'autre solution:

>>> wl,hl = largest_rotated_rect(1500,500,math.radians(20))
>>> print (wl,hl),', area=',wl*hl
(828.2888697391496, 230.61639227890998) , area= 191016.990904
>>> wm,hm = rotatedRectWithMaxArea(1500,500,math.radians(20))
>>> print (wm,hm),', area=',wm*hm
(730.9511000407718, 266.044443118978) , area= 194465.478358

Avec l'angle a dans [0,pi/2[ le cadre de délimitation de l'image pivotée (largeur w , hauteur h ) a ces dimensions:

  • largeur w_bb = w*cos(a) + h*sin(a)
  • hauteur h_bb = w*sin(a) + h*cos(a)

Si w_r , h_r sont la largeur et la hauteur optimales calculées de l'image recadrée, alors les encarts de la boîte englobante sont:

  • dans le sens horizontal: (w_bb-w_r)/2
  • dans la direction verticale: (h_bb-h_r)/2

Preuve:

La recherche du rectangle aligné sur l'axe entre deux lignes parallèles ayant une surface maximale est un problème d'optimisation avec un paramètre, par exemple x comme dans cette figure:

Soit s la distance entre les deux lignes parallèles (il apparaîtra que c'est le côté le plus court du rectangle pivoté). Alors les côtés a , b du rectangle recherché ont un rapport constant avec x , sx , resp., À savoir x = a sin α et (sx) = b cos α:

Donc maximiser la surface a*b signifie maximiser x*(sx) . A cause du "théorème de la hauteur" pour les triangles rectangles, nous connaissons x*(sx) = p*q = h*h . Donc la surface maximale est atteinte en x = sx = s/2 , c'est-à-dire que les deux coins E, G entre les lignes parallèles sont sur la ligne médiane:

Cette solution n'est valide que si ce rectangle maximal s'inscrit dans le rectangle pivoté. Par conséquent, l' EG diagonal ne doit pas être plus long que l'autre côté l du rectangle tourné. Depuis

EG = AF + DH = s / 2 * (cot α + tan α) = s / (2 * sin α cos α) = s / sin 2 α

nous avons la condition s ≤ l sin 2 α, où s et l sont le côté le plus court et le plus long du rectangle pivoté.

Dans le cas de s> l sin 2 α, le paramètre x doit être plus petit (que s / 2) et tous les coins du rectangle recherché sont chacun d'un côté du rectangle pivoté. Cela conduit à l'équation

x * lit α + (sx) * tan α = l

donnant x = sin α (l cos α - s sin α) / cos 2 α. De a = x / sin α et b = (sx) / cos α nous obtenons les formules utilisées ci-dessus.


Answer #6

Solution rapide

Merci à coproc pour sa formidable solution. Voici le code dans swift

// Given a rectangle of size.width x size.height that has been rotated by 'angle' (in
// radians), computes the width and height of the largest possible
// axis-aligned rectangle (maximal area) within the rotated rectangle.
func rotatedRectWithMaxArea(size: CGSize, angle: CGFloat) -> CGSize {
    let w = size.width
    let h = size.height

    if(w <= 0 || h <= 0) {
        return CGSize.zero
    }

    let widthIsLonger = w >= h
    let (sideLong, sideShort) = widthIsLonger ? (w, h) : (w, h)

    // since the solutions for angle, -angle and 180-angle are all the same,
    // if suffices to look at the first quadrant and the absolute values of sin,cos:
    let (sinA, cosA) = (sin(angle), cos(angle))
    if(sideShort <= 2*sinA*cosA*sideLong || abs(sinA-cosA) < 1e-10) {
        // half constrained case: two crop corners touch the longer side,
        // the other two corners are on the mid-line parallel to the longer line
        let x = 0.5*sideShort
        let (wr, hr) = widthIsLonger ? (x/sinA, x/cosA) : (x/cosA, x/sinA)
        return CGSize(width: wr, height: hr)
    } else {
        // fully constrained case: crop touches all 4 sides
        let cos2A = cosA*cosA - sinA*sinA
        let (wr, hr) = ((w*cosA - h*sinA)/cos2A, (h*cosA - w*sinA)/cos2A)
        return CGSize(width: wr, height: hr)
    }
}




aabb