Find a small square patch inside an "approxPolyDP" polygon

edit

Filter your mask with a kernel having the size you want to find and then take the maximum response, if this response is not the size of the kernel, there doesn't exist a large enough patch, otherwise you can use its location for a suitable patch.

Code:

import cv2
import numpy as np

# read in your image
mask = cv2.imread('zEBLK2z.jpg', cv2.CV_LOAD_IMAGE_GRAYSCALE)
# make sure the masked part is 1 (not 255)
mask[mask>0] = 1

# make a window with the minimum window size to find
min_s = 16
kernel = np.ones((min_s, min_s),dtype=np.uint8)
# filter the image with this kernel
res = cv2.filter2D(mask, cv2.CV_16S, kernel)

# find the maximum 
m = np.amax(res)
# if the maximum is the area of your window at least
# one location has been found
if m == min_s*min_s:
    mask_color = cv2.cvtColor(mask*255, cv2.cv.CV_GRAY2BGR)
    # show each location where we found the maximum
    # i.e. a possible location for a patch
    mask_color[res == m] = (0,255,0)                       

    # if you are only interested in the first hit use this:
    # find firs index and convert it to coordinates of the mask
    y,x = np.unravel_index(np.argmax(res), mask.shape)
    # could do now other things with this location, 
    # but for now just show it in another color
    mask_color[y:y+min_s,x:x+min_s] = (255,0,0)

    cv2.imwrite('result.png', mask_color)

Result (green: all possible locations, blue the first one):