Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-12-15 10:04:21 

0001 /*
0002     Copyright 2008 Intel Corporation
0003 
0004     Use, modification and distribution are subject to the Boost Software License,
0005     Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0006     http://www.boost.org/LICENSE_1_0.txt).
0007 */
0008 #ifndef BOOST_POLYGON_RECTANGLE_FORMATION_HPP
0009 #define BOOST_POLYGON_RECTANGLE_FORMATION_HPP
0010 namespace boost { namespace polygon{
0011 
0012 namespace rectangle_formation {
0013   template <class T>
0014   class ScanLineToRects {
0015   public:
0016     typedef T rectangle_type;
0017     typedef typename rectangle_traits<T>::coordinate_type coordinate_type;
0018     typedef rectangle_data<coordinate_type> scan_rect_type;
0019   private:
0020 
0021     typedef std::set<scan_rect_type, less_rectangle_concept<scan_rect_type, scan_rect_type> > ScanData;
0022     ScanData scanData_;
0023     bool haveCurrentRect_;
0024     scan_rect_type currentRect_;
0025     orientation_2d orient_;
0026     typename rectangle_traits<T>::coordinate_type currentCoordinate_;
0027   public:
0028     inline ScanLineToRects() : scanData_(), haveCurrentRect_(), currentRect_(), orient_(), currentCoordinate_() {}
0029 
0030     inline ScanLineToRects(orientation_2d orient, rectangle_type model) :
0031       scanData_(orientation_2d(orient.to_int() ? VERTICAL : HORIZONTAL)),
0032       haveCurrentRect_(false), currentRect_(), orient_(orient), currentCoordinate_() {
0033       assign(currentRect_, model);
0034       currentCoordinate_ = (std::numeric_limits<coordinate_type>::max)();
0035     }
0036 
0037     template <typename CT>
0038     inline ScanLineToRects& processEdge(CT& rectangles, const interval_data<coordinate_type>& edge);
0039 
0040     inline ScanLineToRects& nextMajorCoordinate(coordinate_type currentCoordinate) {
0041       if(haveCurrentRect_) {
0042         scanData_.insert(scanData_.end(), currentRect_);
0043         haveCurrentRect_ = false;
0044       }
0045       currentCoordinate_ = currentCoordinate;
0046       return *this;
0047     }
0048 
0049   };
0050 
0051   template <class CT, class ST, class rectangle_type, typename interval_type, typename coordinate_type> inline CT&
0052   processEdge_(CT& rectangles, ST& scanData, const interval_type& edge,
0053                bool& haveCurrentRect, rectangle_type& currentRect, coordinate_type currentCoordinate, orientation_2d orient)
0054   {
0055     typedef typename CT::value_type result_type;
0056     bool edgeProcessed = false;
0057     if(!scanData.empty()) {
0058 
0059       //process all rectangles in the scanData that touch the edge
0060       typename ST::iterator dataIter = scanData.lower_bound(rectangle_type(edge, edge));
0061       //decrement beginIter until its low is less than edge's low
0062       while((dataIter == scanData.end() || (*dataIter).get(orient).get(LOW) > edge.get(LOW)) &&
0063             dataIter != scanData.begin())
0064         {
0065           --dataIter;
0066         }
0067       //process each rectangle until the low end of the rectangle
0068       //is greater than the high end of the edge
0069       while(dataIter != scanData.end() &&
0070             (*dataIter).get(orient).get(LOW) <= edge.get(HIGH))
0071         {
0072           const rectangle_type& rect = *dataIter;
0073           //if the rectangle data intersects the edge at all
0074           if(rect.get(orient).get(HIGH) >= edge.get(LOW)) {
0075             if(contains(rect.get(orient), edge, true)) {
0076               //this is a closing edge
0077               //we need to write out the intersecting rectangle and
0078               //insert between 0 and 2 rectangles into the scanData
0079               //write out rectangle
0080               rectangle_type tmpRect = rect;
0081 
0082               if(rect.get(orient.get_perpendicular()).get(LOW) < currentCoordinate) {
0083                 //set the high coordinate perpedicular to slicing orientation
0084                 //to the current coordinate of the scan event
0085                 tmpRect.set(orient.get_perpendicular().get_direction(HIGH),
0086                             currentCoordinate);
0087                 result_type result;
0088                 assign(result, tmpRect);
0089                 rectangles.insert(rectangles.end(), result);
0090               }
0091               //erase the rectangle from the scan data
0092               typename ST::iterator nextIter = dataIter;
0093               ++nextIter;
0094               scanData.erase(dataIter);
0095               if(tmpRect.get(orient).get(LOW) < edge.get(LOW)) {
0096                 //insert a rectangle for the overhang of the bottom
0097                 //of the rectangle back into scan data
0098                 rectangle_type lowRect(tmpRect);
0099                 lowRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
0100                                                                 currentCoordinate));
0101                 lowRect.set(orient.get_direction(HIGH), edge.get(LOW));
0102                 scanData.insert(nextIter, lowRect);
0103               }
0104               if(tmpRect.get(orient).get(HIGH) > edge.get(HIGH)) {
0105                 //insert a rectangle for the overhang of the top
0106                 //of the rectangle back into scan data
0107                 rectangle_type highRect(tmpRect);
0108                 highRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
0109                                                                  currentCoordinate));
0110                 highRect.set(orient.get_direction(LOW), edge.get(HIGH));
0111                 scanData.insert(nextIter, highRect);
0112               }
0113               //we are done with this edge
0114               edgeProcessed = true;
0115               break;
0116             } else {
0117               //it must be an opening edge
0118               //assert that rect does not overlap the edge but only touches
0119               //write out rectangle
0120               rectangle_type tmpRect = rect;
0121               //set the high coordinate perpedicular to slicing orientation
0122               //to the current coordinate of the scan event
0123               if(tmpRect.get(orient.get_perpendicular().get_direction(LOW)) < currentCoordinate) {
0124                 tmpRect.set(orient.get_perpendicular().get_direction(HIGH),
0125                             currentCoordinate);
0126                 result_type result;
0127                 assign(result, tmpRect);
0128                 rectangles.insert(rectangles.end(), result);
0129               }
0130               //erase the rectangle from the scan data
0131               typename ST::iterator nextIter = dataIter;
0132               ++nextIter;
0133               scanData.erase(dataIter);
0134               dataIter = nextIter;
0135               if(haveCurrentRect) {
0136                 if(currentRect.get(orient).get(HIGH) >= edge.get(LOW)){
0137                   if(!edgeProcessed && currentRect.get(orient.get_direction(HIGH)) > edge.get(LOW)){
0138                     rectangle_type tmpRect2(currentRect);
0139                     tmpRect2.set(orient.get_direction(HIGH), edge.get(LOW));
0140                     scanData.insert(nextIter, tmpRect2);
0141                     if(currentRect.get(orient.get_direction(HIGH)) > edge.get(HIGH)) {
0142                       currentRect.set(orient, interval_data<coordinate_type>(edge.get(HIGH), currentRect.get(orient.get_direction(HIGH))));
0143                     } else {
0144                       haveCurrentRect = false;
0145                     }
0146                   } else {
0147                     //extend the top of current rect
0148                     currentRect.set(orient.get_direction(HIGH),
0149                                     (std::max)(edge.get(HIGH),
0150                                                tmpRect.get(orient.get_direction(HIGH))));
0151                   }
0152                 } else {
0153                   //insert current rect into the scanData
0154                   scanData.insert(nextIter, currentRect);
0155                   //create a new current rect
0156                   currentRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
0157                                                                       currentCoordinate));
0158                   currentRect.set(orient, interval_data<coordinate_type>((std::min)(tmpRect.get(orient).get(LOW),
0159                                                        edge.get(LOW)),
0160                                                                          (std::max)(tmpRect.get(orient).get(HIGH),
0161                                                        edge.get(HIGH))));
0162                 }
0163               } else {
0164                 haveCurrentRect = true;
0165                 currentRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
0166                                                                     currentCoordinate));
0167                 currentRect.set(orient, interval_data<coordinate_type>((std::min)(tmpRect.get(orient).get(LOW),
0168                                                      edge.get(LOW)),
0169                                                                        (std::max)(tmpRect.get(orient).get(HIGH),
0170                                                      edge.get(HIGH))));
0171               }
0172               //skip to nextIter position
0173               edgeProcessed = true;
0174               continue;
0175             }
0176             //edgeProcessed = true;
0177           }
0178           ++dataIter;
0179         } //end while edge intersects rectangle data
0180 
0181     }
0182     if(!edgeProcessed) {
0183       if(haveCurrentRect) {
0184         if(currentRect.get(orient.get_perpendicular().get_direction(HIGH))
0185            == currentCoordinate &&
0186            currentRect.get(orient.get_direction(HIGH)) >= edge.get(LOW))
0187           {
0188             if(currentRect.get(orient.get_direction(HIGH)) > edge.get(LOW)){
0189               rectangle_type tmpRect(currentRect);
0190               tmpRect.set(orient.get_direction(HIGH), edge.get(LOW));
0191               scanData.insert(scanData.end(), tmpRect);
0192               if(currentRect.get(orient.get_direction(HIGH)) > edge.get(HIGH)) {
0193                 currentRect.set(orient,
0194                                 interval_data<coordinate_type>(edge.get(HIGH),
0195                                          currentRect.get(orient.get_direction(HIGH))));
0196                 return rectangles;
0197               } else {
0198                 haveCurrentRect = false;
0199                 return rectangles;
0200               }
0201             }
0202             //extend current rect
0203             currentRect.set(orient.get_direction(HIGH), edge.get(HIGH));
0204             return rectangles;
0205           }
0206         scanData.insert(scanData.end(), currentRect);
0207         haveCurrentRect = false;
0208       }
0209       rectangle_type tmpRect(currentRect);
0210       tmpRect.set(orient.get_perpendicular(), interval_data<coordinate_type>(currentCoordinate,
0211                                                       currentCoordinate));
0212       tmpRect.set(orient, edge);
0213       scanData.insert(tmpRect);
0214       return rectangles;
0215     }
0216     return rectangles;
0217 
0218   }
0219 
0220   template <class T>
0221   template <class CT>
0222   inline
0223   ScanLineToRects<T>& ScanLineToRects<T>::processEdge(CT& rectangles, const interval_data<coordinate_type>& edge)
0224   {
0225     processEdge_(rectangles, scanData_, edge, haveCurrentRect_, currentRect_, currentCoordinate_, orient_);
0226     return *this;
0227   }
0228 
0229 
0230 } //namespace rectangle_formation
0231 
0232   template <typename T, typename T2>
0233   struct get_coordinate_type_for_rectangles {
0234     typedef typename polygon_traits<T>::coordinate_type type;
0235   };
0236   template <typename T>
0237   struct get_coordinate_type_for_rectangles<T, rectangle_concept> {
0238     typedef typename rectangle_traits<T>::coordinate_type type;
0239   };
0240 
0241   template <typename output_container, typename iterator_type, typename rectangle_concept>
0242   void form_rectangles(output_container& output, iterator_type begin, iterator_type end,
0243                        orientation_2d orient, rectangle_concept ) {
0244     typedef typename output_container::value_type rectangle_type;
0245     typedef typename get_coordinate_type_for_rectangles<rectangle_type, typename geometry_concept<rectangle_type>::type>::type Unit;
0246     rectangle_data<Unit> model;
0247     Unit prevPos = (std::numeric_limits<Unit>::max)();
0248     rectangle_formation::ScanLineToRects<rectangle_data<Unit> > scanlineToRects(orient, model);
0249     for(iterator_type itr = begin;
0250         itr != end; ++ itr) {
0251       Unit pos = (*itr).first;
0252       if(pos != prevPos) {
0253         scanlineToRects.nextMajorCoordinate(pos);
0254         prevPos = pos;
0255       }
0256       Unit lowy = (*itr).second.first;
0257       iterator_type tmp_itr = itr;
0258       ++itr;
0259       Unit highy = (*itr).second.first;
0260       scanlineToRects.processEdge(output, interval_data<Unit>(lowy, highy));
0261       if(std::abs((*itr).second.second) > 1) itr = tmp_itr; //next edge begins from this vertex
0262     }
0263   }
0264 }
0265 }
0266 #endif
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!