ceph/src/boost/libs/polygon/include/boost/polygon/detail/rectangle_formation.hpp

   1 /*
   2     Copyright 2008 Intel Corporation
   3
   4     Use, modification and distribution are subject to the Boost Software License,
   5     Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6     http://www.boost.org/LICENSE_1_0.txt).
   7 */
   8 #ifndef BOOST_POLYGON_RECTANGLE_FORMATION_HPP
   9 #define BOOST_POLYGON_RECTANGLE_FORMATION_HPP
  10 namespace boost { namespace polygon{
  11
  12 namespace rectangle_formation {
  13   template <class T>
  14   class ScanLineToRects {
  15   public:
  16     typedef T rectangle_type;
  17     typedef typename rectangle_traits<T>::coordinate_type coordinate_type;
  18     typedef rectangle_data<coordinate_type> scan_rect_type;
  19   private:
  20
  21     typedef std::set<scan_rect_type, less_rectangle_concept<scan_rect_type, scan_rect_type> > ScanData;
  22     ScanData scanData_;
  23     bool haveCurrentRect_;
  24     scan_rect_type currentRect_;
  25     orientation_2d orient_;
  26     typename rectangle_traits<T>::coordinate_type currentCoordinate_;
  27   public:
  28     inline ScanLineToRects() : scanData_(), haveCurrentRect_(), currentRect_(), orient_(), currentCoordinate_() {}
  29
  30     inline ScanLineToRects(orientation_2d orient, rectangle_type model) :
  31       scanData_(orientation_2d(orient.to_int() ? VERTICAL : HORIZONTAL)),
  32       haveCurrentRect_(false), currentRect_(), orient_(orient), currentCoordinate_() {
  33       assign(currentRect_, model);
  34       currentCoordinate_ = (std::numeric_limits<coordinate_type>::max)();
  35     }
  36
  37     template <typename CT>
  38     inline ScanLineToRects& processEdge(CT& rectangles, const interval_data<coordinate_type>& edge);
  39
  40     inline ScanLineToRects& nextMajorCoordinate(coordinate_type currentCoordinate) {
  41       if(haveCurrentRect_) {
  42         scanData_.insert(scanData_.end(), currentRect_);
  43         haveCurrentRect_ = false;
  44       }
  45       currentCoordinate_ = currentCoordinate;
  46       return *this;
  47     }
  48
  49   };
  50
  51   template <class CT, class ST, class rectangle_type, typename interval_type, typename coordinate_type> inline CT&
  52   processEdge_(CT& rectangles, ST& scanData, const interval_type& edge,
  53                bool& haveCurrentRect, rectangle_type& currentRect, coordinate_type currentCoordinate, orientation_2d orient)
  54   {
  55     typedef typename CT::value_type result_type;
  56     bool edgeProcessed = false;
  57     if(!scanData.empty()) {
  58
  59       //process all rectangles in the scanData that touch the edge
  60       typename ST::iterator dataIter = scanData.lower_bound(rectangle_type(edge, edge));
  61       //decrement beginIter until its low is less than edge's low
  62       while((dataIter == scanData.end() || (*dataIter).get(orient).get(LOW) > edge.get(LOW)) &&
  63             dataIter != scanData.begin())
  64         {
  65           --dataIter;
  66         }
  67       //process each rectangle until the low end of the rectangle
  68       //is greater than the high end of the edge
  69       while(dataIter != scanData.end() &&
  70             (*dataIter).get(orient).get(LOW) <= edge.get(HIGH))
  71         {
  72           const rectangle_type& rect = *dataIter;
  73           //if the rectangle data intersects the edge at all
  74           if(rect.get(orient).get(HIGH) >= edge.get(LOW)) {
  75             if(contains(rect.get(orient), edge, true)) {
  76               //this is a closing edge
  77               //we need to write out the intersecting rectangle and
  78               //insert between 0 and 2 rectangles into the scanData
  79               //write out rectangle
  80               rectangle_type tmpRect = rect;
  81
  82               if(rect.get(orient.get_perpendicular()).get(LOW) < currentCoordinate) {
  83                 //set the high coordinate perpedicular to slicing orientation
  84                 //to the current coordinate of the scan event
  85                 tmpRect.set(orient.get_perpendicular().get_direction(HIGH),
  86                             currentCoordinate);
  87                 result_type result;
  88                 assign(result, tmpRect);
  89                 rectangles.insert(rectangles.end(), result);
  90               }
  91               //erase the rectangle from the scan data
  92               typename ST::iterator nextIter = dataIter;
  93               ++nextIter;
  94               scanData.erase(dataIter);
  95               if(tmpRect.get(orient).get(LOW) < edge.get(LOW)) {
  96                 //insert a rectangle for the overhang of the bottom
  97                 //of the rectangle back into scan data
  98                 rectangle_type lowRect(tmpRect);
  99                 lowRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
 100                                                                 currentCoordinate));
 101                 lowRect.set(orient.get_direction(HIGH), edge.get(LOW));
 102                 scanData.insert(nextIter, lowRect);
 103               }
 104               if(tmpRect.get(orient).get(HIGH) > edge.get(HIGH)) {
 105                 //insert a rectangle for the overhang of the top
 106                 //of the rectangle back into scan data
 107                 rectangle_type highRect(tmpRect);
 108                 highRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
 109                                                                  currentCoordinate));
 110                 highRect.set(orient.get_direction(LOW), edge.get(HIGH));
 111                 scanData.insert(nextIter, highRect);
 112               }
 113               //we are done with this edge
 114               edgeProcessed = true;
 115               break;
 116             } else {
 117               //it must be an opening edge
 118               //assert that rect does not overlap the edge but only touches
 119               //write out rectangle
 120               rectangle_type tmpRect = rect;
 121               //set the high coordinate perpedicular to slicing orientation
 122               //to the current coordinate of the scan event
 123               if(tmpRect.get(orient.get_perpendicular().get_direction(LOW)) < currentCoordinate) {
 124                 tmpRect.set(orient.get_perpendicular().get_direction(HIGH),
 125                             currentCoordinate);
 126                 result_type result;
 127                 assign(result, tmpRect);
 128                 rectangles.insert(rectangles.end(), result);
 129               }
 130               //erase the rectangle from the scan data
 131               typename ST::iterator nextIter = dataIter;
 132               ++nextIter;
 133               scanData.erase(dataIter);
 134               dataIter = nextIter;
 135               if(haveCurrentRect) {
 136                 if(currentRect.get(orient).get(HIGH) >= edge.get(LOW)){
 137                   if(!edgeProcessed && currentRect.get(orient.get_direction(HIGH)) > edge.get(LOW)){
 138                     rectangle_type tmpRect2(currentRect);
 139                     tmpRect2.set(orient.get_direction(HIGH), edge.get(LOW));
 140                     scanData.insert(nextIter, tmpRect2);
 141                     if(currentRect.get(orient.get_direction(HIGH)) > edge.get(HIGH)) {
 142                       currentRect.set(orient, interval_data<coordinate_type>(edge.get(HIGH), currentRect.get(orient.get_direction(HIGH))));
 143                     } else {
 144                       haveCurrentRect = false;
 145                     }
 146                   } else {
 147                     //extend the top of current rect
 148                     currentRect.set(orient.get_direction(HIGH),
 149                                     (std::max)(edge.get(HIGH),
 150                                                tmpRect.get(orient.get_direction(HIGH))));
 151                   }
 152                 } else {
 153                   //insert current rect into the scanData
 154                   scanData.insert(nextIter, currentRect);
 155                   //create a new current rect
 156                   currentRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
 157                                                                       currentCoordinate));
 158                   currentRect.set(orient, interval_data<coordinate_type>((std::min)(tmpRect.get(orient).get(LOW),
 159                                                        edge.get(LOW)),
 160                                                                          (std::max)(tmpRect.get(orient).get(HIGH),
 161                                                        edge.get(HIGH))));
 162                 }
 163               } else {
 164                 haveCurrentRect = true;
 165                 currentRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
 166                                                                     currentCoordinate));
 167                 currentRect.set(orient, interval_data<coordinate_type>((std::min)(tmpRect.get(orient).get(LOW),
 168                                                      edge.get(LOW)),
 169                                                                        (std::max)(tmpRect.get(orient).get(HIGH),
 170                                                      edge.get(HIGH))));
 171               }
 172               //skip to nextIter position
 173               edgeProcessed = true;
 174               continue;
 175             }
 176             //edgeProcessed = true;
 177           }
 178           ++dataIter;
 179         } //end while edge intersects rectangle data
 180
 181     }
 182     if(!edgeProcessed) {
 183       if(haveCurrentRect) {
 184         if(currentRect.get(orient.get_perpendicular().get_direction(HIGH))
 185            == currentCoordinate &&
 186            currentRect.get(orient.get_direction(HIGH)) >= edge.get(LOW))
 187           {
 188             if(currentRect.get(orient.get_direction(HIGH)) > edge.get(LOW)){
 189               rectangle_type tmpRect(currentRect);
 190               tmpRect.set(orient.get_direction(HIGH), edge.get(LOW));
 191               scanData.insert(scanData.end(), tmpRect);
 192               if(currentRect.get(orient.get_direction(HIGH)) > edge.get(HIGH)) {
 193                 currentRect.set(orient,
 194                                 interval_data<coordinate_type>(edge.get(HIGH),
 195                                          currentRect.get(orient.get_direction(HIGH))));
 196                 return rectangles;
 197               } else {
 198                 haveCurrentRect = false;
 199                 return rectangles;
 200               }
 201             }
 202             //extend current rect
 203             currentRect.set(orient.get_direction(HIGH), edge.get(HIGH));
 204             return rectangles;
 205           }
 206         scanData.insert(scanData.end(), currentRect);
 207         haveCurrentRect = false;
 208       }
 209       rectangle_type tmpRect(currentRect);
 210       tmpRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
 211                                                       currentCoordinate));
 212       tmpRect.set(orient, edge);
 213       scanData.insert(tmpRect);
 214       return rectangles;
 215     }
 216     return rectangles;
 217
 218   }
 219
 220   template <class T>
 221   template <class CT>
 222   inline
 223   ScanLineToRects<T>& ScanLineToRects<T>::processEdge(CT& rectangles, const interval_data<coordinate_type>& edge)
 224   {
 225     processEdge_(rectangles, scanData_, edge, haveCurrentRect_, currentRect_, currentCoordinate_, orient_);
 226     return *this;
 227   }
 228
 229
 230 } //namespace rectangle_formation
 231
 232   template <typename T, typename T2>
 233   struct get_coordinate_type_for_rectangles {
 234     typedef typename polygon_traits<T>::coordinate_type type;
 235   };
 236   template <typename T>
 237   struct get_coordinate_type_for_rectangles<T, rectangle_concept> {
 238     typedef typename rectangle_traits<T>::coordinate_type type;
 239   };
 240
 241   template <typename output_container, typename iterator_type, typename rectangle_concept>
 242   void form_rectangles(output_container& output, iterator_type begin, iterator_type end,
 243                        orientation_2d orient, rectangle_concept ) {
 244     typedef typename output_container::value_type rectangle_type;
 245     typedef typename get_coordinate_type_for_rectangles<rectangle_type, typename geometry_concept<rectangle_type>::type>::type Unit;
 246     rectangle_data<Unit> model;
 247     Unit prevPos = (std::numeric_limits<Unit>::max)();
 248     rectangle_formation::ScanLineToRects<rectangle_data<Unit> > scanlineToRects(orient, model);
 249     for(iterator_type itr = begin;
 250         itr != end; ++ itr) {
 251       Unit pos = (*itr).first;
 252       if(pos != prevPos) {
 253         scanlineToRects.nextMajorCoordinate(pos);
 254         prevPos = pos;
 255       }
 256       Unit lowy = (*itr).second.first;
 257       iterator_type tmp_itr = itr;
 258       ++itr;
 259       Unit highy = (*itr).second.first;
 260       scanlineToRects.processEdge(output, interval_data<Unit>(lowy, highy));
 261       if(std::abs((*itr).second.second) > 1) itr = tmp_itr; //next edge begins from this vertex
 262     }
 263   }
 264 }
 265 }
 266 #endif