9

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.

Largest empty rectangle 1

Largest empty rectangle 2

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?

Richard
  • 56,349
  • 34
  • 180
  • 251
karmakomik
  • 93
  • 1
  • 4
  • 1
    The 5th link in your linked google results could be working for you. Since they also deal with polygon that can have holes in in. The holes would be your polygons. So try: http://www.sciencedirect.com/science/article/pii/0925772195000410 – NoDataDumpNoContribution Dec 10 '14 at 11:58
  • @Trilarion Thank you, that looks promising! – karmakomik Dec 10 '14 at 12:11

1 Answers1

5

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).

Richard
  • 56,349
  • 34
  • 180
  • 251