Finding the largest rectangle inside a quadrilateral
===

Lately, I've scanned a lot of album covers in an attempt to digitalize my music collection. The default procedure after scanning is rotating and cropping.

For rotating, the important thing is to find one or more lines of reference. After rotating, the 'normal' lines will be more or less horizontal (or vertical) and the odd lines will be somewhat slanted. Two 'different' rotations can be distinguished:

![Two quadrilaterals][1]

NOTE: The two quadrilaterals are two album covers. You can imagine the two lines in the album covers as two printed lines. All the reference lines are in bold. You might wonder why the album covers aren't just rectangles but note that this image is greatly exagerated. That said, if you've ever looked at album covers closely, you'll notice that they're rarely ever close to a rectangle.


In situation A, it is clear that most of the cover edges are parallel and form 90 degree angles, and/or the printed objects are overly slanted which indicates that the print itself is slanted. In both cases I can better use the cover edges as reference.

In situation B, most of the lines seem irregular and the print seems alright. I then better use the printed objects as reference.

All in all, this is mostly an intuitive process.

Although the aforementioned is not part of the actual problem I thought it would be useful for you to know the background info first. We've now arrived at the cropping step, the part that has always bugged me.

My question is simple: If I must crop any album cover, how can I crop it in such a way that it leaves me with the largest portion of the album cover? Put differently, how can I find the 4 values that together form the largest possible rectangle inside a quadrilateral?

The only condition is that the rectangle must be parallel to the reference lines, i.e. horizontal.


  [1]: http://i.stack.imgur.com/lWPQ0.png