Find Largest Rectangle in Rotated Image

Some time ago I was working with images in Java. I wanted to rotate an image but also crop the image so you do not see any blank areas. When you rotate an image in java it does not crop the blanks areas for you. In my example I will show you how you can use my algorithm to find the best dimensions to crop based on the largest rectangle possible for the rotated image.

To get started I will first show you my original image.

Figure 1. Original image of Purple Swamphen

Now I will rotate my image by 20 degrees. My image has the black blank areas that I do not wish to have in my final image. What I want is a cropped image of the largest rectangle possible in this rotated image.

Figure 2. Rotated image by 20 degrees

There is not just one large rectangle that will fit into the rotated image. There are many possible rectangles, as seen in Figure 3.

Figure 3. Rotated image showing 2 rectangles filling the rotated image

Figure 3 shows the rotated image with 2 inner rectangles filling the inside of the rotated image. Usually we want the largest area rectangle, or possibly the widest or tallest.

Here are 2 examples showing the images we may want. Figure 4 showing the widest rectangle which also has the largest area, and Figure 5 showing the tallest rectangle.

Figure 4. Widest and Largest cropped rectangle from rotated image

Figure 5. Tallest cropped rectangle from rotated image

Here is the algorithm to calculate the largest rectangle in a rotated image.

/**
  * Return a largest Rectangle that will fit in a rotated image
  * @param imgWidth Width of image
  * @param imgHeight Height of Image
  * @param rotAngDeg Rotation angle in degrees
  * @param type 0 = Largest Area, 1 = Smallest Area, 2 = Widest, 3 = Tallest
  * @return
  */
 public static Rectangle getLargestRectangle(double imageWidth, double imageHeight, double rotAngDeg, int type) {
  Rectangle rect = null;
  
  double rotateAngleDeg = rotAngDeg % 180d;
  if (rotateAngleDeg < 0d) {
   rotateAngleDeg += 360d;
   rotateAngleDeg = rotateAngleDeg % 180d;
  }
  double imgWidth = imageWidth;
  double imgHeight = imageHeight;
  
  if (rotateAngleDeg == 0 || rotateAngleDeg == 180) {
   // Angle is 0. No change needed
   rect = new Rectangle(0,0,(int)imgWidth,(int)imgHeight);
   return rect;
  }
  
  if (rotateAngleDeg == 90) {
   // Angle is 90. Width and height swapped
   rect = new Rectangle(0,0,(int)imgHeight,(int)imgWidth);
   return rect;
  }
  
  if (rotateAngleDeg > 90) {
   // Angle > 90 therefore angle = 90 - ("+rotateAngleDeg+" - 90) = "+(90 - (rotateAngleDeg - 90))
   rotateAngleDeg = 90 - (rotateAngleDeg - 90);
  }
  
  double rotateAngle = Math.toRadians(rotateAngleDeg);
  double sinRotAng = Math.sin(rotateAngle);
  double cosRotAng = Math.cos(rotateAngle);
  double tanRotAng = Math.tan(rotateAngle);
  // Point 1 of rotated rectangle
  double x1 = sinRotAng * imgHeight;
  double y1 = 0;
  // Point 2 of rotated rectangle
  double x2 = cosRotAng * imgWidth + x1;
  double y2 = sinRotAng * imgWidth;
  // Point 3 of rotated rectangle
  double x3 = x2 - x1;
  double y3 = y2 + cosRotAng * imgHeight;
  // Point 4 of rotated rectangle
  double x4 = 0;
  double y4 = y3 - y2;
  // MidPoint of rotated image
  double midx = x2 / 2;
  double midy = y3 / 2;
  
  // Angle for new rectangle (based on image width and height)
  double imgAngle = Math.atan(imgHeight / imgWidth);
  double imgRotAngle = Math.atan(imgWidth / imgHeight);
  double tanImgAng = Math.tan(imgAngle);
  double tanImgRotAng = Math.tan(imgRotAngle);
  // X Point for new rectangle on bottom line
  double ibx1 = midy / tanImgAng + midx;
  double ibx2 = midy * tanImgAng + midx;
  
  // First intersecting lines
  // y = ax + b  ,  y = cx + d  ==>  x = (d - b) / (a - c)
  double a = y2 / x3;
  double b = tanRotAng * -x1;
  double c = -imgHeight / imgWidth;
  double d = tanImgAng * ibx1;
  
  // Intersecting point 1
  double ix1 = (d - b) / (a - c);
  double iy1 = a * ix1 + b;
  
  // Second intersecting lines
  c = -imgWidth / imgHeight;
  d = tanImgRotAng * ibx2;
  
  // Intersecting point 2
  double ix2 = (d - b) / (a - c);
  double iy2 = a * ix2 + b;
  
  // Work out smallest rectangle
  double radx1 = Math.abs(midx - ix1);
  double rady1 = Math.abs(midy - iy1);
  double radx2 = Math.abs(midx - ix2);
  double rady2 = Math.abs(midy - iy2);
  // Work out area of rectangles
  double area1 = radx1 * rady1;
  double area2 = radx2 * rady2;
  // Rectangle (x,y,width,height)
  Rectangle rect1 = new Rectangle((int)Math.round(midx-radx1),(int)Math.round(midy-rady1),
    (int)Math.round(radx1*2),(int)Math.round(rady1*2));
  
  // Rectangle (x,y,width,height)
  Rectangle rect2 = new Rectangle((int)Math.round(midx-radx2),(int)Math.round(midy-rady2),
    (int)Math.round(radx2*2),(int)Math.round(rady2*2));
  
  switch (type) {
   case 0: rect = (area1 > area2 ? rect1 : rect2); break;
   case 1: rect = (area1 < area2 ? rect1 : rect2); break;
   case 2: rect = (radx1 > radx2 ? rect1 : rect2); break;
   case 3: rect = (rady1 > rady2 ? rect1 : rect2); break;
  }
  
  return rect;
 }

