Largest rectangle in a polygon

on 16 Dec 2006 by Mukund (@muks)

GIMP now has working code to find the largest rectangle in the quadrilateral (aligned with the XY axes) which results after a transform (rotate, perspective, etc.). As an example, when a user rotates an image, she can decide to automatically crop the image to an rectangle aligned with the canvas so that no transparent areas are introduced (an often used use-case which is used usually often ;). A UI for using this feature will be available soon.

The shapes below are from a GTK+ test program which uses Cairo to draw, but when I took screenshots, the window decoration disappeared (maybe because of desktop effects). The black polygon is the transformed quadrilateral and the green rectangle is the computed result. The function also accepts an aspect ratio to provide a properly sized rectangle.

Example 1 of computing largest rectangle in a quadrilateral Example 2 of computing largest rectangle in a quadrilateral Example 3 of computing largest rectangle in a quadrilateral Example 4 of computing largest rectangle in a quadrilateral Example 5 of computing largest rectangle in a quadrilateral