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