Find the largest rectangle that fits inside a polygon

Question

I need to find the largest rectangle that can fit inside any polygon,

what i tried is dividing the svg to 2d grid and loop the 2d array to see if the current grid cell intersects with the polygon to create a new 2d binary array where intersection is 1 else 0

now i need to find the largest rectangle from that 2d array AND more importantly its location

as example:

if the 2d array is like this, i need to find the largest rect in that array and its x1,y1 (start i,j) and x2,y2 (end i,j).

axis aligned or any oriented inscribed rectangle? for oriented one look at this [2D OBB](https://stackoverflow.com/a/42997918/2521214) it finds the smallest outscribed rectangle but I think if you change the search condition it should be modified to find largest inscribed one ... SQUARE_MAP (2D version of 3D CUBE_MAP) is your friend ... — Spektre, Apr 03 '22 at 09:14
@Spektre thx for your reply.. yes axises are aligned not oriented — Sherif Salah, Apr 03 '22 at 13:52
@Spektre area, i can almost get the largest rectangle by area now, but the strugle is to find its location, i can't get to return x and y for it, i'm using the largest area in histogram algorithm and it only returns the area (mostly correct).. i need the coords and need to know if there is a better solution — Sherif Salah, Apr 03 '22 at 20:40

Spektre · Answer 1 · 2022-04-04T06:11:23.427

well you can brute force the location and scan for the size which will be O(n^6) if n is the avg size of side of your map in pixels ...

The location might be speed up by search (accepting not strictly sorted data) for example like this:

How approximation search works

which would lead to ~O(n^4.log^2(n)). But beware the search must be configured properly in order to not skip solution ... The size search can be improved too by using similar technique like I did in here:

2D OBB

Just use different metric so I would create LUT tables of start and end positions for each x and y (4 LUT tables) which will speed up the search leading to ~O(n^2.log^2(n)) while creation of LUT is O(n^2). btw the same LUTs I sometimes use in OCR like here (last 2 images):

OCR and character similarity

Now problem with this approach is it can not handle concave polygon correctly as there might be more edges per x,y than just 2. So to remedy that you would need to have more LUTs and use them based on position in polygon (divide polygon to "convex" areas)

So putting all these together would look something like this:

approx loop (center x) // ~O(log(n))
 approx loop (center y) // ~O(log(n))
  grow loop (square size to max using) LUT // O(n)
    {
    grow loop (x size to max while decreasing original square y size) // O(n)
    grow loop (y size to max while decreasing original square x size) // O(n)
    use bigger from the above 2 rectangles
    }

Just do not forget to use area of polygon / area of rectangle as approximation error value. This algo is resulting in ~O(n^2.log^2(n)) which is not great but still doable.

Another option is convert your polygon to squares, and use bin-packing and or graph and or backtracking techniques to grow to biggest rectangle ... but those are not my cup of tea so I am not confident enough to create answer about them.

Find the largest rectangle that fits inside a polygon

1 Answers1