Finding largest inscribed rectangle in polygon

Question

I have a bunch of images with labeled polygons marked in red (255,0,0):

I want to extract the bounding box but inside the polygon as shown with the blue rectangle:

OpenCV cv.boundingRect gives me the outer bounding box but how to extract the inner bounding box?

Answer 1

This inscribed rectangle problem is a bit more complex than outer rectangle. A related general case is polygon inside polygon - the polygon containment problem is described in this 1983 paper. This algorithm determines whether a polygon with n points can fit another polygon with m points with a complexity of O(n^3 m^3(n+m)log(n+m)) complexity.

The restricted case of "Largest Inscribed Rectangles in Geometric Convex Sets" can be done much faster. Have a look at this 2019 paper (DeepAI Link) They consider the problem of finding inscribed boxes and axis-aligned inscribed boxes of maximum volume, inside a compact and solid convex set.

Here is another older easier to understand algorithm for convex polygons with good visualizations.

Here is a MATLAB implementation. but the code lacks comments and is a bit difficult to understand.

Here is a python implementation but a bit dated.