The algorithm for finding the largest empty rectangle among other polygons

Question

Scenario : there is a rectangular space inside which there are arbitrarily located polygons of arbitrary orientations. The goal is to find the largest empty rectangle that can be set inside the empty areas of the rectangular space. These images below illustrate a scenario with polygons in blue and a dashed line representing the maximum empty rectangle that can be set in each scenario.

Problem . Finding large empty rectangles seems to be a well-known problem in computational geometry, but the algorithms I found in this area concerned finding empty rectangles among points (CGAL implemented this) and line segments. Is there a way to adapt these existing methods to my scenario? Or is there an easier way to do this?

Answer 1

Unfortunately, most of the literature on computational geometry, with which I am familiar, apparently generates beautiful descriptions of algorithms and proofs of their correctness without actually providing implementations. Perhaps this is due to the fact that implementations are usually quite related.

You do not indicate the degree of inaccuracy you may suffer. If you have a certain tolerance, this answer is for you.

My suggestion is that you turn this difficult task into an easier task .

• Find the bounding box of your polygon collection.
• Divide the bounding box into the grid. The finer the grid, the better your accuracy, but the longer it will take to find a solution.
• Find how many areas of each grid cell (molded as a rectangular polygon) intersect with many polygons.
• If the overlap is sufficient (greater than a certain minimum value), mark the grid cell with zero; otherwise mark it with one.
• You now have a rectangular array of zeros and ones. This forms the basis of a simpler task: what is the largest rectangular subset of this grid that consists entirely of them?

This simple problem has many solutions available all over the Internet (for example, 1 , 2 , 3 , 4 , 5 , 6 ).