title: How to find free area rectangles?
body: <p>Can anyone help me on how to draw rectangles for space in a bounding box region with n rectangular obstacles? There could be any number of axis parallel rectangular obstacles, this is not a unique case, thus different corner cases needs to be taken into consideration. Is it best to use maximal horizontal strip algorithm? And how? </p>
  
  <p>Problem Description:</p>
  
  <p>1.SUB1 and SUB2 are the obstacles and you will not touch the internal of SUB1 and SUB2,  you need to find all the free areas externally to all SUBs and create rectangles out of them.</p>
  
  <p>2.You will need to find all the possible rectangles on the free areas rectangles accordingly with its sweep through from left to right without intersecting the SUBs; </p>
  
  <p>The total number of maximal horizontal space rectangles in this case should be 7 or in general, 3n+2 (where n being the number of obstacles):
  <a href="http://img25.imageshack.us/img25/452/pic1gts.png" rel="nofollow noreferrer">alt text http://img25.imageshack.us/img25/452/pic1gts.png</a></p>
  
  <p><a href="http://img22.imageshack.us/img22/3417/pic2h.png" rel="nofollow noreferrer">alt text http://img22.imageshack.us/img22/3417/pic2h.png</a></p>
  
  <p><a href="http://img16.imageshack.us/img16/5818/pic3h.png" rel="nofollow noreferrer">alt text http://img16.imageshack.us/img16/5818/pic3h.png</a></p>
  
  <p><a href="http://img13.imageshack.us/img13/2151/pic4.png" rel="nofollow noreferrer">alt text http://img13.imageshack.us/img13/2151/pic4.png</a></p>
  
  <p>Click to view images:
  <a href="http://img25.imageshack.us/img25/452/pic1gts.png" rel="nofollow noreferrer">http://img25.imageshack.us/img25/452/pic1gts.png</a>
  <a href="http://img22.imageshack.us/img22/3417/pic2h.png" rel="nofollow noreferrer">http://img22.imageshack.us/img22/3417/pic2h.png</a>
  <a href="http://img16.imageshack.us/img16/5818/pic3h.png" rel="nofollow noreferrer">http://img16.imageshack.us/img16/5818/pic3h.png</a>
  <a href="http://img13.imageshack.us/img13/2151/pic4.png" rel="nofollow noreferrer">http://img13.imageshack.us/img13/2151/pic4.png</a></p>