Best way to find largest square that fits in a polygon drawn on an image

Question

I'm using OpenCV to match a bunch of viewpoints into a panorama. The result is a bunch of images on a black background (sort of a polygonal shape). What I want to do is crop this polygon so that there is no black in the resulting image. Is there a good algorithm to do this?

The naive way I am thinking is to start with a small square in the middle of the image and expand upwards until I hit black, then expand left and right.

The solution I want is the one that maximizes the total area of the filled region.

EDIT: The polygon is concave so we need to check for that -- I think the O(N^2) algorithm of trying every vertex pair is feasible as N is small. But we need to check that the region bound is filled which I guess could be done in O(N) by checking every vertex to see if it lies within the bounds of the rectangle defined by the vertex pair we picked. This gives us a O(N^3) algorithm

Answer 1

The naive solution may not work well because usually making the rectangle taller will limit its width, so you will not get the optimal solution.

If you do not have too many vertices on the polygon, the following might work: try picking every combination of top and bottom edges. To simplify, assume that they will always include one of the vertices of the polygon. When the top and bottom are specified, the sides can be determined, so for each pair of top/bottom you can calculate the area. Pick the solution that gives the largest area.

The simplification above may give suboptimal results, but it shouldn't be too bad.