/* 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). */ #include #include #ifndef BOOST_POLYGON_POLYGON_FORMATION_HPP #define BOOST_POLYGON_POLYGON_FORMATION_HPP namespace boost { namespace polygon{ namespace polygon_formation { /* * End has two states, HEAD and TAIL as is represented by a bool */ typedef bool End; /* * HEAD End is represented as false because it is the lesser state */ const End HEAD = false; /* * 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. * 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. * PolyLines keep state information about what orientation their incomplete head and tail geometry have, * which side of the polyline is solid and whether the polyline is joined head-to-head and tail-to-head. * PolyLines have nothing whatsoever to do with holes. * It may be valuable to collect a histogram of PolyLine lengths used by an algorithm on its typical data * sets and tune the allocation of the initial vector of coordinate data to be greater than or equal to * the mean, median, mode, or mean plus some number of standard deviation, or just generally large enough * to prevent too much unnecesary reallocations, but not too big that it wastes a lot of memory and degrades cache * performance. */ template 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 ptdata_; /* * head and tail points to other polylines before and after this in a chain */ PolyLine* headp_; PolyLine* tailp_; /* * state bitmask * bit zero is orientation, 0 H, 1 V * bit 1 is head connectivity, 0 for head, 1 for tail * bit 2 is tail connectivity, 0 for head, 1 for tail * bit 3 is solid to left of PolyLine when 1, right when 0 */ int state_; public: /* * 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); //equivalence operator bool operator==(const PolyLine& b) const; /* * valid PolyLine (only default constructed polylines are invalid.) */ bool isValid() const; /* * Orientation of Head */ orientation_2d headOrient() const; /* * returns true if first coordinate is an X value (first segment is vertical) */ 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 */ bool oddLength() const; /* * retrun the End of the other polyline that the specified end of this polyline is connected to */ End endConnectivity(End end) const; /* * retrun true if the head of this polyline is connect to the tail of a polyline */ bool headToTail() const; /* * retrun true if the head of this polyline is connect to the head of a polyline */ bool headToHead() const; /* * retrun true if the tail of this polyline is connect to the tail of a polyline */ bool tailToTail() const; /* * 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 */ Side solidSide() const; /* * retrun true if there is solid to the right of this polyline */ bool solidToRight() const; /* * returns true if the polyline tail is not connected */ bool active() const; /* * 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 */ PolyLine& pushPoint(const point_data& point); /* * changes the last coordinate of the tail of the polyline by the amount of the delta */ PolyLine& extendTail(Unit delta); /* * join thisEnd of this polyline to that polyline's end */ PolyLine& joinTo(End thisEnd, PolyLine& that, End end); /* * join an end of this polyline to the tail of that polyline */ PolyLine& joinToTail(PolyLine& that, End end); /* * join an end of this polyline to the head of that polyline */ PolyLine& joinToHead(PolyLine& that, End end); /* * join the head of this polyline to the head of that polyline */ //join this to that in the given way PolyLine& joinHeadToHead(PolyLine& that); /* * join the head of this polyline to the tail of that polyline */ PolyLine& joinHeadToTail(PolyLine& that); /* * join the tail of this polyline to the head of that polyline */ PolyLine& joinTailToHead(PolyLine& that); /* * join the tail of this polyline to the tail of that polyline */ PolyLine& joinTailToTail(PolyLine& that); /* * dissconnect the tail at the end of the polygon */ PolyLine& disconnectTails(); /* * get the coordinate at one end of this polyline, by default the tail end */ Unit getEndCoord(End end = TAIL) const; /* * get the point on the polyline at the given index (polylines have the same number of coordinates as points */ point_data getPoint(unsigned int index) const; /* * get the point on one end of the polyline, by default the tail */ point_data getEndPoint(End end = TAIL) const; /* * get the orientation of a segment by index */ orientation_2d segmentOrient(unsigned int index = 0) const; /* * get a coordinate by index using the square bracket operator */ Unit operator[] (unsigned int index) const; /* * get the number of segments/points/coordinates in the polyline */ unsigned int numSegments() const; /* * get the pointer to the next polyline at one end of this */ PolyLine* next(End end) const; /* * write out coordinates of this and all attached polylines to a single vector */ PolyLine* writeOut(std::vector& outVec, End startEnd = TAIL) const; private: //methods PolyLine& joinTo_(End thisEnd, PolyLine& that, End end); }; //forward declaration template class PolyLinePolygonData; //forward declaration template class PolyLinePolygonWithHolesData; /* * ActiveTail represents an edge of an incomplete polygon. * * An ActiveTail object is the active tail end of a polyline object, which may (should) be the attached to * a chain of polyline objects through a pointer. The ActiveTail class provides an abstraction between * and algorithm that builds polygons and the PolyLine data representation of incomplete polygons that are * being built. It does this by providing an iterface to access the information about the last edge at the * tail of the PolyLine it is associated with. To a polygon constructing algorithm, an ActiveTail is a floating * edge of an incomplete polygon and has an orientation and coordinate value, as well as knowing which side of * 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 * 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, * or reassociate the hole to another incomplete polygon in the case that it become a hole itself. Alternately, * the active tail may add a filiment to stitch a hole into a shell and "fracture" the hole out of the interior * of a polygon. The active tail maintains a static output buffer to temporarily write polygon data to when * it outputs a figure so that outputting a polygon does not require the allocation of a temporary buffer. This * static buffer should be destroyed whenever the program determines that it won't need it anymore and would prefer to * release the memory it has allocated back to the system. */ template class ActiveTail { private: //data PolyLine* tailp_; ActiveTail *otherTailp_; std::list holesList_; //Sum of all the polylines which constitute the active tail (including holes)// size_t polyLineSize_; public: inline size_t getPolyLineSize(){ return polyLineSize_; } inline void setPolyLineSize(int delta){ polyLineSize_ = delta; } inline void addPolyLineSize(int delta){ polyLineSize_ += delta; } /* * iterator over coordinates of the figure */ class iterator { private: const PolyLine* pLine_; const PolyLine* pLineEnd_; unsigned int index_; unsigned int indexEnd_; End startEnd_; public: inline iterator() : pLine_(), pLineEnd_(), index_(), indexEnd_(), startEnd_() {} 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 startEnd_ = TAIL; if(!isHole ^ (orient == HORIZONTAL)) { //switch winding direction at = at->getOtherActiveTail(); } //now we have the right winding direction //if it is horizontal we need to skip the first element pLine_ = at->getTail(); if(at->getTail()->numSegments() > 0) index_ = at->getTail()->numSegments() - 1; if((at->getOrient() == HORIZONTAL) ^ (orient == HORIZONTAL)) { pLineEnd_ = at->getTail(); indexEnd_ = pLineEnd_->numSegments() - 1; if(index_ == 0) { pLine_ = at->getTail()->next(HEAD); if(at->getTail()->endConnectivity(HEAD) == TAIL) { index_ = pLine_->numSegments() -1; } else { startEnd_ = HEAD; index_ = 0; } } else { --index_; } } else { pLineEnd_ = at->getOtherActiveTail()->getTail(); if(pLineEnd_->numSegments() > 0) indexEnd_ = pLineEnd_->numSegments() - 1; } at->getTail()->joinTailToTail(*(at->getOtherActiveTail()->getTail())); } inline size_t size(void){ size_t count = 0; End dir = startEnd_; PolyLine const * currLine = pLine_; size_t ops = 0; while(currLine != pLineEnd_){ ops++; count += currLine->numSegments(); currLine = currLine->next(dir == HEAD ? TAIL : HEAD); dir = currLine->endConnectivity(dir == HEAD ? TAIL : HEAD); } count += pLineEnd_->numSegments(); return count; //no. of vertices } //use bitwise copy and assign provided by the compiler inline iterator& operator++() { if(pLine_ == pLineEnd_ && index_ == indexEnd_) { pLine_ = 0; index_ = 0; return *this; } if(startEnd_ == HEAD) { ++index_; if(index_ == pLine_->numSegments()) { End end = pLine_->endConnectivity(TAIL); pLine_ = pLine_->next(TAIL); if(end == TAIL) { startEnd_ = TAIL; index_ = pLine_->numSegments() -1; } else { index_ = 0; } } } else { if(index_ == 0) { End end = pLine_->endConnectivity(HEAD); pLine_ = pLine_->next(HEAD); if(end == TAIL) { index_ = pLine_->numSegments() -1; } else { startEnd_ = HEAD; index_ = 0; } } else { --index_; } } return *this; } inline const iterator operator++(int) { iterator tmp(*this); ++(*this); return tmp; } inline bool operator==(const iterator& that) const { return pLine_ == that.pLine_ && index_ == that.index_; } inline bool operator!=(const iterator& that) const { return pLine_ != that.pLine_ || index_ != that.index_; } inline Unit operator*() { return (*pLine_)[index_]; } }; /* * iterator over holes contained within the figure */ typedef typename std::list::const_iterator iteratorHoles; //default constructor ActiveTail(); //constructor ActiveTail(orientation_2d orient, Unit coord, Side solidToRight, ActiveTail* otherTailp); //constructor ActiveTail(PolyLine* active, ActiveTail* otherTailp); //copy constructor ActiveTail(const ActiveTail& that); //destructor ~ActiveTail(); //assignment operator ActiveTail& operator=(const ActiveTail& that); //equivalence operator bool operator==(const ActiveTail& b) const; /* * comparison operators, ActiveTail objects are sortable by geometry */ bool operator<(const ActiveTail& b) const; bool operator<=(const ActiveTail& b) const; bool operator>(const ActiveTail& b) const; bool operator>=(const ActiveTail& b) const; /* * get the pointer to the polyline that this is an active tail of */ PolyLine* getTail() const; /* * get the pointer to the polyline at the other end of the chain */ PolyLine* getOtherTail() const; /* * get the pointer to the activetail at the other end of the chain */ ActiveTail* getOtherActiveTail() const; /* * test if another active tail is the other end of the chain */ bool isOtherTail(const ActiveTail& b); /* * update this end of chain pointer to new polyline */ ActiveTail& updateTail(PolyLine* newTail); /* * associate a hole to this active tail by the specified policy */ ActiveTail* addHole(ActiveTail* hole, bool fractureHoles); /* * get the list of holes */ const std::list& getHoles() const; /* * copy holes from that to this */ void copyHoles(ActiveTail& that); /* * find out if solid to right */ bool solidToRight() const; /* * get coordinate (getCoord and getCoordinate are aliases for eachother) */ Unit getCoord() const; Unit getCoordinate() const; /* * get the tail orientation */ orientation_2d getOrient() const; /* * add a coordinate to the polygon at this active tail end, properly handle degenerate edges by removing redundant coordinate */ void pushCoordinate(Unit coord); /* * write the figure that this active tail points to out to the temp buffer */ void writeOutFigure(std::vector& outVec, bool isHole = false) const; /* * write the figure that this active tail points to out through iterators */ void writeOutFigureItrs(iterator& beginOut, iterator& endOut, bool isHole = false, orientation_2d orient = VERTICAL) const; iterator begin(bool isHole, orientation_2d orient) const; iterator end() const; /* * write the holes that this active tail points to out through iterators */ void writeOutFigureHoleItrs(iteratorHoles& beginOut, iteratorHoles& endOut) const; iteratorHoles beginHoles() const; iteratorHoles endHoles() const; /* * joins the two chains that the two active tail tails are ends of * checks for closure of figure and writes out polygons appropriately * returns a handle to a hole if one is closed */ static ActiveTail* joinChains(ActiveTail* at1, ActiveTail* at2, bool solid, std::vector& outBufferTmp); template static ActiveTail* joinChains(ActiveTail* at1, ActiveTail* at2, bool solid, typename std::vector& outBufferTmp); /* * deallocate temp buffer */ static void destroyOutBuffer(); /* * deallocate all polygon data this active tail points to (deep delete, call only from one of a pair of active tails) */ void destroyContents(); }; /* allocate a polyline object */ template PolyLine* createPolyLine(orientation_2d orient, Unit coord, Side side); /* deallocate a polyline object */ template void destroyPolyLine(PolyLine* pLine); /* allocate an activetail object */ template ActiveTail* createActiveTail(); /* deallocate an activetail object */ template void destroyActiveTail(ActiveTail* aTail); template class PolyLineHoleData { private: ActiveTail* p_; public: typedef Unit coordinate_type; typedef typename ActiveTail::iterator compact_iterator_type; typedef iterator_compact_to_points > iterator_type; inline PolyLineHoleData() : p_(0) {} inline PolyLineHoleData(ActiveTail* p) : p_(p) {} //use default copy and assign inline compact_iterator_type begin_compact() const { return p_->begin(true, (orientT ? VERTICAL : HORIZONTAL)); } 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 { return p_->getPolyLineSize(); } inline ActiveTail* yield() { return p_; } template inline PolyLineHoleData& set(iT inputBegin, iT inputEnd) { return *this; } template inline PolyLineHoleData& set_compact(iT inputBegin, iT inputEnd) { return *this; } }; template class PolyLinePolygonWithHolesData { private: ActiveTail* p_; public: typedef Unit coordinate_type; typedef typename ActiveTail::iterator compact_iterator_type; typedef iterator_compact_to_points > iterator_type; typedef PolyLineHoleData hole_type; typedef typename coordinate_traits::area_type area_type; class iteratorHoles { private: typename ActiveTail::iteratorHoles itr_; public: inline iteratorHoles() : itr_() {} inline iteratorHoles(typename ActiveTail::iteratorHoles itr) : itr_(itr) {} //use bitwise copy and assign provided by the compiler inline iteratorHoles& operator++() { ++itr_; return *this; } inline const iteratorHoles operator++(int) { iteratorHoles tmp(*this); ++(*this); return tmp; } inline bool operator==(const iteratorHoles& that) const { return itr_ == that.itr_; } inline bool operator!=(const iteratorHoles& that) const { return itr_ != that.itr_; } inline PolyLineHoleData operator*() { return PolyLineHoleData(*itr_);} }; typedef iteratorHoles iterator_holes_type; inline PolyLinePolygonWithHolesData() : p_(0) {} inline PolyLinePolygonWithHolesData(ActiveTail* p) : p_(p) {} //use default copy and assign inline compact_iterator_type begin_compact() const { return p_->begin(false, (orientT ? VERTICAL : HORIZONTAL)); } 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 iteratorHoles begin_holes() const { return iteratorHoles(p_->beginHoles()); } inline iteratorHoles end_holes() const { return iteratorHoles(p_->endHoles()); } inline ActiveTail* yield() { return p_; } //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 inline PolyLinePolygonWithHolesData& set(iT inputBegin, iT inputEnd) { return *this; } template 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 inline PolyLinePolygonWithHolesData& set_holes(iT inputBegin, iT inputEnd) { return *this; } }; template struct PolyLineType { }; template struct PolyLineType { typedef PolyLinePolygonWithHolesData type; }; template struct PolyLineType { typedef PolyLinePolygonWithHolesData type; }; template struct PolyLineType { typedef PolyLinePolygonWithHolesData type; }; template struct PolyLineType { typedef PolyLineHoleData type; }; template struct PolyLineType { typedef PolyLineHoleData type; }; template struct PolyLineType { typedef PolyLineHoleData type; }; template class ScanLineToPolygonItrs { private: std::map*> tailMap_; typedef typename PolyLineType::type PolyLinePolygonData; std::vector outputPolygons_; bool fractureHoles_; public: typedef typename std::vector::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 >& leftEdges, std::vector >& rightEdges, size_t vertexThreshold=(std::numeric_limits::max)() ); /********************************************************************** *methods implementing new polygon formation code * **********************************************************************/ void updatePartialSimplePolygonsWithRightEdges(Unit currentX, const std::vector >& leftEdges, size_t threshold); void updatePartialSimplePolygonsWithLeftEdges(Unit currentX, const std::vector >& leftEdges, size_t threshold); void closePartialSimplePolygon(Unit, ActiveTail*, ActiveTail*); void maintainPartialSimplePolygonInvariant(iterator& ,iterator& ,Unit, const std::vector >&, const std::vector >&, size_t vertexThreshold=(std::numeric_limits::max)()); void insertNewLeftEdgeIntoTailMap(Unit, Unit, Unit, typename std::map*>::iterator &); /**********************************************************************/ inline size_t getTailMapSize(){ typename std::map* >::const_iterator itr; size_t tsize = 0; for(itr=tailMap_.begin(); itr!=tailMap_.end(); ++itr){ tsize += (itr->second)->getPolyLineSize(); } return tsize; } /*print the active tails in this map:*/ inline void print(){ typename std::map* >::const_iterator itr; printf("=========TailMap[%lu]=========\n", tailMap_.size()); for(itr=tailMap_.begin(); itr!=tailMap_.end(); ++itr){ std::cout<< "[" << itr->first << "] : " << std::endl; //print active tail// ActiveTail const *t = (itr->second); PolyLine const *pBegin = t->getTail(); PolyLine const *pEnd = t->getOtherActiveTail()->getTail(); std::string sorient = pBegin->solidToRight() ? "RIGHT" : "LEFT"; std::cout<< " ActiveTail.tailp_ (solid= " << sorient ; End dir = TAIL; while(pBegin!=pEnd){ std::cout << pBegin << "={ "; for(size_t i=0; inumSegments(); i++){ point_data u = pBegin->getPoint(i); std::cout << "(" << u.x() << "," << u.y() << ") "; } std::cout << "} "; pBegin = pBegin->next(dir == HEAD ? TAIL : HEAD); dir = pBegin->endConnectivity(dir == HEAD ? TAIL : HEAD); } if(pEnd){ std::cout << pEnd << "={ "; for(size_t i=0; inumSegments(); i++){ point_data u = pEnd->getPoint(i); std::cout << "(" << u.x() << "," << u.y() << ") "; } std::cout << "} "; } std::cout << " end= " << pEnd << std::endl; } } private: void clearOutput_(); }; /* * ScanLine does all the work of stitching together polygons from incoming vertical edges */ // template // class ScanLineToPolygons { // private: // ScanLineToPolygonItrs scanline_; // public: // 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& outBufferTmp, Unit currentX, std::vector >& leftEdges, // std::vector >& rightEdges) { // typename ScanLineToPolygonItrs::iterator itr, endItr; // scanline_.processEdges(itr, endItr, currentX, leftEdges, rightEdges); // //copy data into outBufferTmp // while(itr != endItr) { // typename PolyLinePolygonData::iterator pditr; // outBufferTmp.push_back(0); // unsigned int sizeIndex = outBufferTmp.size() - 1; // int count = 0; // for(pditr = (*itr).begin(); pditr != (*itr).end(); ++pditr) { // outBufferTmp.push_back(*pditr); // ++count; // } // outBufferTmp[sizeIndex] = count; // typename PolyLinePolygonData::iteratorHoles pdHoleItr; // for(pdHoleItr = (*itr).beginHoles(); pdHoleItr != (*itr).endHoles(); ++pdHoleItr) { // outBufferTmp.push_back(0); // unsigned int sizeIndex2 = outBufferTmp.size() - 1; // int count2 = 0; // for(pditr = (*pdHoleItr).begin(); pditr != (*pdHoleItr).end(); ++pditr) { // outBufferTmp.push_back(*pditr); // ++count2; // } // outBufferTmp[sizeIndex2] = -count; // } // ++itr; // } // } // }; const int VERTICAL_HEAD = 1, HEAD_TO_TAIL = 2, TAIL_TO_TAIL = 4, SOLID_TO_RIGHT = 8; //EVERY FUNCTION in this DEF file should be explicitly defined as inline //microsoft compiler improperly warns whenever you cast an integer to bool //call this function on an integer to convert it to bool without a warning template inline bool to_bool(const T& val) { return val != 0; } //default constructor (for preallocation) template inline PolyLine::PolyLine() : ptdata_() ,headp_(0), tailp_(0), state_(-1) {} //constructor template inline PolyLine::PolyLine(orientation_2d orient, Unit coord, Side side) : ptdata_(1, coord), headp_(0), tailp_(0), state_(orient.to_int() + (side << 3)){} //copy constructor template inline PolyLine::PolyLine(const PolyLine& pline) : ptdata_(pline.ptdata_), headp_(pline.headp_), tailp_(pline.tailp_), state_(pline.state_) {} //destructor template inline PolyLine::~PolyLine() { //clear out data just in case it is read later headp_ = tailp_ = 0; state_ = 0; } template inline PolyLine& PolyLine::operator=(const PolyLine& that) { if(!(this == &that)) { headp_ = that.headp_; tailp_ = that.tailp_; ptdata_ = that.ptdata_; state_ = that.state_; } return *this; } template inline bool PolyLine::operator==(const PolyLine& b) const { return this == &b || (state_ == b.state_ && headp_ == b.headp_ && tailp_ == b.tailp_); } //valid PolyLine template inline bool PolyLine::isValid() const { return state_ > -1; } //first coordinate is an X value //first segment is vertical template inline bool PolyLine::verticalHead() const { return state_ & VERTICAL_HEAD; } //retrun true is PolyLine has odd number of coordiantes template inline bool PolyLine::oddLength() const { return to_bool((ptdata_.size()-1) % 2); } //last coordiante is an X value //last segment is vertical template inline bool PolyLine::verticalTail() const { return to_bool(verticalHead() ^ oddLength()); } template inline orientation_2d PolyLine::tailOrient() const { return (verticalTail() ? VERTICAL : HORIZONTAL); } template inline orientation_2d PolyLine::headOrient() const { return (verticalHead() ? VERTICAL : HORIZONTAL); } template inline End PolyLine::endConnectivity(End end) const { //Tail should be defined as true if(end) { return tailToTail(); } return headToTail(); } template inline bool PolyLine::headToTail() const { return to_bool(state_ & HEAD_TO_TAIL); } template inline bool PolyLine::headToHead() const { return to_bool(!headToTail()); } template inline bool PolyLine::tailToHead() const { return to_bool(!tailToTail()); } template inline bool PolyLine::tailToTail() const { return to_bool(state_ & TAIL_TO_TAIL); } template inline Side PolyLine::solidSide() const { return solidToRight(); } template inline bool PolyLine::solidToRight() const { return to_bool(state_ & SOLID_TO_RIGHT) != 0; } template inline bool PolyLine::active() const { return !to_bool(tailp_); } template inline PolyLine& PolyLine::pushCoordinate(Unit coord) { ptdata_.push_back(coord); return *this; } template inline PolyLine& PolyLine::popCoordinate() { ptdata_.pop_back(); return *this; } template inline PolyLine& PolyLine::pushPoint(const point_data& point) { if(numSegments()){ point_data endPt = getEndPoint(); //vertical is true, horizontal is false if((tailOrient().to_int() ? point.get(VERTICAL) == endPt.get(VERTICAL) : point.get(HORIZONTAL) == endPt.get(HORIZONTAL))) { //we were pushing a colinear segment return popCoordinate(); } } return pushCoordinate(tailOrient().to_int() ? point.get(VERTICAL) : point.get(HORIZONTAL)); } template inline PolyLine& PolyLine::extendTail(Unit delta) { ptdata_.back() += delta; return *this; } //private member function that creates a link from this PolyLine to that template inline PolyLine& PolyLine::joinTo_(End thisEnd, PolyLine& that, End end) { if(thisEnd){ tailp_ = &that; state_ &= ~TAIL_TO_TAIL; //clear any previous state_ of bit (for safety) state_ |= (end << 2); //place bit into mask } else { headp_ = &that; state_ &= ~HEAD_TO_TAIL; //clear any previous state_ of bit (for safety) state_ |= (end << 1); //place bit into mask } return *this; } //join two PolyLines (both ways of the association) template inline PolyLine& PolyLine::joinTo(End thisEnd, PolyLine& that, End end) { joinTo_(thisEnd, that, end); that.joinTo_(end, *this, thisEnd); return *this; } //convenience functions for joining PolyLines template inline PolyLine& PolyLine::joinToTail(PolyLine& that, End end) { return joinTo(TAIL, that, end); } template inline PolyLine& PolyLine::joinToHead(PolyLine& that, End end) { return joinTo(HEAD, that, end); } template inline PolyLine& PolyLine::joinHeadToHead(PolyLine& that) { return joinToHead(that, HEAD); } template inline PolyLine& PolyLine::joinHeadToTail(PolyLine& that) { return joinToHead(that, TAIL); } template inline PolyLine& PolyLine::joinTailToHead(PolyLine& that) { return joinToTail(that, HEAD); } template inline PolyLine& PolyLine::joinTailToTail(PolyLine& that) { return joinToTail(that, TAIL); } template inline PolyLine& PolyLine::disconnectTails() { next(TAIL)->state_ &= !TAIL_TO_TAIL; next(TAIL)->tailp_ = 0; state_ &= !TAIL_TO_TAIL; tailp_ = 0; return *this; } template inline Unit PolyLine::getEndCoord(End end) const { if(end) return ptdata_.back(); return ptdata_.front(); } template inline orientation_2d PolyLine::segmentOrient(unsigned int index) const { return (to_bool((unsigned int)verticalHead() ^ (index % 2)) ? VERTICAL : HORIZONTAL); } template inline point_data PolyLine::getPoint(unsigned int index) const { //assert(isValid() && headp_->isValid()) ("PolyLine: headp_ must be valid"); point_data pt; pt.set(HORIZONTAL, ptdata_[index]); pt.set(VERTICAL, ptdata_[index]); Unit prevCoord; if(index == 0) { prevCoord = headp_->getEndCoord(headToTail()); } else { prevCoord = ptdata_[index-1]; } pt.set(segmentOrient(index), prevCoord); return pt; } template inline point_data PolyLine::getEndPoint(End end) const { return getPoint((end ? numSegments() - 1 : (unsigned int)0)); } template inline Unit PolyLine::operator[] (unsigned int index) const { //assert(ptdata_.size() > index) ("PolyLine: out of bounds index"); return ptdata_[index]; } template inline unsigned int PolyLine::numSegments() const { return ptdata_.size(); } template inline PolyLine* PolyLine::next(End end) const { return (end ? tailp_ : headp_); } template inline ActiveTail::ActiveTail() : tailp_(0), otherTailp_(0), holesList_(), polyLineSize_(0) {} template inline ActiveTail::ActiveTail(orientation_2d orient, Unit coord, Side solidToRight, ActiveTail* otherTailp) : tailp_(0), otherTailp_(0), holesList_(), polyLineSize_(0) { tailp_ = createPolyLine(orient, coord, solidToRight); otherTailp_ = otherTailp; polyLineSize_ = tailp_->numSegments(); } template inline ActiveTail::ActiveTail(PolyLine* active, ActiveTail* otherTailp) : tailp_(active), otherTailp_(otherTailp), holesList_(), polyLineSize_(0) {} //copy constructor template inline ActiveTail::ActiveTail(const ActiveTail& that) : tailp_(that.tailp_), otherTailp_(that.otherTailp_), holesList_(), polyLineSize_(that.polyLineSize_) {} //destructor template inline ActiveTail::~ActiveTail() { //clear them in case the memory is read later tailp_ = 0; otherTailp_ = 0; } template inline ActiveTail& ActiveTail::operator=(const ActiveTail& that) { //self assignment is safe in this case tailp_ = that.tailp_; otherTailp_ = that.otherTailp_; polyLineSize_ = that.polyLineSize_; return *this; } template inline bool ActiveTail::operator==(const ActiveTail& b) const { return tailp_ == b.tailp_ && otherTailp_ == b.otherTailp_; } template inline bool ActiveTail::operator<(const ActiveTail& b) const { return tailp_->getEndPoint().get(VERTICAL) < b.tailp_->getEndPoint().get(VERTICAL); } template inline bool ActiveTail::operator<=(const ActiveTail& b) const { return !(*this > b); } template inline bool ActiveTail::operator>(const ActiveTail& b) const { return b < (*this); } template inline bool ActiveTail::operator>=(const ActiveTail& b) const { return !(*this < b); } template inline PolyLine* ActiveTail::getTail() const { return tailp_; } template inline PolyLine* ActiveTail::getOtherTail() const { return otherTailp_->tailp_; } template inline ActiveTail* ActiveTail::getOtherActiveTail() const { return otherTailp_; } template inline bool ActiveTail::isOtherTail(const ActiveTail& b) { // assert( (tailp_ == b.getOtherTail() && getOtherTail() == b.tailp_) || // (tailp_ != b.getOtherTail() && getOtherTail() != b.tailp_)) // ("ActiveTail: Active tails out of sync"); return otherTailp_ == &b; } template inline ActiveTail& ActiveTail::updateTail(PolyLine* newTail) { //subtract the old size and add new size// int delta = newTail->numSegments() - tailp_->numSegments(); addPolyLineSize(delta); otherTailp_->addPolyLineSize(delta); tailp_ = newTail; return *this; } template inline ActiveTail* ActiveTail::addHole(ActiveTail* hole, bool fractureHoles) { if(!fractureHoles){ holesList_.push_back(hole); copyHoles(*hole); copyHoles(*(hole->getOtherActiveTail())); return this; } ActiveTail* h, *v; ActiveTail* other = hole->getOtherActiveTail(); if(other->getOrient() == VERTICAL) { //assert that hole.getOrient() == HORIZONTAL //this case should never happen h = hole; v = other; } else { //assert that hole.getOrient() == VERTICAL h = other; v = hole; } h->pushCoordinate(v->getCoordinate()); //assert that h->getOrient() == VERTICAL //v->pushCoordinate(getCoordinate()); //assert that v->getOrient() == VERTICAL //I can't close a figure by adding a hole, so pass zero for xMin and yMin std::vector tmpVec; ActiveTail::joinChains(this, h, false, tmpVec); return v; } template inline const std::list*>& ActiveTail::getHoles() const { return holesList_; } template inline void ActiveTail::copyHoles(ActiveTail& that) { holesList_.splice(holesList_.end(), that.holesList_); //splice the two lists together } template inline bool ActiveTail::solidToRight() const { return getTail()->solidToRight(); } template inline Unit ActiveTail::getCoord() const { return getTail()->getEndCoord(); } template inline Unit ActiveTail::getCoordinate() const { return getCoord(); } template inline orientation_2d ActiveTail::getOrient() const { return getTail()->tailOrient(); } template inline void ActiveTail::pushCoordinate(Unit coord) { //appropriately handle any co-linear polyline segments by calling push point internally point_data p; p.set(HORIZONTAL, coord); p.set(VERTICAL, coord); //if we are vertical assign the last coordinate (an X) to p.x, else to p.y p.set(getOrient().get_perpendicular(), getCoordinate()); int oldSegments = tailp_->numSegments(); tailp_->pushPoint(p); int delta = tailp_->numSegments() - oldSegments; addPolyLineSize(delta); otherTailp_->addPolyLineSize(delta); } //global utility functions template inline PolyLine* createPolyLine(orientation_2d orient, Unit coord, Side side) { return new PolyLine(orient, coord, side); } template inline void destroyPolyLine(PolyLine* pLine) { delete pLine; } template inline ActiveTail* createActiveTail() { //consider replacing system allocator with ActiveTail memory pool return new ActiveTail(); } template inline void destroyActiveTail(ActiveTail* aTail) { delete aTail; } //no recursion, to prevent max recursion depth errors template inline void ActiveTail::destroyContents() { tailp_->disconnectTails(); PolyLine* nextPolyLinep = tailp_->next(HEAD); End end = tailp_->endConnectivity(HEAD); destroyPolyLine(tailp_); while(nextPolyLinep) { End nextEnd = nextPolyLinep->endConnectivity(!end); //get the direction of next polyLine PolyLine* nextNextPolyLinep = nextPolyLinep->next(!end); //get the next polyline destroyPolyLine(nextPolyLinep); //destroy the current polyline end = nextEnd; nextPolyLinep = nextNextPolyLinep; } } template inline typename ActiveTail::iterator ActiveTail::begin(bool isHole, orientation_2d orient) const { return iterator(this, isHole, orient); } template inline typename ActiveTail::iterator ActiveTail::end() const { return iterator(); } template inline typename ActiveTail::iteratorHoles ActiveTail::beginHoles() const { return holesList_.begin(); } template inline typename ActiveTail::iteratorHoles ActiveTail::endHoles() const { return holesList_.end(); } template inline void ActiveTail::writeOutFigureItrs(iterator& beginOut, iterator& endOut, bool isHole, orientation_2d orient) const { beginOut = begin(isHole, orient); endOut = end(); } template inline void ActiveTail::writeOutFigureHoleItrs(iteratorHoles& beginOut, iteratorHoles& endOut) const { beginOut = beginHoles(); endOut = endHoles(); } template inline void ActiveTail::writeOutFigure(std::vector& outVec, bool isHole) const { //we start writing out the polyLine that this active tail points to at its tail std::size_t size = outVec.size(); outVec.push_back(0); //place holder for size PolyLine* nextPolyLinep = 0; if(!isHole){ nextPolyLinep = otherTailp_->tailp_->writeOut(outVec); } else { nextPolyLinep = tailp_->writeOut(outVec); } Unit firsty = outVec[size + 1]; if((getOrient() == HORIZONTAL) ^ !isHole) { //our first coordinate is a y value, so we need to rotate it to the end typename std::vector::iterator tmpItr = outVec.begin(); 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); 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 } //the vector contains the coordinates of the linked list of PolyLines in the correct order //first element is supposed to be the size outVec[size] = outVec.size() - 1 - size; //number of coordinates in vector //assert outVec[size] % 2 == 0 //it should be even //make the size negative for holes outVec[size] *= (isHole ? -1 : 1); } //no recursion to prevent max recursion depth errors template inline PolyLine* PolyLine::writeOut(std::vector& outVec, End startEnd) const { if(startEnd == HEAD){ //forward order outVec.insert(outVec.end(), ptdata_.begin(), ptdata_.end()); return tailp_; }else{ //reverse order //do not reserve because we expect outVec to be large enough already for(int i = ptdata_.size() - 1; i >= 0; --i){ outVec.push_back(ptdata_[i]); } //NT didn't know about this version of the API.... //outVec.insert(outVec.end(), ptdata_.rbegin(), ptdata_.rend()); return headp_; } } //solid indicates if it was joined by a solit or a space template inline ActiveTail* ActiveTail::joinChains(ActiveTail* at1, ActiveTail* at2, bool solid, std::vector& outBufferTmp) { //checks to see if we closed a figure if(at1->isOtherTail(*at2)){ //value of solid tells us if we closed solid or hole //and output the solid or handle the hole appropriately //if the hole needs to fracture across horizontal partition boundary we need to notify //the calling context to do so if(solid) { //the chains are being joined because there is solid to the right //this means that if the figure is closed at this point it must be a hole //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 { //assert pG != 0 //the figure that was closed is a shell at1->writeOutFigure(outBufferTmp); //process holes of the polygon at1->copyHoles(*at2); //there should not be holes on at2, but if there are, copy them over const std::list*>& holes = at1->getHoles(); for(typename std::list*>::const_iterator litr = holes.begin(); litr != holes.end(); ++litr) { (*litr)->writeOutFigure(outBufferTmp, true); //delete the hole (*litr)->destroyContents(); destroyActiveTail((*litr)->getOtherActiveTail()); destroyActiveTail((*litr)); } //delete the polygon at1->destroyContents(); //at2 contents are the same as at1, so it should not destroy them destroyActiveTail(at1); destroyActiveTail(at2); } return 0; } //join the two partial polygons into one large partial polygon at1->getTail()->joinTailToTail(*(at2->getTail())); *(at1->getOtherActiveTail()) = ActiveTail(at1->getOtherTail(), at2->getOtherActiveTail()); *(at2->getOtherActiveTail()) = ActiveTail(at2->getOtherTail(), at1->getOtherActiveTail()); int accumulate = at2->getPolyLineSize() + at1->getPolyLineSize(); (at1->getOtherActiveTail())->setPolyLineSize(accumulate); (at2->getOtherActiveTail())->setPolyLineSize(accumulate); at1->getOtherActiveTail()->copyHoles(*at1); at1->getOtherActiveTail()->copyHoles(*at2); destroyActiveTail(at1); destroyActiveTail(at2); return 0; } //solid indicates if it was joined by a solit or a space template template inline ActiveTail* ActiveTail::joinChains(ActiveTail* at1, ActiveTail* at2, bool solid, std::vector& outBufferTmp) { //checks to see if we closed a figure if(at1->isOtherTail(*at2)){ //value of solid tells us if we closed solid or hole //and output the solid or handle the hole appropriately //if the hole needs to fracture across horizontal partition boundary we need to notify //the calling context to do so if(solid) { //the chains are being joined because there is solid to the right //this means that if the figure is closed at this point it must be a hole //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 { //assert pG != 0 //the figure that was closed is a shell outBufferTmp.push_back(at1); at1->copyHoles(*at2); //there should not be holes on at2, but if there are, copy them over } return 0; } //join the two partial polygons into one large partial polygon at1->getTail()->joinTailToTail(*(at2->getTail())); *(at1->getOtherActiveTail()) = ActiveTail(at1->getOtherTail(), at2->getOtherActiveTail()); *(at2->getOtherActiveTail()) = ActiveTail(at2->getOtherTail(), at1->getOtherActiveTail()); int accumulate = at2->getPolyLineSize() + at1->getPolyLineSize(); (at1->getOtherActiveTail())->setPolyLineSize(accumulate); (at2->getOtherActiveTail())->setPolyLineSize(accumulate); at1->getOtherActiveTail()->copyHoles(*at1); at1->getOtherActiveTail()->copyHoles(*at2); destroyActiveTail(at1); destroyActiveTail(at2); return 0; } template inline typename std::map::iterator findAtNext(std::map& theMap, typename std::map::iterator pos, const TKey& key) { if(pos == theMap.end()) return theMap.find(key); //if they match the mapItr is pointing to the correct position if(pos->first < key) { return theMap.find(key); } 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 // with add hole template inline std::pair*, ActiveTail*> createActiveTailsAsPair(Unit x, Unit y, bool solid, ActiveTail* phole, bool fractureHoles) { ActiveTail* at1 = 0; ActiveTail* at2 = 0; if(!phole || !fractureHoles){ at1 = createActiveTail(); at2 = createActiveTail(); (*at1) = ActiveTail(VERTICAL, x, solid, at2); (*at2) = ActiveTail(HORIZONTAL, y, !solid, at1); //provide a function through activeTail class to provide this at1->getTail()->joinHeadToHead(*(at2->getTail())); at1->addPolyLineSize(1); at2->addPolyLineSize(1); if(phole) at1->addHole(phole, fractureHoles); //assert fractureHoles == false return std::pair*, ActiveTail*>(at1, at2); } //assert phole is not null //assert fractureHoles is true if(phole->getOrient() == VERTICAL) { at2 = phole; } else { at2 = phole->getOtherActiveTail(); //should never be executed since orientation is expected to be vertical } //assert solid == false, we should be creating a corner with solid below and to the left if there was a hole at1 = at2->getOtherActiveTail(); //assert at1 is horizontal at1->pushCoordinate(x); //assert at2 is vertical at2->pushCoordinate(y); return std::pair*, ActiveTail*>(at1, at2); } /* * | * | * = * |######## * |######## (add a new ActiveTail in the tailMap_). * |######## * |######## * |######## * = * | * | * * NOTE: Call this only if you are sure that the $ledege$ is not in the tailMap_ */ template inline void ScanLineToPolygonItrs:: insertNewLeftEdgeIntoTailMap(Unit currentX, Unit yBegin, Unit yEnd, typename std::map *>::iterator &hint){ ActiveTail *currentTail = NULL; std::pair*, ActiveTail*> tailPair = createActiveTailsAsPair(currentX, yBegin, true, currentTail, fractureHoles_); currentTail = tailPair.first; if(!tailMap_.empty()){ ++hint; } hint = tailMap_.insert(hint, std::make_pair(yBegin, tailPair.second)); currentTail->pushCoordinate(yEnd); ++hint; hint = tailMap_.insert(hint, std::make_pair(yEnd, currentTail)); } template inline void ScanLineToPolygonItrs:: closePartialSimplePolygon(Unit currentX, ActiveTail*pfig, ActiveTail*ppfig){ pfig->pushCoordinate(currentX); ActiveTail::joinChains(pfig, ppfig, false, outputPolygons_); } /* * If the invariant is maintained correctly then left edges can do the * following. * * =### * ####### * ####### * ####### * ####### * =### * |### (input left edge) * |### * =### * ####### * ####### * =### */ template inline void ScanLineToPolygonItrs:: updatePartialSimplePolygonsWithLeftEdges(Unit currentX, const std::vector > &leftEdges, size_t vertexThreshold){ typename std::map* >::iterator succ, succ1; typename std::map* >::iterator pred, pred1, hint; Unit begin, end; ActiveTail *pfig, *ppfig; std::pair*, ActiveTail*> tailPair; size_t pfig_size = 0; 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); if(succ != tailMap_.end() && pred != tailMap_.end()){ //CASE-1// //join the corresponding active tails// pfig = succ->second; ppfig = pred->second; pfig_size = pfig->getPolyLineSize() + ppfig->getPolyLineSize(); if(pfig_size >= vertexThreshold){ size_t bsize = pfig->getPolyLineSize(); size_t usize = ppfig->getPolyLineSize(); if(usize+2 < vertexThreshold){ //cut-off the lower piece (succ1, succ) join (succ1, pred)// succ1 = succ; --succ1; assert((succ1 != tailMap_.end()) && ((succ->second)->getOtherActiveTail() == succ1->second)); closePartialSimplePolygon(currentX, succ1->second, succ->second); tailPair = createActiveTailsAsPair(currentX, succ1->first, true, NULL, fractureHoles_); //just update the succ1 with new ActiveTail*// succ1->second = tailPair.second; ActiveTail::joinChains(tailPair.first, pred->second, true, outputPolygons_); }else if(bsize+2 < vertexThreshold){ //cut-off the upper piece () join ()// pred1 = pred; ++pred1; assert(pred1 != tailMap_.end() && ((pred1->second)->getOtherActiveTail() == pred->second)); closePartialSimplePolygon(currentX, pred->second, pred1->second); //just update the pred1 with ActiveTail* = pfig// pred1->second = pfig; pfig->pushCoordinate(currentX); pfig->pushCoordinate(pred1->first); }else{ //cut both and create an left edge between (pred->first, succ1)// succ1 = succ; --succ1; pred1 = pred; ++pred1; assert(pred1 != tailMap_.end() && succ1 != tailMap_.end()); assert((pred1->second)->getOtherActiveTail() == pred->second); assert((succ1->second)->getOtherActiveTail() == succ->second); closePartialSimplePolygon(currentX, succ1->second, succ->second); closePartialSimplePolygon(currentX, pred->second, pred1->second); tailPair = createActiveTailsAsPair(currentX, succ1->first, true, NULL, fractureHoles_); succ1->second = tailPair.second; pred1->second = tailPair.first; (tailPair.first)->pushCoordinate(pred1->first); } }else{ //just join them with closing// pfig->pushCoordinate(currentX); ActiveTail::joinChains(pfig, ppfig, true, outputPolygons_); } 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(currentX, begin, true, NULL, fractureHoles_); hint = pred; ++hint; hint = tailMap_.insert(hint, std::make_pair(begin, tailPair.second)); pfig = pred->second; pfig_size = pfig->getPolyLineSize() + 2; if(pfig_size >= vertexThreshold){ //cut-off piece from [pred, pred1] , add [begin, pred1]// pred1 = pred; ++pred1; assert((pred1 != tailMap_.end()) && ((pred1->second)->getOtherActiveTail() == pred->second)); closePartialSimplePolygon(currentX, pred->second, pred1->second); //update: we need left edge between (begin, pred1->first)// pred1->second = tailPair.first; (tailPair.first)->pushCoordinate(pred1->first); }else{ //just join// ActiveTail::joinChains(tailPair.first, pfig, true, outputPolygons_); } tailMap_.erase(pred); }else if(succ != tailMap_.end() && pred == tailMap_.end()){ //CASE-3// //pred is missing in the map, first insert it into the map// hint = succ; ++hint; hint = tailMap_.insert(hint, std::make_pair(end, (ActiveTail *) NULL)); pfig = succ->second; pfig_size = pfig->getPolyLineSize() + 2; if(pfig_size >= vertexThreshold){ //this figure needs cutting here// succ1 = succ; --succ1; assert((succ1 != tailMap_.end()) && (succ1->second == pfig->getOtherActiveTail())); ppfig = succ1->second; closePartialSimplePolygon(currentX, ppfig, pfig); //update: we need a left edge between (succ1->first, end)// tailPair = createActiveTailsAsPair(currentX, succ1->first, true, NULL, fractureHoles_); succ1->second = tailPair.second; hint->second = tailPair.first; (tailPair.first)->pushCoordinate(end); }else{ //no cutting needed// hint->second = pfig; pfig->pushCoordinate(currentX); pfig->pushCoordinate(end); } tailMap_.erase(succ); }else{ //insert both pred and succ// insertNewLeftEdgeIntoTailMap(currentX, begin, end, hint); } } } template inline void ScanLineToPolygonItrs:: updatePartialSimplePolygonsWithRightEdges(Unit currentX, const std::vector > &rightEdges, size_t vertexThreshold) { typename std::map