Algorithm to find the largest empty rectangle amid other polygons

Question

The scenario : There is a rectangular space inside which there are arbitrarily placed polygons of arbitrary orientations. The aim is to find the largest empty rectangle that can be fitted inside the empty regions of the rectangular space. These images below illustrate the scenario with the polygons in blue and the dotted line representing the maximum empty rectangle that can be fitted in each scenario.

The problem : Apparently, finding largest empty rectangles is a well known problem in computational geometry, but the algorithms I found in this area dealt with finding empty rectangles amid points (CGAL has implemented this) and line segments. Is there a way to adapt these existing techniques for my scenario? Or is there a simpler way to do this?

Answer 1

Unfortunately, most of the computational geometry literature with which I am familiar seems to generate beautiful descriptions of algorithms and proofs of their correctness without actually providing implementations. Perhaps this is because the implementations are generally rather involved.

You don't mention what degree of inaccuracy you can tolerate. If you have some tolerance, this answer's for you.

My suggestion is that you turn this hard problem into an easier problem.

1. Find the bounding box of your polygon collection.
2. Divide the bounding box into a grid. The finer the grid the better your accuracy, but the longer it will take to find a solution.
3. Find how much area of each grid cell (cast as a rectangular polygon) intersects with the polygon set.
4. If the overlap is sufficient (greater than some minimum value you specify), mark the grid cell with a zero; otherwise, mark it with a one.
5. You now have a rectangular array of zeros and ones. This forms the basis of the easier problem: what is the largest rectangular subset of this grid which is composed entirely of ones?

This easier problem has a number of accessible solutions all over the internet (e.g. 1, 2, 3, 4, 5, 6).