title: Optimally Find Empty Space On Grid
body: <p>I'm hoping somebody can help me optimize an algorithm I'm dealing with in my current project.  This is being coded in C#, but is more of a logic problem.</p>
  
  <p>I have a two-dimensional array of bools (a grid) which act as a container of rectangles.  When a rectangle is placed on the grid, it toggles the bools to true.</p>
  
  <p>Empty space = false</p>
  
  <p>Occupied space = true</p>
  
  <p>Now for the problem.  How do I find the closest empty position to a point (x, y) where a rectangle of width (w) and height (h) can fit without overlapping an occupied space?</p>
  
  <p>I've done a very naive baseline implementation that works as follows:</p>
  
  <pre><code>WHILE point not found
    SET g to nearest unchecked grid point
    SET allempty to true
  
    FOR EACH x value in rect (i)
       FOR EACH y value in rect (j)
         IF gridpoint[i, j] is occupied
            SET allempty to false;
         END IF
       END FOR
    END FOR
  
    IF allempty
       RETURN g as legal location
    END IF
  END WHILE
  </code></pre>
  
  <p>But I know there are other, more efficient ways to perform this operation.  Can anybody point me to an algorithm that could do this more effectively?</p>
  
  <p>Thanks for your time</p>