src/dsutil/xy_utils.cpp

   1 #include "stdafx.h"
   2 #include "xy_utils.h"
   3 #include <vector>
   4 #include <algorithm>
   5
   6 void MergeRects(const CAtlList<CRect>& input, CAtlList<CRect>* output)
   7 {
   8     if(output==NULL || input.GetCount()==0)
   9         return;
  10
  11     struct Segment
  12     {
  13         int top, bottom;
  14         int seg_start, seg_end;
  15         CAtlList<CRect>* rects;
  16
  17         Segment()
  18         {
  19             rects = NULL;
  20         }
  21         ~Segment()
  22         {
  23             delete rects;
  24         }
  25     };
  26
  27     struct BreakPoint
  28     {
  29         int x;
  30         const RECT* rect;
  31
  32         inline bool operator<(const BreakPoint& breakpoint ) const
  33         {
  34             return (x < breakpoint.x);
  35         }
  36     };
  37
  38     int input_count = input.GetCount();
  39     std::vector<int> vertical_breakpoints(2*input_count);
  40     std::vector<BreakPoint> herizon_breakpoints(input_count + 1);
  41
  42     POSITION pos = input.GetHeadPosition();
  43     for(int i=0; i<input_count; i++)
  44     {
  45         const CRect& rect = input.GetNext(pos);
  46         vertical_breakpoints[2*i]=rect.top;
  47         vertical_breakpoints[2*i+1]=rect.bottom;
  48
  49         herizon_breakpoints[i].x = rect.left;
  50         herizon_breakpoints[i].rect = &rect;
  51     }
  52     CRect sentinel_rect(INT_MAX, 0, INT_MAX, INT_MAX);
  53     herizon_breakpoints[input_count].x = INT_MAX;//sentinel
  54     herizon_breakpoints[input_count].rect = &sentinel_rect;
  55
  56     std::sort(vertical_breakpoints.begin(), vertical_breakpoints.end());
  57     std::sort(herizon_breakpoints.begin(), herizon_breakpoints.end());
  58
  59     std::vector<Segment> tempSegments(vertical_breakpoints.size()-1);
  60     int ptr = 1, prev = vertical_breakpoints[0], count = 0;
  61     for(int i = vertical_breakpoints.size()-1; i > 0; i--, ptr++)
  62     {
  63         if(vertical_breakpoints[ptr] != prev)
  64         {
  65             Segment& seg = tempSegments[count];
  66             seg.top = prev;
  67             seg.bottom = vertical_breakpoints[ptr];
  68             seg.seg_end = seg.seg_start = INT_MIN;//important! cannot use =0
  69             seg.rects = new CAtlList<CRect>();
  70
  71             prev = vertical_breakpoints[ptr];
  72             count++;
  73         }
  74     }
  75
  76     for(int i=0; i<=input_count; i++)
  77     {
  78         const CRect& rect = *herizon_breakpoints[i].rect;
  79
  80         int start = 0, mid, end = count;
  81
  82         while(start<end)
  83         {
  84             mid = (start+end)>>1;
  85             if(tempSegments[mid].top < rect.top)
  86             {
  87                 start = mid+1;
  88             }
  89             else
  90             {
  91                 end = mid;
  92             }
  93         }
  94         for(; start < count && tempSegments[start].bottom <= rect.bottom; start++)
  95         {
  96             if(tempSegments[start].seg_end<rect.left)
  97             {
  98                 CRect out_rect( tempSegments[start].seg_start, tempSegments[start].top, tempSegments[start].seg_end, tempSegments[start].bottom );
  99                 tempSegments[start].rects->AddTail( out_rect );
 100                 tempSegments[start].seg_start = rect.left;
 101                 tempSegments[start].seg_end = rect.right;
 102             }
 103             else if( tempSegments[start].seg_end<rect.right )
 104             {
 105                 tempSegments[start].seg_end=rect.right;
 106             }
 107         }
 108     }
 109     for (int i=count-1;i>0;i--)
 110     {
 111         CAtlList<CRect>& cur_line = *tempSegments[i].rects;
 112         CRect cur_rect = cur_line.RemoveTail();
 113         if(tempSegments[i].top == tempSegments[i-1].bottom)
 114         {
 115             CAtlList<CRect>& upper_line = *tempSegments[i-1].rects;
 116
 117             POSITION pos = upper_line.GetTailPosition();
 118             while(pos)
 119             {
 120                 CRect& upper_rect = upper_line.GetPrev(pos);
 121                 while( upper_rect.right<cur_rect.right || upper_rect.left<cur_rect.left )
 122                 {
 123                     output->AddHead(cur_rect);
 124                     //if(!cur_line.IsEmpty())
 125                     cur_rect = cur_line.RemoveTail();
 126                 }
 127                 if(cur_line.IsEmpty())
 128                     break;
 129
 130                 if(upper_rect.right==cur_rect.right && upper_rect.left==cur_rect.left)
 131                 {
 132                     upper_rect.bottom = cur_rect.bottom;
 133                     //if(!cur_line.IsEmpty())
 134                     cur_rect = cur_line.RemoveTail();
 135                 }
 136                 //else if ( upper_rect.right>cur_rect.right || upper_rect.left>cur_rect.left )
 137             }
 138         }
 139         while(!cur_line.IsEmpty())
 140         {
 141             output->AddHead(cur_rect);
 142             cur_rect = cur_line.RemoveTail();
 143         }
 144     }
 145     if(count>0)
 146     {
 147         CAtlList<CRect>& cur_line = *tempSegments[0].rects;
 148         CRect cur_rect = cur_line.RemoveTail();
 149         while(!cur_line.IsEmpty())
 150         {
 151             output->AddHead(cur_rect);
 152             cur_rect = cur_line.RemoveTail();
 153         }
 154     }
 155 }