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: ScanLineToRects()28 inline ScanLineToRects() : scanData_(), haveCurrentRect_(), currentRect_(), orient_(), currentCoordinate_() {} 29 ScanLineToRects(orientation_2d orient,rectangle_type model)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 nextMajorCoordinate(coordinate_type currentCoordinate)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& processEdge_(CT & rectangles,ST & scanData,const interval_type & edge,bool & haveCurrentRect,rectangle_type & currentRect,coordinate_type currentCoordinate,orientation_2d orient)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 processEdge(CT & rectangles,const interval_data<coordinate_type> & edge)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> form_rectangles(output_container & output,iterator_type begin,iterator_type end,orientation_2d orient,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(abs((*itr).second.second) > 1) itr = tmp_itr; //next edge begins from this vertex 262 } 263 } 264 } 265 } 266 #endif 267