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

Try distance transform if working with pixels, find the maximum point and then based on this position find maximum square within region by expanding square/rectangle as you mention

Answer 2

Seems like a line sweep algorithm would work well. Start with, say, a vertical line on the left edge and move it to the right some x increment at a time. At each stop, look at every line segment of the line that's internal to the polygon. (There could be more than one when it's concave.) Consider sub-line-segments along the line segment.

Then take horizontal lines from each endpoint of the sub-line-segment and find the crossing intersections with the polygon (in both directions) to find the largest rect containing that sub-line-segment.

Performance could be O(n_xn_y²), though you can reduce it with heuristics and adaptive step sizes.

A case that might be missed by too many assumptions or shortcuts is:

+------\    /---+
|       \  /    |
\        \/     /
 \             /
 /             \
/      /\       \
|     /  \      |
+----/    \-----+

Answer 3

Considering the limited number of images likely to be in the panorama, you could use a brute force method and try all possible combinations. The user could never tell the difference, and the writing and maintenance of the function would probably be faster. It's just not as interesting that way, though.

Answer 4

Let's assume the polygon is convex on a discrete XY grid. Then the entire shape of the polygon can be represented by an array of (x1,x2) pairs, one for each Y coordinate in the grid. You get this array of (x1,x2) pairs by tracing the edges of the polygon.

You know the square has to touch the polygon in two diagonal points at least, either upper-left-lower-right or lower-left-upper-right.

At each left-edge point, you can find the closest point to the right, the closest directly up and directly down, and the closest point on each diagonal, 45 degrees up and down. If the distance on a diagonal is equal or less than any of the rectilinear distances, you have a square that fits in the polygon. There may be more than one, so keep going to find the largest one.

Answer 5

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.