diff options
Diffstat (limited to 'boost/polygon/detail/polygon_formation.hpp')
| -rw-r--r-- | boost/polygon/detail/polygon_formation.hpp | 374 |
1 files changed, 175 insertions, 199 deletions
diff --git a/boost/polygon/detail/polygon_formation.hpp b/boost/polygon/detail/polygon_formation.hpp index be2f54351d..f4c0d70d9c 100644 --- a/boost/polygon/detail/polygon_formation.hpp +++ b/boost/polygon/detail/polygon_formation.hpp @@ -1,6 +1,6 @@ /* Copyright 2008 Intel Corporation - + Use, modification and distribution are subject to the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt). @@ -27,24 +27,24 @@ namespace polygon_formation { * TAIL End is represented by true because TAIL comes after head and 1 after 0 */ const End TAIL = true; - + /* * 2D turning direction, left and right sides (is a boolean value since it has two states.) */ typedef bool Side; - + /* * LEFT Side is 0 because we inuitively think left to right; left < right */ const Side LEFT = false; - + /* * RIGHT Side is 1 so that right > left */ const Side RIGHT = true; /* - * The PolyLine class is data storage and services for building and representing partial polygons. + * The PolyLine class is data storage and services for building and representing partial polygons. * As the polyline is added to it extends its storage to accomodate the data. * PolyLines can be joined head-to-head/head-to-tail when it is determined that two polylines are * part of the same polygon. @@ -61,14 +61,14 @@ namespace polygon_formation { class PolyLine { private: //data - + /* * ptdata_ a vector of coordiantes * if VERTICAL_HEAD, first coordiante is an X * else first coordinate is a Y */ std::vector<Unit> ptdata_; - + /* * head and tail points to other polylines before and after this in a chain */ @@ -89,18 +89,18 @@ namespace polygon_formation { * default constructor (for preallocation) */ PolyLine(); - + /* * constructor that takes the orientation, coordiante and side to which there is solid */ PolyLine(orientation_2d orient, Unit coord, Side side); - + //copy constructor PolyLine(const PolyLine& pline); - + //destructor ~PolyLine(); - + //assignment operator PolyLine& operator=(const PolyLine& that); @@ -120,18 +120,18 @@ namespace polygon_formation { /* * returns true if first coordinate is an X value (first segment is vertical) */ - bool verticalHead() const; + bool verticalHead() const; /* * returns the orientation_2d fo the tail */ orientation_2d tailOrient() const; - + /* * returns true if last coordinate is an X value (last segment is vertical) */ bool verticalTail() const; - + /* * retrun true if PolyLine has odd number of coordiantes */ @@ -159,7 +159,7 @@ namespace polygon_formation { * retrun true if the tail of this polyline is connect to the head of a polyline */ bool tailToHead() const; - + /* * retrun the side on which there is solid for this polyline */ @@ -179,12 +179,12 @@ namespace polygon_formation { * adds a coordinate value to the end of the polyline changing the tail orientation */ PolyLine& pushCoordinate(Unit coord); - + /* * removes a coordinate value at the end of the polyline changing the tail orientation */ PolyLine& popCoordinate(); - + /* * extends the tail of the polyline to include the point, changing orientation if needed */ @@ -301,7 +301,7 @@ namespace polygon_formation { * that edge is supposed to be solid or space. Any incomplete polygon will have two active tails. Active tails * may be joined together to merge two incomplete polygons into a larger incomplete polygon. If two active tails * that are to be merged are the oppositve ends of the same incomplete polygon that indicates that the polygon - * has been closed and is complete. The active tail keeps a pointer to the other active tail of its incomplete + * has been closed and is complete. The active tail keeps a pointer to the other active tail of its incomplete * polygon so that it is easy to check this condition. These pointers are updated when active tails are joined. * The active tail also keeps a list of pointers to active tail objects that serve as handles to closed holes. In * this way a hole can be associated to another incomplete polygon, which will eventually be its enclosing shell, @@ -316,11 +316,11 @@ namespace polygon_formation { class ActiveTail { private: //data - PolyLine<Unit>* tailp_; + PolyLine<Unit>* tailp_; ActiveTail *otherTailp_; std::list<ActiveTail*> holesList_; //Sum of all the polylines which constitute the active tail (including holes)// - size_t polyLineSize_; + size_t polyLineSize_; public: inline size_t getPolyLineSize(){ @@ -334,7 +334,7 @@ namespace polygon_formation { inline void addPolyLineSize(int delta){ polyLineSize_ += delta; } - + /* * iterator over coordinates of the figure */ @@ -347,7 +347,7 @@ namespace polygon_formation { End startEnd_; public: inline iterator() : pLine_(), pLineEnd_(), index_(), indexEnd_(), startEnd_() {} - inline iterator(const ActiveTail* at, bool isHole, orientation_2d orient) : + inline iterator(const ActiveTail* at, bool isHole, orientation_2d orient) : pLine_(), pLineEnd_(), index_(), indexEnd_(), startEnd_() { //if it is a hole and orientation is vertical or it is not a hole and orientation is horizontal //we want to use this active tail, otherwise we want to use the other active tail @@ -391,11 +391,11 @@ namespace polygon_formation { while(currLine != pLineEnd_){ ops++; count += currLine->numSegments(); - currLine = currLine->next(dir == HEAD ? TAIL : HEAD); - dir = currLine->endConnectivity(dir == HEAD ? TAIL : HEAD); + currLine = currLine->next(dir == HEAD ? TAIL : HEAD); + dir = currLine->endConnectivity(dir == HEAD ? TAIL : HEAD); } count += pLineEnd_->numSegments(); - return count; //no. of vertices + return count; //no. of vertices } //use bitwise copy and assign provided by the compiler @@ -596,7 +596,7 @@ namespace polygon_formation { /* deallocate an activetail object */ template <typename Unit> void destroyActiveTail(ActiveTail<Unit>* aTail); - + template<bool orientT, typename Unit> class PolyLineHoleData { private: @@ -612,19 +612,10 @@ namespace polygon_formation { inline compact_iterator_type end_compact() const { return p_->end(); } inline iterator_type begin() const { return iterator_type(begin_compact(), end_compact()); } inline iterator_type end() const { return iterator_type(end_compact(), end_compact()); } - inline std::size_t size() const { + inline std::size_t size() const { return p_->getPolyLineSize(); } inline ActiveTail<Unit>* yield() { return p_; } - template<class iT> - inline PolyLineHoleData& set(iT inputBegin, iT inputEnd) { - return *this; - } - template<class iT> - inline PolyLineHoleData& set_compact(iT inputBegin, iT inputEnd) { - return *this; - } - }; template<bool orientT, typename Unit> @@ -676,21 +667,6 @@ namespace polygon_formation { //stub out these four required functions that will not be used but are needed for the interface inline std::size_t size_holes() const { return 0; } inline std::size_t size() const { return 0; } - template<class iT> - inline PolyLinePolygonWithHolesData& set(iT inputBegin, iT inputEnd) { - return *this; - } - template<class iT> - inline PolyLinePolygonWithHolesData& set_compact(iT inputBegin, iT inputEnd) { - return *this; - } - - // initialize a polygon from x,y values, it is assumed that the first is an x - // and that the input is a well behaved polygon - template<class iT> - inline PolyLinePolygonWithHolesData& set_holes(iT inputBegin, iT inputEnd) { - return *this; - } }; @@ -717,34 +693,34 @@ namespace polygon_formation { std::vector<PolyLinePolygonData> outputPolygons_; bool fractureHoles_; public: - typedef typename std::vector<PolyLinePolygonData>::iterator iterator; + typedef typename std::vector<PolyLinePolygonData>::iterator iterator; inline ScanLineToPolygonItrs() : tailMap_(), outputPolygons_(), fractureHoles_(false) {} /* construct a scanline with the proper offsets, protocol and options */ inline ScanLineToPolygonItrs(bool fractureHoles) : tailMap_(), outputPolygons_(), fractureHoles_(fractureHoles) {} - + ~ScanLineToPolygonItrs() { clearOutput_(); } - + /* process all vertical edges, left and right, at a unique x coordinate, edges must be sorted low to high */ - void processEdges(iterator& beginOutput, iterator& endOutput, - Unit currentX, std::vector<interval_data<Unit> >& leftEdges, + void processEdges(iterator& beginOutput, iterator& endOutput, + Unit currentX, std::vector<interval_data<Unit> >& leftEdges, std::vector<interval_data<Unit> >& rightEdges, size_t vertexThreshold=(std::numeric_limits<size_t>::max)() ); - + /********************************************************************** - *methods implementing new polygon formation code + *methods implementing new polygon formation code * **********************************************************************/ - void updatePartialSimplePolygonsWithRightEdges(Unit currentX, + void updatePartialSimplePolygonsWithRightEdges(Unit currentX, const std::vector<interval_data<Unit> >& leftEdges, size_t threshold); - void updatePartialSimplePolygonsWithLeftEdges(Unit currentX, + void updatePartialSimplePolygonsWithLeftEdges(Unit currentX, const std::vector<interval_data<Unit> >& leftEdges, size_t threshold); void closePartialSimplePolygon(Unit, ActiveTail<Unit>*, ActiveTail<Unit>*); void maintainPartialSimplePolygonInvariant(iterator& ,iterator& ,Unit, - const std::vector<interval_data<Unit> >&, - const std::vector<interval_data<Unit> >&, + const std::vector<interval_data<Unit> >&, + const std::vector<interval_data<Unit> >&, size_t vertexThreshold=(std::numeric_limits<size_t>::max)()); void insertNewLeftEdgeIntoTailMap(Unit, Unit, Unit, @@ -769,7 +745,7 @@ namespace polygon_formation { ActiveTail<Unit> const *t = (itr->second); PolyLine<Unit> const *pBegin = t->getTail(); PolyLine<Unit> const *pEnd = t->getOtherActiveTail()->getTail(); - std::string sorient = pBegin->solidToRight() ? "RIGHT" : "LEFT"; + std::string sorient = pBegin->solidToRight() ? "RIGHT" : "LEFT"; std::cout<< " ActiveTail.tailp_ (solid= " << sorient ; End dir = TAIL; while(pBegin!=pEnd){ @@ -793,7 +769,7 @@ namespace polygon_formation { std::cout << " end= " << pEnd << std::endl; } } - + private: void clearOutput_(); }; @@ -809,9 +785,9 @@ namespace polygon_formation { // inline ScanLineToPolygons() : scanline_() {} // /* construct a scanline with the proper offsets, protocol and options */ // inline ScanLineToPolygons(bool fractureHoles) : scanline_(fractureHoles) {} - + // /* process all vertical edges, left and right, at a unique x coordinate, edges must be sorted low to high */ -// inline void processEdges(std::vector<Unit>& outBufferTmp, Unit currentX, std::vector<interval_data<Unit> >& leftEdges, +// inline void processEdges(std::vector<Unit>& outBufferTmp, Unit currentX, std::vector<interval_data<Unit> >& leftEdges, // std::vector<interval_data<Unit> >& rightEdges) { // typename ScanLineToPolygonItrs<true, Unit>::iterator itr, endItr; // scanline_.processEdges(itr, endItr, currentX, leftEdges, rightEdges); @@ -857,7 +833,7 @@ namespace polygon_formation { //constructor template <typename Unit> - inline PolyLine<Unit>::PolyLine(orientation_2d orient, Unit coord, Side side) : + inline PolyLine<Unit>::PolyLine(orientation_2d orient, Unit coord, Side side) : ptdata_(1, coord), headp_(0), tailp_(0), @@ -899,7 +875,7 @@ namespace polygon_formation { //valid PolyLine template <typename Unit> - inline bool PolyLine<Unit>::isValid() const { + inline bool PolyLine<Unit>::isValid() const { return state_ > -1; } //first coordinate is an X value @@ -921,7 +897,7 @@ namespace polygon_formation { inline bool PolyLine<Unit>::verticalTail() const { return to_bool(verticalHead() ^ oddLength()); } - + template <typename Unit> inline orientation_2d PolyLine<Unit>::tailOrient() const { return (verticalTail() ? VERTICAL : HORIZONTAL); @@ -953,16 +929,16 @@ namespace polygon_formation { inline bool PolyLine<Unit>::tailToHead() const { return to_bool(!tailToTail()); } - + template <typename Unit> inline bool PolyLine<Unit>::tailToTail() const { return to_bool(state_ & TAIL_TO_TAIL); } template <typename Unit> - inline Side PolyLine<Unit>::solidSide() const { + inline Side PolyLine<Unit>::solidSide() const { return solidToRight(); } - + template <typename Unit> inline bool PolyLine<Unit>::solidToRight() const { return to_bool(state_ & SOLID_TO_RIGHT) != 0; @@ -1112,11 +1088,11 @@ namespace polygon_formation { } template <typename Unit> - inline ActiveTail<Unit>::ActiveTail() : tailp_(0), otherTailp_(0), holesList_(), + inline ActiveTail<Unit>::ActiveTail() : tailp_(0), otherTailp_(0), holesList_(), polyLineSize_(0) {} template <typename Unit> - inline ActiveTail<Unit>::ActiveTail(orientation_2d orient, Unit coord, Side solidToRight, ActiveTail* otherTailp) : + inline ActiveTail<Unit>::ActiveTail(orientation_2d orient, Unit coord, Side solidToRight, ActiveTail* otherTailp) : tailp_(0), otherTailp_(0), holesList_(), polyLineSize_(0) { tailp_ = createPolyLine(orient, coord, solidToRight); otherTailp_ = otherTailp; @@ -1124,8 +1100,8 @@ namespace polygon_formation { } template <typename Unit> - inline ActiveTail<Unit>::ActiveTail(PolyLine<Unit>* active, ActiveTail<Unit>* otherTailp) : - tailp_(active), otherTailp_(otherTailp), holesList_(), + inline ActiveTail<Unit>::ActiveTail(PolyLine<Unit>* active, ActiveTail<Unit>* otherTailp) : + tailp_(active), otherTailp_(otherTailp), holesList_(), polyLineSize_(0) {} //copy constructor @@ -1134,9 +1110,9 @@ namespace polygon_formation { //destructor template <typename Unit> - inline ActiveTail<Unit>::~ActiveTail() { + inline ActiveTail<Unit>::~ActiveTail() { //clear them in case the memory is read later - tailp_ = 0; otherTailp_ = 0; + tailp_ = 0; otherTailp_ = 0; } template <typename Unit> @@ -1159,33 +1135,33 @@ namespace polygon_formation { } template <typename Unit> - inline bool ActiveTail<Unit>::operator<=(const ActiveTail<Unit>& b) const { + inline bool ActiveTail<Unit>::operator<=(const ActiveTail<Unit>& b) const { return !(*this > b); } - + template <typename Unit> - inline bool ActiveTail<Unit>::operator>(const ActiveTail<Unit>& b) const { + inline bool ActiveTail<Unit>::operator>(const ActiveTail<Unit>& b) const { return b < (*this); } - + template <typename Unit> - inline bool ActiveTail<Unit>::operator>=(const ActiveTail<Unit>& b) const { + inline bool ActiveTail<Unit>::operator>=(const ActiveTail<Unit>& b) const { return !(*this < b); } template <typename Unit> - inline PolyLine<Unit>* ActiveTail<Unit>::getTail() const { + inline PolyLine<Unit>* ActiveTail<Unit>::getTail() const { return tailp_; } template <typename Unit> - inline PolyLine<Unit>* ActiveTail<Unit>::getOtherTail() const { + inline PolyLine<Unit>* ActiveTail<Unit>::getOtherTail() const { return otherTailp_->tailp_; } template <typename Unit> - inline ActiveTail<Unit>* ActiveTail<Unit>::getOtherActiveTail() const { + inline ActiveTail<Unit>* ActiveTail<Unit>::getOtherActiveTail() const { return otherTailp_; } template <typename Unit> inline bool ActiveTail<Unit>::isOtherTail(const ActiveTail<Unit>& b) { // assert( (tailp_ == b.getOtherTail() && getOtherTail() == b.tailp_) || - // (tailp_ != b.getOtherTail() && getOtherTail() != b.tailp_)) + // (tailp_ != b.getOtherTail() && getOtherTail() != b.tailp_)) // ("ActiveTail: Active tails out of sync"); return otherTailp_ == &b; } @@ -1214,7 +1190,7 @@ namespace polygon_formation { if(other->getOrient() == VERTICAL) { //assert that hole.getOrient() == HORIZONTAL //this case should never happen - h = hole; + h = hole; v = other; } else { //assert that hole.getOrient() == VERTICAL @@ -1242,23 +1218,23 @@ namespace polygon_formation { } template <typename Unit> - inline bool ActiveTail<Unit>::solidToRight() const { + inline bool ActiveTail<Unit>::solidToRight() const { return getTail()->solidToRight(); } template <typename Unit> - inline Unit ActiveTail<Unit>::getCoord() const { + inline Unit ActiveTail<Unit>::getCoord() const { return getTail()->getEndCoord(); } - + template <typename Unit> - inline Unit ActiveTail<Unit>::getCoordinate() const { - return getCoord(); } + inline Unit ActiveTail<Unit>::getCoordinate() const { + return getCoord(); } template <typename Unit> - inline orientation_2d ActiveTail<Unit>::getOrient() const { + inline orientation_2d ActiveTail<Unit>::getOrient() const { return getTail()->tailOrient(); } template <typename Unit> - inline void ActiveTail<Unit>::pushCoordinate(Unit coord) { + inline void ActiveTail<Unit>::pushCoordinate(Unit coord) { //appropriately handle any co-linear polyline segments by calling push point internally point_data<Unit> p; p.set(HORIZONTAL, coord); @@ -1359,16 +1335,16 @@ namespace polygon_formation { if((getOrient() == HORIZONTAL) ^ !isHole) { //our first coordinate is a y value, so we need to rotate it to the end typename std::vector<Unit>::iterator tmpItr = outVec.begin(); - tmpItr += size; + tmpItr += size; outVec.erase(++tmpItr); //erase the 2nd element } End startEnd = tailp_->endConnectivity(HEAD); if(isHole) startEnd = otherTailp_->tailp_->endConnectivity(HEAD); while(nextPolyLinep) { bool nextStartEnd = nextPolyLinep->endConnectivity(!startEnd); - nextPolyLinep = nextPolyLinep->writeOut(outVec, startEnd); + nextPolyLinep = nextPolyLinep->writeOut(outVec, startEnd); startEnd = nextStartEnd; - } + } if((getOrient() == HORIZONTAL) ^ !isHole) { //we want to push the y value onto the end since we ought to have ended with an x outVec.push_back(firsty); //should never be executed because we want first value to be an x @@ -1402,7 +1378,7 @@ namespace polygon_formation { //solid indicates if it was joined by a solit or a space template <typename Unit> - inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid, std::vector<Unit>& outBufferTmp) + inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid, std::vector<Unit>& outBufferTmp) { //checks to see if we closed a figure if(at1->isOtherTail(*at2)){ @@ -1457,7 +1433,7 @@ namespace polygon_formation { //solid indicates if it was joined by a solit or a space template <typename Unit> template <typename PolygonT> - inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid, + inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid, std::vector<PolygonT>& outBufferTmp) { //checks to see if we closed a figure if(at1->isOtherTail(*at2)){ @@ -1471,7 +1447,7 @@ namespace polygon_formation { //because otherwise it would have to have another vertex to the right of this one //and would not be closed at this point return at1; - } else { + } else { //assert pG != 0 //the figure that was closed is a shell outBufferTmp.push_back(at1); @@ -1495,8 +1471,8 @@ namespace polygon_formation { return 0; } - template <class TKey, class T> inline typename std::map<TKey, T>::iterator findAtNext(std::map<TKey, T>& theMap, - typename std::map<TKey, T>::iterator pos, const TKey& key) + template <class TKey, class T> inline typename std::map<TKey, T>::iterator findAtNext(std::map<TKey, T>& theMap, + typename std::map<TKey, T>::iterator pos, const TKey& key) { if(pos == theMap.end()) return theMap.find(key); //if they match the mapItr is pointing to the correct position @@ -1505,22 +1481,22 @@ namespace polygon_formation { } if(pos->first > key) { return theMap.end(); - } + } //else they are equal and no need to do anything to the iterator return pos; } // createActiveTailsAsPair is called in these two end cases of geometry // 1. lower left concave corner - // ###| // ###| - // ###|### + // ###| + // ###|### // ###|### // 2. lower left convex corner - // |### - // |### - // | - // | + // |### + // |### + // | + // | // In case 1 there may be a hole propigated up from the bottom. If the fracture option is enabled // the two active tails that form the filament fracture line edges can become the new active tail pair // by pushing x and y onto them. Otherwise the hole simply needs to be associated to one of the new active tails @@ -1540,7 +1516,7 @@ namespace polygon_formation { at1->addPolyLineSize(1); at2->addPolyLineSize(1); - if(phole) + if(phole) at1->addHole(phole, fractureHoles); //assert fractureHoles == false return std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*>(at1, at2); } @@ -1561,7 +1537,7 @@ namespace polygon_formation { return std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*>(at1, at2); } - /* + /* * | * | * = @@ -1581,10 +1557,10 @@ namespace polygon_formation { insertNewLeftEdgeIntoTailMap(Unit currentX, Unit yBegin, Unit yEnd, typename std::map<Unit, ActiveTail<Unit> *>::iterator &hint){ ActiveTail<Unit> *currentTail = NULL; - std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = - createActiveTailsAsPair(currentX, yBegin, true, currentTail, + std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = + createActiveTailsAsPair(currentX, yBegin, true, currentTail, fractureHoles_); - currentTail = tailPair.first; + currentTail = tailPair.first; if(!tailMap_.empty()){ ++hint; } @@ -1631,8 +1607,8 @@ namespace polygon_formation { hint = tailMap_.begin(); for(size_t i=0; i < leftEdges.size(); i++){ begin = leftEdges[i].get(LOW); end = leftEdges[i].get(HIGH); - succ = findAtNext(tailMap_, hint, begin); - pred = findAtNext(tailMap_, hint, end); + succ = findAtNext(tailMap_, hint, begin); + pred = findAtNext(tailMap_, hint, end); if(succ != tailMap_.end() && pred != tailMap_.end()){ //CASE-1// //join the corresponding active tails// @@ -1646,7 +1622,7 @@ namespace polygon_formation { if(usize+2 < vertexThreshold){ //cut-off the lower piece (succ1, succ) join (succ1, pred)// succ1 = succ; --succ1; - assert((succ1 != tailMap_.end()) && + assert((succ1 != tailMap_.end()) && ((succ->second)->getOtherActiveTail() == succ1->second)); closePartialSimplePolygon(currentX, succ1->second, succ->second); tailPair = createActiveTailsAsPair<Unit>(currentX, succ1->first, @@ -1659,7 +1635,7 @@ namespace polygon_formation { }else if(bsize+2 < vertexThreshold){ //cut-off the upper piece () join ()// pred1 = pred; ++pred1; - assert(pred1 != tailMap_.end() && + assert(pred1 != tailMap_.end() && ((pred1->second)->getOtherActiveTail() == pred->second)); closePartialSimplePolygon(currentX, pred->second, pred1->second); @@ -1667,11 +1643,11 @@ namespace polygon_formation { pred1->second = pfig; pfig->pushCoordinate(currentX); pfig->pushCoordinate(pred1->first); - }else{ + }else{ //cut both and create an left edge between (pred->first, succ1)// - succ1 = succ; --succ1; + succ1 = succ; --succ1; pred1 = pred; ++pred1; - assert(pred1 != tailMap_.end() && succ1 != tailMap_.end()); + assert(pred1 != tailMap_.end() && succ1 != tailMap_.end()); assert((pred1->second)->getOtherActiveTail() == pred->second); assert((succ1->second)->getOtherActiveTail() == succ->second); @@ -1689,11 +1665,11 @@ namespace polygon_formation { pfig->pushCoordinate(currentX); ActiveTail<Unit>::joinChains(pfig, ppfig, true, outputPolygons_); } - hint = pred; ++hint; + hint = pred; ++hint; tailMap_.erase(succ); tailMap_.erase(pred); }else if(succ == tailMap_.end() && pred != tailMap_.end()){ //CASE-2// //succ is missing in the map, first insert it into the map// - tailPair = createActiveTailsAsPair<Unit>(currentX, begin, true, NULL, + tailPair = createActiveTailsAsPair<Unit>(currentX, begin, true, NULL, fractureHoles_); hint = pred; ++hint; hint = tailMap_.insert(hint, std::make_pair(begin, tailPair.second)); @@ -1703,7 +1679,7 @@ namespace polygon_formation { if(pfig_size >= vertexThreshold){ //cut-off piece from [pred, pred1] , add [begin, pred1]// pred1 = pred; ++pred1; - assert((pred1 != tailMap_.end()) && + assert((pred1 != tailMap_.end()) && ((pred1->second)->getOtherActiveTail() == pred->second)); closePartialSimplePolygon(currentX, pred->second, pred1->second); @@ -1712,7 +1688,7 @@ namespace polygon_formation { (tailPair.first)->pushCoordinate(pred1->first); }else{ //just join// - ActiveTail<Unit>::joinChains(tailPair.first, pfig, + ActiveTail<Unit>::joinChains(tailPair.first, pfig, true, outputPolygons_); } tailMap_.erase(pred); @@ -1753,19 +1729,19 @@ namespace polygon_formation { template<bool orientT, typename Unit, typename polygon_concept_type> inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>:: updatePartialSimplePolygonsWithRightEdges(Unit currentX, - const std::vector<interval_data<Unit> > &rightEdges, size_t vertexThreshold) + const std::vector<interval_data<Unit> > &rightEdges, size_t vertexThreshold) { - + typename std::map<Unit, ActiveTail<Unit>* >::iterator succ, pred, hint; - std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair; + std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair; Unit begin, end; size_t i = 0; //If rightEdges is non-empty Then tailMap_ is non-empty // assert(rightEdges.empty() || !tailMap_.empty() ); while( i < rightEdges.size() ){ - //find the interval in the tailMap which contains this interval// - pred = tailMap_.lower_bound(rightEdges[i].get(HIGH)); + //find the interval in the tailMap which contains this interval// + pred = tailMap_.lower_bound(rightEdges[i].get(HIGH)); assert(pred != tailMap_.end()); succ = pred; --succ; assert(pred != succ); @@ -1794,11 +1770,11 @@ namespace polygon_formation { if(rightEdges[j-1].get(HIGH) != rightEdges[j].get(LOW)){ if(!found_solid_opening){ found_solid_opening = true; - solid_opening_begin = rightEdges[j-1].get(HIGH); + solid_opening_begin = rightEdges[j-1].get(HIGH); solid_opening_end = rightEdges[j].get(LOW); }else{ ++hint; - insertNewLeftEdgeIntoTailMap(currentX, + insertNewLeftEdgeIntoTailMap(currentX, rightEdges[j-1].get(HIGH), rightEdges[j].get(LOW), hint); } } @@ -1810,9 +1786,9 @@ namespace polygon_formation { if(!found_solid_opening){ found_solid_opening = true; solid_opening_begin = rightEdges[j-1].get(HIGH); solid_opening_end = end; - }else{ - // a solid opening has been found already, we need to insert a new left - // between [rightEdges[j-1].get(HIGH), end] + }else{ + // a solid opening has been found already, we need to insert a new left + // between [rightEdges[j-1].get(HIGH), end] Unit lbegin = rightEdges[j-1].get(HIGH); tailPair = createActiveTailsAsPair<Unit>(currentX, lbegin, true, NULL, fractureHoles_); @@ -1823,7 +1799,7 @@ namespace polygon_formation { } } - size_t vertex_delta = ((begin != solid_opening_begin) && + size_t vertex_delta = ((begin != solid_opening_begin) && (end != solid_opening_end)) ? 4 : 2; if(!found_solid_opening){ @@ -1837,7 +1813,7 @@ namespace polygon_formation { assert(begin != solid_opening_begin || end != solid_opening_end); if(begin != solid_opening_begin && end != solid_opening_end){ - insertNewLeftEdgeIntoTailMap(currentX, solid_opening_begin, + insertNewLeftEdgeIntoTailMap(currentX, solid_opening_begin, solid_opening_end, hint); }else if(begin == solid_opening_begin){ //we just need to update the succ in the tailMap_// @@ -1845,7 +1821,7 @@ namespace polygon_formation { true, NULL, fractureHoles_); succ->second = tailPair.second; hint = succ; ++hint; - hint = tailMap_.insert(pred, std::make_pair(solid_opening_end, + hint = tailMap_.insert(pred, std::make_pair(solid_opening_end, tailPair.first)); (tailPair.first)->pushCoordinate(solid_opening_end); erase_succ = false; @@ -1872,13 +1848,13 @@ namespace polygon_formation { } if(end != solid_opening_end){ - std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = - createActiveTailsAsPair<Unit>(currentX, solid_opening_end, false, + std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = + createActiveTailsAsPair<Unit>(currentX, solid_opening_end, false, NULL, fractureHoles_); hint = pred; ++hint; - hint = tailMap_.insert(hint, std::make_pair(solid_opening_end, + hint = tailMap_.insert(hint, std::make_pair(solid_opening_end, tailPair.second)); - ActiveTail<Unit>::joinChains(tailPair.first, ppfig, false, + ActiveTail<Unit>::joinChains(tailPair.first, ppfig, false, outputPolygons_); }else{ erase_pred = false; @@ -1897,12 +1873,12 @@ namespace polygon_formation { } // Maintains the following invariant: - // a. All the partial polygons formed at any state can be closed + // a. All the partial polygons formed at any state can be closed // by a single edge. template<bool orientT, typename Unit, typename polygon_concept_type> inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>:: - maintainPartialSimplePolygonInvariant(iterator& beginOutput, - iterator& endOutput, Unit currentX, const std::vector<interval_data<Unit> >& l, + maintainPartialSimplePolygonInvariant(iterator& beginOutput, + iterator& endOutput, Unit currentX, const std::vector<interval_data<Unit> >& l, const std::vector<interval_data<Unit> >& r, size_t vertexThreshold) { clearOutput_(); @@ -1917,109 +1893,109 @@ namespace polygon_formation { endOutput = outputPolygons_.end(); } - + //Process edges connects vertical input edges (right or left edges of figures) to horizontal edges stored as member //data of the scanline object. It also creates now horizontal edges as needed to construct figures from edge data. // - //There are only 12 geometric end cases where the scanline intersects a horizontal edge and even fewer unique + //There are only 12 geometric end cases where the scanline intersects a horizontal edge and even fewer unique //actions to take: // 1. Solid on both sides of the vertical partition after the current position and space on both sides before - // ###|### - // ###|### - // | - // | + // ###|### + // ###|### + // | + // | // This case does not need to be handled because there is no vertical edge at the current x coordinate. // // 2. Solid on both sides of the vertical partition before the current position and space on both sides after - // | - // | - // ###|### - // ###|### + // | + // | + // ###|### + // ###|### // This case does not need to be handled because there is no vertical edge at the current x coordinate. // // 3. Solid on the left of the vertical partition after the current position and space elsewhere - // ###| - // ###| - // | - // | + // ###| + // ###| + // | + // | // The horizontal edge from the left is found and turns upward because of the vertical right edge to become // the currently active vertical edge. // // 4. Solid on the left of the vertical partion before the current position and space elsewhere - // | - // | - // ###| + // | + // | + // ###| // ###| // The horizontal edge from the left is found and joined to the currently active vertical edge. // // 5. Solid to the right above and below and solid to the left above current position. - // ###|### - // ###|### - // |### - // |### + // ###|### + // ###|### + // |### + // |### // The horizontal edge from the left is found and joined to the currently active vertical edge, // potentially closing a hole. // // 6. Solid on the left of the vertical partion before the current position and solid to the right above and below // |### - // |### - // ###|### + // |### + // ###|### // ###|### // The horizontal edge from the left is found and turns upward because of the vertical right edge to become // the currently active vertical edge. // // 7. Solid on the right of the vertical partition after the current position and space elsewhere - // |### - // |### - // | - // | + // |### + // |### + // | + // | // Create two new ActiveTails, one is added to the horizontal edges and the other becomes the vertical currentTail // // 8. Solid on the right of the vertical partion before the current position and space elsewhere - // | - // | - // |### + // | + // | + // |### // |### // The currentTail vertical edge turns right and is added to the horizontal edges data // // 9. Solid to the right above and solid to the left above and below current position. - // ###|### - // ###|### - // ###| + // ###|### + // ###|### + // ###| // ###| // The currentTail vertical edge turns right and is added to the horizontal edges data // // 10. Solid on the left of the vertical partion above and below the current position and solid to the right below - // ###| // ###| - // ###|### + // ###| + // ###|### // ###|### // Create two new ActiveTails, one is added to the horizontal edges data and the other becomes the vertical currentTail // // 11. Solid to the right above and solid to the left below current position. - // |### // |### - // ###| + // |### + // ###| // ###| // The currentTail vertical edge joins the horizontal edge from the left (may close a polygon) // Create two new ActiveTails, one is added to the horizontal edges data and the other becomes the vertical currentTail // // 12. Solid on the left of the vertical partion above the current position and solid to the right below - // ###| // ###| - // |### + // ###| + // |### // |### // The currentTail vertical edge turns right and is added to the horizontal edges data. // The horizontal edge from the left turns upward and becomes the currentTail vertical edge // template <bool orientT, typename Unit, typename polygon_concept_type> inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>:: - processEdges(iterator& beginOutput, iterator& endOutput, - Unit currentX, std::vector<interval_data<Unit> >& leftEdges, + processEdges(iterator& beginOutput, iterator& endOutput, + Unit currentX, std::vector<interval_data<Unit> >& leftEdges, std::vector<interval_data<Unit> >& rightEdges, size_t vertexThreshold) { clearOutput_(); - typename std::map<Unit, ActiveTail<Unit>*>::iterator nextMapItr; + typename std::map<Unit, ActiveTail<Unit>*>::iterator nextMapItr; //foreach edge unsigned int leftIndex = 0; unsigned int rightIndex = 0; @@ -2035,7 +2011,7 @@ namespace polygon_formation { nextMapItr = tailMap_.begin(); while(leftIndex < leftEdges.size() || rightIndex < rightEdges.size()) { - interval_data<Unit> edges[2] = {interval_data<Unit> (UnitMax, UnitMax), + interval_data<Unit> edges[2] = {interval_data<Unit> (UnitMax, UnitMax), interval_data<Unit> (UnitMax, UnitMax)}; bool haveNextEdge = true; if(leftIndex < leftEdges.size()) @@ -2051,7 +2027,7 @@ namespace polygon_formation { interval_data<Unit> & nextEdge = edges[!trailingEdge]; //process this edge if(!bottomAlreadyProcessed) { - //assert currentTail = 0 + //assert currentTail = 0 //process the bottom end of this edge typename std::map<Unit, ActiveTail<Unit>*>::iterator thisMapItr = findAtNext(tailMap_, nextMapItr, edge.get(LOW)); @@ -2078,7 +2054,7 @@ namespace polygon_formation { //we need to create one and another one to be the current vertical tail //if this is a trailing edge then there is space to the right of the vertical edge //so pass the inverse of trailingEdge to indicate solid to the right - std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = + std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = createActiveTailsAsPair(currentX, edge.get(LOW), !trailingEdge, currentTail, fractureHoles_); currentTail = tailPair.first; tailMap_.insert(nextMapItr, std::pair<Unit, ActiveTail<Unit>*>(edge.get(LOW), tailPair.second)); @@ -2106,7 +2082,7 @@ namespace polygon_formation { //two new tails are created, the vertical becomes current tail, the horizontal becomes thisMapItr tail //pass true becuase they are created at the lower left corner of some solid //pass null because there is no hole pointer possible - std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = + std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = createActiveTailsAsPair<Unit>(currentX, edge.get(HIGH), true, 0, fractureHoles_); currentTail = tailPair.first; thisMapItr->second = tailPair.second; @@ -2162,7 +2138,7 @@ namespace polygon_formation { //set current tail to null currentTail = 0; } - } + } //delete thisMapItr from the map tailMap_.erase(thisMapItr); } else { @@ -2175,7 +2151,7 @@ namespace polygon_formation { //leave nextMapItr unchanged, it is still next } } - + //increment index leftIndex += !trailingEdge; rightIndex += trailingEdge; @@ -2218,9 +2194,9 @@ namespace polygon_formation { //public API to access polygon formation algorithm template <typename output_container, typename iterator_type, typename concept_type> - unsigned int get_polygons(output_container& container, - iterator_type begin, iterator_type end, orientation_2d orient, - bool fracture_holes, concept_type, + unsigned int get_polygons(output_container& container, + iterator_type begin, iterator_type end, orientation_2d orient, + bool fracture_holes, concept_type, size_t sliceThreshold = (std::numeric_limits<size_t>::max)() ) { typedef typename output_container::value_type polygon_type; typedef typename std::iterator_traits<iterator_type>::value_type::first_type coordinate_type; @@ -2240,7 +2216,7 @@ namespace polygon_formation { if(pos != prevPos) { if(orient == VERTICAL) { typename polygon_formation::ScanLineToPolygonItrs<true, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd; - scanlineToPolygonItrsV.processEdges(itrPoly, itrPolyEnd, prevPos, + scanlineToPolygonItrsV.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges, sliceThreshold); for( ; itrPoly != itrPolyEnd; ++ itrPoly) { ++countPolygons; @@ -2249,7 +2225,7 @@ namespace polygon_formation { } } else { typename polygon_formation::ScanLineToPolygonItrs<false, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd; - scanlineToPolygonItrsH.processEdges(itrPoly, itrPolyEnd, prevPos, + scanlineToPolygonItrsH.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges, sliceThreshold); for( ; itrPoly != itrPolyEnd; ++ itrPoly) { ++countPolygons; |