I have an arbitrary shape defined by a binary mask (gray = shape, black = background).
I would like to find a largest possible rectangle containing only gray pixels (such rectangle is pictured in yellow):
The shape is always "one piece" but it is not necessarily convex (not all point pairs on the shape's boundary can be connected by a straight line going through the shape).
Sometimes many of such "maximum rectangles" exist and then further constrains can be introduced, such as:
- Taking the rectangle with its center nearest to shape's center of mass (or center of image)
- Taking rectangle with aspect ratio nearest to a predefined ratio (i.e. 4:3)
My first thought about the algorithm is the following:
- Compute distance transform of the shape and find its center of mass
- Grow square area while it contains only shape's pixels
- Grow the rectangle (originally a square) in width or height while it contains only shape's pixels.
However, I think such algorithm would be slow and would not lead to optimal solution.