How to calculate the largest rectangle in a polyhedron?

Question

Mathematics

There is an image with an affine transformation applied (for example, rotation, or rotation + translation). As a result, some of its parts became empty, since there was nothing to turn there. It is necessary to crop it to a rectangle of the maximum size so as to remove all the void.
.
Algorithmic formulation of the problem.
There is a pixel coordinate grid with a convex polyhedron drawn in it. The vertex coordinates are unknown, but all pixels inside the polyhedron are known to be true, and all outside are false. The origin of coordinates is known - the point (0,0) and the end of coordinates (xMax, yMax).
We need an algorithm (it can be heuristic, the main thing is to be fast) that would give the coordinates of the vertices of the largest rectangle inscribed in this polyhedron. An important condition is that the sides of the rectangle are parallel to the coordinate axes, that is, any rotation is excluded.
There is a similar general level problem with an arbitrary matrix www.drdobbs.com/database/the-maximal-rectangle-pro... but I'm sure there is a much faster solution for a convex polygon.

Answer 1

You can try something like a binary search. Those. first of all, take a horizontal line from the middle of the upper half, and the second from the middle of the lower half. Next, find the left and right verticals along these horizontals, at least by simply scanning the points, i.e. to "feel" the edges of the image. And further - by recursion we divide the middle of the upper half into the upper and lower, the same with the lower half, the direction of the search for the vertical boundaries of the image is already known. Using the branch and boundary method, we cut off the options when the found area begins to decrease. Something like this.

Answer 2

I would first find the positions of the clipping lines.
For example, for each corner, I would find the intersection points of the color image with the borders of the image (the first ones are true). Based on these points, for each line, you can build its formula Ax + By + C = 0 (moreover, 2 lines will be parallel and 2 perpendicular, i.e. I will differ only in the constant C and the sign A or B)
Further, the task was to be easy - this is the maximization of the area of ​​a rectangle whose corners lie on these 4 lines. 100% such a problem is already described somewhere in the literature, in the extreme case, solve it with iterative methods.

Answer 3

You know the angle of rotation. Therefore, you can build 4 vectors: from the center to each corner. And with some step approach the center along these vectors. The larger the step, the less time, but the rougher it will be to calculate. You end up with 4 points of the rectangle. Looking for the smallest length. Adjust the rest to its length. Maybe there is something faster. Didn't check.

Answer 4

Come on ... I hope everyone can count derivatives.
Now let's take a closer look at the rectangle. How is its area calculated? Oh yeah, S = a*b, that's 7th grade geometry, if not 4th grade math.
Ok, now you can look at the polygon in which you need to fit the rectangle. Well, he's nasty, yes, but some things are known. Namely, "straight cuts", as @begemot_sun told us , in general, in this problem, it is better to store a polygon in the form of straight lines. Well, that’s not the point, it’s just that there will be a little more calculations. Ok, now what do we do. We are building a function. Yes, yes - the most banal function. The function S(\phi) = a(\phi)*b(\phi). How to get it - I'll leave it to you, there is some geometry of the 7th grade.
Well, yes, but the question is, what to do with it at all? Attention answer - searching for an extremum in the general case is a difficult task =) Even wolframalpha is powerless here (however, specifically in this case it is even impossible). So here only optimizations take place - the gradient descent method or the "annealing" method . Google it, read it, implement it.
Also, it can become so suddenly that the problem is resolved in a general way. Well, that is, when you look for a derivative, try not to substitute values, but just them. It may well be that the problem has a simple analytical solution.
PS Do not try to ask someone to solve the problem for you on such resources. First, it's bad manners. Secondly, the resource is here to suggest a solution to the problem, but not to solve it INSTEAD of you. This particular case will require 10 hours of remembering a high school matan, which is not very pleasant. Considering the salary of 2k/hour, I think it will be a little expensive.
UPD. It suddenly dawned on me that the addiction would be a little more difficult. In the sense that it will not just be S(\phi), but S(\phi, a) = a*b(\phi, a). Well, yes, the task will be more difficult. That is, this is already the most for nothing there is a matan - the maximum function of two variables.