Chris@16: /*
Chris@16:     Copyright 2008 Intel Corporation
Chris@16: 
Chris@16:     Use, modification and distribution are subject to the Boost Software License,
Chris@16:     Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16:     http://www.boost.org/LICENSE_1_0.txt).
Chris@16: */
Chris@16: #ifndef BOOST_POLYGON_RECTANGLE_FORMATION_HPP
Chris@16: #define BOOST_POLYGON_RECTANGLE_FORMATION_HPP
Chris@16: namespace boost { namespace polygon{
Chris@16: 
Chris@16: namespace rectangle_formation {
Chris@16:   template <class T>
Chris@16:   class ScanLineToRects {
Chris@16:   public:
Chris@16:     typedef T rectangle_type;
Chris@16:     typedef typename rectangle_traits<T>::coordinate_type coordinate_type;
Chris@16:     typedef rectangle_data<coordinate_type> scan_rect_type;
Chris@16:   private:
Chris@16: 
Chris@16:     typedef std::set<scan_rect_type, less_rectangle_concept<scan_rect_type, scan_rect_type> > ScanData;
Chris@16:     ScanData scanData_;
Chris@16:     bool haveCurrentRect_;
Chris@16:     scan_rect_type currentRect_;
Chris@16:     orientation_2d orient_;
Chris@16:     typename rectangle_traits<T>::coordinate_type currentCoordinate_;
Chris@16:   public:
Chris@16:     inline ScanLineToRects() : scanData_(), haveCurrentRect_(), currentRect_(), orient_(), currentCoordinate_() {}
Chris@16: 
Chris@16:     inline ScanLineToRects(orientation_2d orient, rectangle_type model) :
Chris@16:       scanData_(orientation_2d(orient.to_int() ? VERTICAL : HORIZONTAL)),
Chris@16:       haveCurrentRect_(false), currentRect_(), orient_(orient), currentCoordinate_() {
Chris@16:       assign(currentRect_, model);
Chris@16:       currentCoordinate_ = (std::numeric_limits<coordinate_type>::max)();
Chris@16:     }
Chris@16: 
Chris@16:     template <typename CT>
Chris@16:     inline ScanLineToRects& processEdge(CT& rectangles, const interval_data<coordinate_type>& edge);
Chris@16: 
Chris@16:     inline ScanLineToRects& nextMajorCoordinate(coordinate_type currentCoordinate) {
Chris@16:       if(haveCurrentRect_) {
Chris@16:         scanData_.insert(scanData_.end(), currentRect_);
Chris@16:         haveCurrentRect_ = false;
Chris@16:       }
Chris@16:       currentCoordinate_ = currentCoordinate;
Chris@16:       return *this;
Chris@16:     }
Chris@16: 
Chris@16:   };
Chris@16: 
Chris@16:   template <class CT, class ST, class rectangle_type, typename interval_type, typename coordinate_type> inline CT&
Chris@16:   processEdge_(CT& rectangles, ST& scanData, const interval_type& edge,
Chris@16:                bool& haveCurrentRect, rectangle_type& currentRect, coordinate_type currentCoordinate, orientation_2d orient)
Chris@16:   {
Chris@16:     typedef typename CT::value_type result_type;
Chris@16:     bool edgeProcessed = false;
Chris@16:     if(!scanData.empty()) {
Chris@16: 
Chris@16:       //process all rectangles in the scanData that touch the edge
Chris@16:       typename ST::iterator dataIter = scanData.lower_bound(rectangle_type(edge, edge));
Chris@16:       //decrement beginIter until its low is less than edge's low
Chris@16:       while((dataIter == scanData.end() || (*dataIter).get(orient).get(LOW) > edge.get(LOW)) &&
Chris@16:             dataIter != scanData.begin())
Chris@16:         {
Chris@16:           --dataIter;
Chris@16:         }
Chris@16:       //process each rectangle until the low end of the rectangle
Chris@16:       //is greater than the high end of the edge
Chris@16:       while(dataIter != scanData.end() &&
Chris@16:             (*dataIter).get(orient).get(LOW) <= edge.get(HIGH))
Chris@16:         {
Chris@16:           const rectangle_type& rect = *dataIter;
Chris@16:           //if the rectangle data intersects the edge at all
Chris@16:           if(rect.get(orient).get(HIGH) >= edge.get(LOW)) {
Chris@16:             if(contains(rect.get(orient), edge, true)) {
Chris@16:               //this is a closing edge
Chris@16:               //we need to write out the intersecting rectangle and
Chris@16:               //insert between 0 and 2 rectangles into the scanData
Chris@16:               //write out rectangle
Chris@16:               rectangle_type tmpRect = rect;
Chris@16: 
Chris@16:               if(rect.get(orient.get_perpendicular()).get(LOW) < currentCoordinate) {
Chris@16:                 //set the high coordinate perpedicular to slicing orientation
Chris@16:                 //to the current coordinate of the scan event
Chris@16:                 tmpRect.set(orient.get_perpendicular().get_direction(HIGH),
Chris@16:                             currentCoordinate);
Chris@16:                 result_type result;
Chris@16:                 assign(result, tmpRect);
Chris@16:                 rectangles.insert(rectangles.end(), result);
Chris@16:               }
Chris@16:               //erase the rectangle from the scan data
Chris@16:               typename ST::iterator nextIter = dataIter;
Chris@16:               ++nextIter;
Chris@16:               scanData.erase(dataIter);
Chris@16:               if(tmpRect.get(orient).get(LOW) < edge.get(LOW)) {
Chris@16:                 //insert a rectangle for the overhang of the bottom
Chris@16:                 //of the rectangle back into scan data
Chris@16:                 rectangle_type lowRect(tmpRect);
Chris@16:                 lowRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
Chris@16:                                                                 currentCoordinate));
Chris@16:                 lowRect.set(orient.get_direction(HIGH), edge.get(LOW));
Chris@16:                 scanData.insert(nextIter, lowRect);
Chris@16:               }
Chris@16:               if(tmpRect.get(orient).get(HIGH) > edge.get(HIGH)) {
Chris@16:                 //insert a rectangle for the overhang of the top
Chris@16:                 //of the rectangle back into scan data
Chris@16:                 rectangle_type highRect(tmpRect);
Chris@16:                 highRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
Chris@16:                                                                  currentCoordinate));
Chris@16:                 highRect.set(orient.get_direction(LOW), edge.get(HIGH));
Chris@16:                 scanData.insert(nextIter, highRect);
Chris@16:               }
Chris@16:               //we are done with this edge
Chris@16:               edgeProcessed = true;
Chris@16:               break;
Chris@16:             } else {
Chris@16:               //it must be an opening edge
Chris@16:               //assert that rect does not overlap the edge but only touches
Chris@16:               //write out rectangle
Chris@16:               rectangle_type tmpRect = rect;
Chris@16:               //set the high coordinate perpedicular to slicing orientation
Chris@16:               //to the current coordinate of the scan event
Chris@16:               if(tmpRect.get(orient.get_perpendicular().get_direction(LOW)) < currentCoordinate) {
Chris@16:                 tmpRect.set(orient.get_perpendicular().get_direction(HIGH),
Chris@16:                             currentCoordinate);
Chris@16:                 result_type result;
Chris@16:                 assign(result, tmpRect);
Chris@16:                 rectangles.insert(rectangles.end(), result);
Chris@16:               }
Chris@16:               //erase the rectangle from the scan data
Chris@16:               typename ST::iterator nextIter = dataIter;
Chris@16:               ++nextIter;
Chris@16:               scanData.erase(dataIter);
Chris@16:               dataIter = nextIter;
Chris@16:               if(haveCurrentRect) {
Chris@16:                 if(currentRect.get(orient).get(HIGH) >= edge.get(LOW)){
Chris@16:                   if(!edgeProcessed && currentRect.get(orient.get_direction(HIGH)) > edge.get(LOW)){
Chris@16:                     rectangle_type tmpRect2(currentRect);
Chris@16:                     tmpRect2.set(orient.get_direction(HIGH), edge.get(LOW));
Chris@16:                     scanData.insert(nextIter, tmpRect2);
Chris@16:                     if(currentRect.get(orient.get_direction(HIGH)) > edge.get(HIGH)) {
Chris@16:                       currentRect.set(orient, interval_data<coordinate_type>(edge.get(HIGH), currentRect.get(orient.get_direction(HIGH))));
Chris@16:                     } else {
Chris@16:                       haveCurrentRect = false;
Chris@16:                     }
Chris@16:                   } else {
Chris@16:                     //extend the top of current rect
Chris@16:                     currentRect.set(orient.get_direction(HIGH),
Chris@16:                                     (std::max)(edge.get(HIGH),
Chris@16:                                                tmpRect.get(orient.get_direction(HIGH))));
Chris@16:                   }
Chris@16:                 } else {
Chris@16:                   //insert current rect into the scanData
Chris@16:                   scanData.insert(nextIter, currentRect);
Chris@16:                   //create a new current rect
Chris@16:                   currentRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
Chris@16:                                                                       currentCoordinate));
Chris@16:                   currentRect.set(orient, interval_data<coordinate_type>((std::min)(tmpRect.get(orient).get(LOW),
Chris@16:                                                        edge.get(LOW)),
Chris@16:                                                                          (std::max)(tmpRect.get(orient).get(HIGH),
Chris@16:                                                        edge.get(HIGH))));
Chris@16:                 }
Chris@16:               } else {
Chris@16:                 haveCurrentRect = true;
Chris@16:                 currentRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
Chris@16:                                                                     currentCoordinate));
Chris@16:                 currentRect.set(orient, interval_data<coordinate_type>((std::min)(tmpRect.get(orient).get(LOW),
Chris@16:                                                      edge.get(LOW)),
Chris@16:                                                                        (std::max)(tmpRect.get(orient).get(HIGH),
Chris@16:                                                      edge.get(HIGH))));
Chris@16:               }
Chris@16:               //skip to nextIter position
Chris@16:               edgeProcessed = true;
Chris@16:               continue;
Chris@16:             }
Chris@16:             //edgeProcessed = true;
Chris@16:           }
Chris@16:           ++dataIter;
Chris@16:         } //end while edge intersects rectangle data
Chris@16: 
Chris@16:     }
Chris@16:     if(!edgeProcessed) {
Chris@16:       if(haveCurrentRect) {
Chris@16:         if(currentRect.get(orient.get_perpendicular().get_direction(HIGH))
Chris@16:            == currentCoordinate &&
Chris@16:            currentRect.get(orient.get_direction(HIGH)) >= edge.get(LOW))
Chris@16:           {
Chris@16:             if(currentRect.get(orient.get_direction(HIGH)) > edge.get(LOW)){
Chris@16:               rectangle_type tmpRect(currentRect);
Chris@16:               tmpRect.set(orient.get_direction(HIGH), edge.get(LOW));
Chris@16:               scanData.insert(scanData.end(), tmpRect);
Chris@16:               if(currentRect.get(orient.get_direction(HIGH)) > edge.get(HIGH)) {
Chris@16:                 currentRect.set(orient,
Chris@16:                                 interval_data<coordinate_type>(edge.get(HIGH),
Chris@16:                                          currentRect.get(orient.get_direction(HIGH))));
Chris@16:                 return rectangles;
Chris@16:               } else {
Chris@16:                 haveCurrentRect = false;
Chris@16:                 return rectangles;
Chris@16:               }
Chris@16:             }
Chris@16:             //extend current rect
Chris@16:             currentRect.set(orient.get_direction(HIGH), edge.get(HIGH));
Chris@16:             return rectangles;
Chris@16:           }
Chris@16:         scanData.insert(scanData.end(), currentRect);
Chris@16:         haveCurrentRect = false;
Chris@16:       }
Chris@16:       rectangle_type tmpRect(currentRect);
Chris@16:       tmpRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
Chris@16:                                                       currentCoordinate));
Chris@16:       tmpRect.set(orient, edge);
Chris@16:       scanData.insert(tmpRect);
Chris@16:       return rectangles;
Chris@16:     }
Chris@16:     return rectangles;
Chris@16: 
Chris@16:   }
Chris@16: 
Chris@16:   template <class T>
Chris@16:   template <class CT>
Chris@16:   inline
Chris@16:   ScanLineToRects<T>& ScanLineToRects<T>::processEdge(CT& rectangles, const interval_data<coordinate_type>& edge)
Chris@16:   {
Chris@16:     processEdge_(rectangles, scanData_, edge, haveCurrentRect_, currentRect_, currentCoordinate_, orient_);
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16: } //namespace rectangle_formation
Chris@16: 
Chris@16:   template <typename T, typename T2>
Chris@16:   struct get_coordinate_type_for_rectangles {
Chris@16:     typedef typename polygon_traits<T>::coordinate_type type;
Chris@16:   };
Chris@16:   template <typename T>
Chris@16:   struct get_coordinate_type_for_rectangles<T, rectangle_concept> {
Chris@16:     typedef typename rectangle_traits<T>::coordinate_type type;
Chris@16:   };
Chris@16: 
Chris@16:   template <typename output_container, typename iterator_type, typename rectangle_concept>
Chris@16:   void form_rectangles(output_container& output, iterator_type begin, iterator_type end,
Chris@16:                        orientation_2d orient, rectangle_concept ) {
Chris@16:     typedef typename output_container::value_type rectangle_type;
Chris@16:     typedef typename get_coordinate_type_for_rectangles<rectangle_type, typename geometry_concept<rectangle_type>::type>::type Unit;
Chris@16:     rectangle_data<Unit> model;
Chris@16:     Unit prevPos = (std::numeric_limits<Unit>::max)();
Chris@16:     rectangle_formation::ScanLineToRects<rectangle_data<Unit> > scanlineToRects(orient, model);
Chris@16:     for(iterator_type itr = begin;
Chris@16:         itr != end; ++ itr) {
Chris@16:       Unit pos = (*itr).first;
Chris@16:       if(pos != prevPos) {
Chris@16:         scanlineToRects.nextMajorCoordinate(pos);
Chris@16:         prevPos = pos;
Chris@16:       }
Chris@16:       Unit lowy = (*itr).second.first;
Chris@16:       iterator_type tmp_itr = itr;
Chris@16:       ++itr;
Chris@16:       Unit highy = (*itr).second.first;
Chris@16:       scanlineToRects.processEdge(output, interval_data<Unit>(lowy, highy));
Chris@16:       if(abs((*itr).second.second) > 1) itr = tmp_itr; //next edge begins from this vertex
Chris@16:     }
Chris@16:   }
Chris@16: }
Chris@16: }
Chris@16: #endif