title: How to get minimum count rectangles that covers another pile of rectangle?
body: <p>Assume I have a pile of rectangles, some of which intersect, some isolate. E. g.</p>
  
  <pre>
  
      +--------------- +                     +-------- +
      |                |                     |         |
      |                |                     |         |
      |       A        |                     |   C     |
      |         +---------------- +          |         |
      |         |      |          |          +---------+-------- +
      |         |      |          |          |                   |
      +---------|----- +  B       |          |       D           |
                |                 |          |                   |
                |                 |          +------------------ +
                +---------------- +
  
      +------------------ +          +-------- +
      |                   |          |         |
      |        E          |          |   X     |
      +-------------------+          |         |
      |                   |          +-------- +
      |                   |                       +------------ +
      |                   |                       |             |
      |        F          |                       |             |
      |                   |                       |     Y       |
      |                   |                       |             |
      +-------------------+                       +------------ +
  
  </pre>
  
  <p>Rect A, B intersect with each other, C, D have one same point, E, F have two same points,  X, Y are isolated.</p>
  
  <p>I have two questions:</p>
  
  <ol>
  <li>How to partion these rectangles into rectangles which cover A, B, C, D, E, F, X, Y exactly also have minimum count like this:</li>
  </ol>
  
  <pre>
  
      +---------+----- +                     +-------- +
      |         |      |                     |         |
      |         |      |                     |         |
      |         |      |                     |         |
      |         |      +--------- +          |         |
      |         |      |          |          +---------+-------- +
      |         |      |          |          |                   |
      +---------+      |          |          |                   |
                |      |          |          |                   |
                |      |          |          +-------------------+
                +------+----------+
  
      +------------------ +          +-------- +
      |                   |          |         |
      |                   |          |         |
      |                   |          |         |
      |                   |          +---------+
      |                   |                       +------------ +
      |                   |                       |             |
      |                   |                       |             |
      |                   |                       |             |
      |                   |                       |             |
      +-------------------+                       +-------------+
  
  </pre>
  
  <ol>
  <li>How to cover intersected rectangles with big ones? Like this:</li>
  </ol>
  
  <pre>
  
      +---------------------------+          +-------------------+
      |                           |          |                   |
      |                           |          |                   |
      |                           |          |                   |
      |                           |          |                   |
      |                           |          |                   |
      |                           |          |                   |
      |                           |          |                   |
      |                           |          |                   |
      |                           |          +-------------------+
      +---------------------------+
  
  
      +-------------------+          +---------+
      |                   |          |         |
      |                   |          |         |
      |                   |          |         |
      |                   |          +---------+
      |                   |                       +------------ +
      |                   |                       |             |
      |                   |                       |             |
      |                   |                       |             |
      |                   |                       |             |
      +-------------------+                       +-------------+
  
  </pre>
  
  <p>For Q1, I've no idea at all....
  For Q2, I wrote some code in C++ but have poor efficiency. I believe there're better methods/algorithm.</p>
  
  <pre><code> bool intersectRect(const Rect&amp; rect1, const Rect&amp; rect2) {
      /* if rect1 and rect2 intersect return true
         else return false
      */
  }
  Rect mergeIntersectRects(const set&lt;Rect&gt;&amp; rects) {
      // suppose rects are all intersected. This function only return a smallest Rect that cover all rects.
  }
  set&lt;Rect&gt; mergeRectToRects(const set&lt;Rect&gt;&amp; rectset, const Rect&amp; rect) {
      set&lt;Rect&gt; _intersect_rects;
      set&lt;Rect&gt; _unintersect_rects;
      for(set&lt;Rect&gt;::const_iterator it = rectset.begin();
          it != rectset.end();
          ++it) {
          if(intersectRect(*it, rect))
              _intersect_rects.insert(*it);
          else 
              _unintersect_rects.insert(*it);
      }
      if(!_intersect_rects.empty()) {
          _intersect_rects.insert(rect);
          return mergeRectToRects(_unintersect_rects,
                                  mergeIntersectRects(_intersect_rects));
      }
      else {
          _unintersect_rects.insert(rect);
          return _unintersect_rects;
      }
  }
  </code></pre>