Here is some code you want want to use for your own testing. It uses JAI for rotating and cropping but really you can use any library for this.

    public static void main(String[] args) throws IOException {
  
     BufferedImage src = ImageIO.read(new File("MyTestImage.jpg"));
     String outType = "jpg";
     int imgWidth = 1280;
     int imgHeight = 851;

     double rotateAngle = 20d;
     BufferedImage rotImg = rotateImage(src, rotateAngle);
     ImageIO.write(rotImg, outType, new File("RotateTest."+outType));
         
     Rectangle rectLargest = getLargestRectangle(imgWidth,imgHeight,rotateAngle,0);
     Rectangle rectTallest = getLargestRectangle(imgWidth,imgHeight,rotateAngle,3);
         
     BufferedImage rotCropImage = cropImage(rotImg, (int)rectLargest.getX(), (int)rectLargest.getY(), (int)rectLargest.getWidth(), (int)rectLargest.getHeight());
     ImageIO.write(rotCropImage, outType, new File("RotateCropTest_LG."+outType));

     rotCropImage = cropImage(rotImg, (int)rectTallest.getX(), (int)rectTallest.getY(), (int)rectTallest.getWidth(), (int)rectTallest.getHeight());
     ImageIO.write(rotCropImage, outType, new File("RotateCropTest_TA."+outType));
    }
        
    public static BufferedImage rotateImage(BufferedImage image, double angle)
    {
     // Gets the angle (converting it to radians).
     float rangle = (float)Math.toRadians(angle);
     // Gets the rotation center.
     float centerX = 0f; float centerY = 0f;
     centerX = image.getWidth()/2f;
     centerY = image.getHeight()/2f;
 
     // Rotates the original image.
     ParameterBlock pb = new ParameterBlock();
     pb.addSource(image);
     pb.add(centerX);
     pb.add(centerY);
     pb.add(rangle);
     pb.add(new InterpolationBilinear());
     // Creates a new, rotated image and uses it on the DisplayJAI component
     RenderedOp result = JAI.create("rotate", pb);
     return result.getAsBufferedImage();
    }
    
    public static BufferedImage cropImage(BufferedImage image, int topLeftX, int topLeftY, int width, int height)
    {
     // Crops the original image.
     ParameterBlock pb = new ParameterBlock();
     pb.addSource(image);
     pb.add((float)topLeftX);
     pb.add((float)topLeftY);
     pb.add((float)width);
     pb.add((float)height);
     // Creates a new, rotated image and uses it on the DisplayJAI component
     RenderedOp result = JAI.create("crop", pb);
     return result.getAsBufferedImage();
    }