This problem can be stated as the find the largest rectangle inscribed in a non-convex polygon.
An approximate solution can be found at this link.
This problem can be formulated also as: for each angle, find the largest rectangle containing only zeros in a matrix, explored in this SO question.
My solution is based on this answer. This will find only axis aligned rectangles, so you can easily rotate the image by a given angle and apply this solution for every angle. My solution is C++, but you can easily port it to Python, since I'm using mostly OpenCV function, or adjust the solution in the above mentioned answer accounting for rotation.
Here we are:
#include <opencv2\opencv.hpp> #include <iostream> using namespace cv; using namespace std; // https://stackoverflow.com/a/30418912/5008845 Rect findMinRect(const Mat1b& src) { Mat1f W(src.rows, src.cols, float(0)); Mat1f H(src.rows, src.cols, float(0)); Rect maxRect(0,0,0,0); float maxArea = 0.f; for (int r = 0; r < src.rows; ++r) { for (int c = 0; c < src.cols; ++c) { if (src(r, c) == 0) { H(r, c) = 1.f + ((r>0) ? H(r-1, c) : 0); W(r, c) = 1.f + ((c>0) ? W(r, c-1) : 0); } float minw = W(r,c); for (int h = 0; h < H(r, c); ++h) { minw = min(minw, W(r-h, c)); float area = (h+1) * minw; if (area > maxArea) { maxArea = area; maxRect = Rect(Point(c - minw + 1, r - h), Point(c+1, r+1)); } } } } return maxRect; } RotatedRect largestRectInNonConvexPoly(const Mat1b& src) { // Create a matrix big enough to not lose points during rotation vector<Point> ptz; findNonZero(src, ptz); Rect bbox = boundingRect(ptz); int maxdim = max(bbox.width, bbox.height); Mat1b work(2*maxdim, 2*maxdim, uchar(0)); src(bbox).copyTo(work(Rect(maxdim - bbox.width/2, maxdim - bbox.height / 2, bbox.width, bbox.height))); // Store best data Rect bestRect; int bestAngle = 0; // For each angle for (int angle = 0; angle < 90; angle += 1) { cout << angle << endl; // Rotate the image Mat R = getRotationMatrix2D(Point(maxdim,maxdim), angle, 1); Mat1b rotated; warpAffine(work, rotated, R, work.size()); // Keep the crop with the polygon vector<Point> pts; findNonZero(rotated, pts); Rect box = boundingRect(pts); Mat1b crop = rotated(box).clone(); // Invert colors crop = ~crop; // Solve the problem: "Find largest rectangle containing only zeros in an binary matrix" // https://stackoverflow.com/questions/2478447/find-largest-rectangle-containing-only-zeros-in-an-n%C3%97n-binary-matrix Rect r = findMinRect(crop); // If best, save result if (r.area() > bestRect.area()) { bestRect = r + box.tl(); // Correct the crop displacement bestAngle = angle; } } // Apply the inverse rotation Mat Rinv = getRotationMatrix2D(Point(maxdim, maxdim), -bestAngle, 1); vector<Point> rectPoints{bestRect.tl(), Point(bestRect.x + bestRect.width, bestRect.y), bestRect.br(), Point(bestRect.x, bestRect.y + bestRect.height)}; vector<Point> rotatedRectPoints; transform(rectPoints, rotatedRectPoints, Rinv); // Apply the reverse translations for (int i = 0; i < rotatedRectPoints.size(); ++i) { rotatedRectPoints[i] += bbox.tl() - Point(maxdim - bbox.width / 2, maxdim - bbox.height / 2); } // Get the rotated rect RotatedRect rrect = minAreaRect(rotatedRectPoints); return rrect; } int main() { Mat1b img = imread("path_to_image", IMREAD_GRAYSCALE); // Compute largest rect inside polygon RotatedRect r = largestRectInNonConvexPoly(img); // Show Mat3b res; cvtColor(img, res, COLOR_GRAY2BGR); Point2f points[4]; r.points(points); for (int i = 0; i < 4; ++i) { line(res, points[i], points[(i + 1) % 4], Scalar(0, 0, 255), 2); } imshow("Result", res); waitKey(); return 0; }
The result image is:
NOTE
I'd like to point out that this code is not optimized, so it can probably perform better. For an approximized solution, see here, and the papers reported there.
This answer to a related question put me in the right direction.
