Find largest rectangle inside polygon - Python

Question

Is there an easy way to the maximum upright rectangle that fits inside a shape? I'm using OpenCV.

http://docs.opencv.org/master/dd/d49/tutorial_py_contour_features.html#gsc.tab=0

How do I crop to largest interior bounding box in OpenCV?

Answer 1

This is not the most effecient implementation but it works :)

topleft_corner = []; 
bottomright_corner = []; 
rectangle_heights= []; 
rectangle_areas = [];
#lets start scanning from the left
# and find the outer two points in each vertical line
for i in range(0,mask.shape[1]):
    line = mask[:,i]
    foreground_indecies = np.where(line == 255)

    top_p1 = foreground_indecies[0][0]
    bottom_p1 = foreground_indecies[0][-1]
    line1_length = bottom_p1 - top_p1
    #scan the mask fromt the right side
    for j in range(mask.shape[1]-1,i+2,-1):
        line2 = mask[:,j]
        foreground_indecies = np.where(line2 == 255)
        top_p2 = foreground_indecies[0][0]
        bottom_p2 = foreground_indecies[0][-1]
        #find length of right line
        line2_length = bottom_p2 - top_p2

        #If the two lines are equal then we have an upright rectangle  :)
        if line1_length == line2_length and i != j :
            topleft_corner.append([i,top_p1])
            bottomright_corner.append([j,bottom_p2])
            rectangle_heights.append(line1_length)
            rectangle_areas.append((j-i) *(line1_length))


#Now we have the list of all possible rectangle heights and their correpsonding pionts
#You can then decide how to choose the right rectangle
#A - By how far it extends vertically
#B - By area size
#I am going to demonstrate how to do B
max_area_index = np.argmax(np.array(rectangle_areas))
topleft_pt  = tuple(topleft_corner[max_area_index])
bottomright_pt= tuple(bottomright_corner[max_area_index])
rgb_mask = cv2.cvtColor(mask, cv2.COLOR_GRAY2BGR)
color = (255, 0, 0) 
# Line thickness of 2 px 
thickness = 2 
# Using cv2.rectangle() method 
# Draw a rectangle with blue line borders of thickness of 2 px 
image = cv2.rectangle(rgb_mask, topleft_pt, bottomright_pt, color, thickness)

Answer 2

You can use the largestinteriorrectangle package:

pip install largestinteriorrectangle

and then

import largestinteriorrectangle as lir
import cv2 as cv

grid = cv.imread("mask.png", 0)
grid = grid > 0
rect = lir.largest_interior_rectangle(grid)