| /* |
| 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). |
| */ |
| #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 <typename Unit> |
| 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 |
| */ |
| 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<Unit>& 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<Unit> getPoint(unsigned int index) const; |
| |
| /* |
| * get the point on one end of the polyline, by default the tail |
| */ |
| point_data<Unit> 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<Unit>& outVec, End startEnd = TAIL) const; |
| |
| private: |
| //methods |
| PolyLine& joinTo_(End thisEnd, PolyLine& that, End end); |
| }; |
| |
| //forward declaration |
| template<bool orientT, typename Unit> |
| class PolyLinePolygonData; |
| |
| //forward declaration |
| template<bool orientT, typename Unit> |
| 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 <typename Unit> |
| class ActiveTail { |
| private: |
| //data |
| PolyLine<Unit>* tailp_; |
| ActiveTail *otherTailp_; |
| std::list<ActiveTail*> holesList_; |
| public: |
| |
| /* |
| * iterator over coordinates of the figure |
| */ |
| class iterator { |
| private: |
| const PolyLine<Unit>* pLine_; |
| const PolyLine<Unit>* 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(); |
| 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(); |
| indexEnd_ = pLineEnd_->numSegments() - 1; |
| } |
| at->getTail()->joinTailToTail(*(at->getOtherActiveTail()->getTail())); |
| } |
| //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<ActiveTail*>::const_iterator iteratorHoles; |
| |
| //default constructor |
| ActiveTail(); |
| |
| //constructor |
| ActiveTail(orientation_2d orient, Unit coord, Side solidToRight, ActiveTail* otherTailp); |
| |
| //constructor |
| ActiveTail(PolyLine<Unit>* 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<Unit>* getTail() const; |
| |
| /* |
| * get the pointer to the polyline at the other end of the chain |
| */ |
| PolyLine<Unit>* 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<Unit>* 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<ActiveTail*>& 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<Unit>& 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<Unit>& outBufferTmp); |
| template <typename PolygonT> |
| static ActiveTail* joinChains(ActiveTail* at1, ActiveTail* at2, bool solid, typename std::vector<PolygonT>& 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 <typename Unit> |
| PolyLine<Unit>* createPolyLine(orientation_2d orient, Unit coord, Side side); |
| |
| /* deallocate a polyline object */ |
| template <typename Unit> |
| void destroyPolyLine(PolyLine<Unit>* pLine); |
| |
| /* allocate an activetail object */ |
| template <typename Unit> |
| ActiveTail<Unit>* createActiveTail(); |
| |
| /* deallocate an activetail object */ |
| template <typename Unit> |
| void destroyActiveTail(ActiveTail<Unit>* aTail); |
| |
| template<bool orientT, typename Unit> |
| class PolyLineHoleData { |
| private: |
| ActiveTail<Unit>* p_; |
| public: |
| typedef Unit coordinate_type; |
| typedef typename ActiveTail<Unit>::iterator compact_iterator_type; |
| typedef iterator_compact_to_points<compact_iterator_type, point_data<coordinate_type> > iterator_type; |
| inline PolyLineHoleData() : p_(0) {} |
| inline PolyLineHoleData(ActiveTail<Unit>* 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 0; } |
| 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> |
| class PolyLinePolygonWithHolesData { |
| private: |
| ActiveTail<Unit>* p_; |
| public: |
| typedef Unit coordinate_type; |
| typedef typename ActiveTail<Unit>::iterator compact_iterator_type; |
| typedef iterator_compact_to_points<compact_iterator_type, point_data<coordinate_type> > iterator_type; |
| typedef PolyLineHoleData<orientT, Unit> hole_type; |
| typedef typename coordinate_traits<Unit>::area_type area_type; |
| class iteratorHoles { |
| private: |
| typename ActiveTail<Unit>::iteratorHoles itr_; |
| public: |
| inline iteratorHoles() : itr_() {} |
| inline iteratorHoles(typename ActiveTail<Unit>::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<orientT, Unit> operator*() { return PolyLineHoleData<orientT, Unit>(*itr_);} |
| }; |
| typedef iteratorHoles iterator_holes_type; |
| |
| inline PolyLinePolygonWithHolesData() : p_(0) {} |
| inline PolyLinePolygonWithHolesData(ActiveTail<Unit>* 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<Unit>* 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<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; |
| } |
| }; |
| |
| |
| template <bool orientT, typename Unit, typename polygon_concept_type> |
| struct PolyLineType { }; |
| template <bool orientT, typename Unit> |
| struct PolyLineType<orientT, Unit, polygon_90_with_holes_concept> { typedef PolyLinePolygonWithHolesData<orientT, Unit> type; }; |
| template <bool orientT, typename Unit> |
| struct PolyLineType<orientT, Unit, polygon_45_with_holes_concept> { typedef PolyLinePolygonWithHolesData<orientT, Unit> type; }; |
| template <bool orientT, typename Unit> |
| struct PolyLineType<orientT, Unit, polygon_with_holes_concept> { typedef PolyLinePolygonWithHolesData<orientT, Unit> type; }; |
| template <bool orientT, typename Unit> |
| struct PolyLineType<orientT, Unit, polygon_90_concept> { typedef PolyLineHoleData<orientT, Unit> type; }; |
| template <bool orientT, typename Unit> |
| struct PolyLineType<orientT, Unit, polygon_45_concept> { typedef PolyLineHoleData<orientT, Unit> type; }; |
| template <bool orientT, typename Unit> |
| struct PolyLineType<orientT, Unit, polygon_concept> { typedef PolyLineHoleData<orientT, Unit> type; }; |
| |
| template <bool orientT, typename Unit, typename polygon_concept_type> |
| class ScanLineToPolygonItrs { |
| private: |
| std::map<Unit, ActiveTail<Unit>*> tailMap_; |
| typedef typename PolyLineType<orientT, Unit, polygon_concept_type>::type PolyLinePolygonData; |
| std::vector<PolyLinePolygonData> outputPolygons_; |
| bool fractureHoles_; |
| public: |
| 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, |
| std::vector<interval_data<Unit> >& rightEdges); |
| |
| private: |
| void clearOutput_(); |
| }; |
| |
| /* |
| * ScanLine does all the work of stitching together polygons from incoming vertical edges |
| */ |
| // template <typename Unit, typename polygon_concept_type> |
| // class ScanLineToPolygons { |
| // private: |
| // ScanLineToPolygonItrs<true, Unit> 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<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); |
| // //copy data into outBufferTmp |
| // while(itr != endItr) { |
| // typename PolyLinePolygonData<true, Unit>::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<true, Unit>::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 <class T> |
| inline bool to_bool(const T& val) { return val != 0; } |
| |
| //default constructor (for preallocation) |
| template <typename Unit> |
| inline PolyLine<Unit>::PolyLine() : ptdata_() ,headp_(0), tailp_(0), state_(-1) {} |
| |
| //constructor |
| template <typename Unit> |
| inline PolyLine<Unit>::PolyLine(orientation_2d orient, Unit coord, Side side) : |
| ptdata_(1, coord), |
| headp_(0), |
| tailp_(0), |
| state_(orient.to_int() + |
| (side << 3)) {} |
| |
| //copy constructor |
| template <typename Unit> |
| inline PolyLine<Unit>::PolyLine(const PolyLine<Unit>& pline) : ptdata_(pline.ptdata_), |
| headp_(pline.headp_), |
| tailp_(pline.tailp_), |
| state_(pline.state_) {} |
| |
| //destructor |
| template <typename Unit> |
| inline PolyLine<Unit>::~PolyLine() { |
| //clear out data just in case it is read later |
| headp_ = tailp_ = 0; |
| state_ = 0; |
| } |
| |
| template <typename Unit> |
| inline PolyLine<Unit>& PolyLine<Unit>::operator=(const PolyLine<Unit>& that) { |
| if(!(this == &that)) { |
| headp_ = that.headp_; |
| tailp_ = that.tailp_; |
| ptdata_ = that.ptdata_; |
| state_ = that.state_; |
| } |
| return *this; |
| } |
| |
| template <typename Unit> |
| inline bool PolyLine<Unit>::operator==(const PolyLine<Unit>& b) const { |
| return this == &b || (state_ == b.state_ && |
| headp_ == b.headp_ && |
| tailp_ == b.tailp_); |
| } |
| |
| //valid PolyLine |
| template <typename Unit> |
| inline bool PolyLine<Unit>::isValid() const { |
| return state_ > -1; } |
| |
| //first coordinate is an X value |
| //first segment is vertical |
| template <typename Unit> |
| inline bool PolyLine<Unit>::verticalHead() const { |
| return state_ & VERTICAL_HEAD; |
| } |
| |
| //retrun true is PolyLine has odd number of coordiantes |
| template <typename Unit> |
| inline bool PolyLine<Unit>::oddLength() const { |
| return to_bool((ptdata_.size()-1) % 2); |
| } |
| |
| //last coordiante is an X value |
| //last segment is vertical |
| template <typename Unit> |
| 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); |
| } |
| |
| template <typename Unit> |
| inline orientation_2d PolyLine<Unit>::headOrient() const { |
| return (verticalHead() ? VERTICAL : HORIZONTAL); |
| } |
| |
| template <typename Unit> |
| inline End PolyLine<Unit>::endConnectivity(End end) const { |
| //Tail should be defined as true |
| if(end) { return tailToTail(); } |
| return headToTail(); |
| } |
| |
| template <typename Unit> |
| inline bool PolyLine<Unit>::headToTail() const { |
| return to_bool(state_ & HEAD_TO_TAIL); |
| } |
| |
| template <typename Unit> |
| inline bool PolyLine<Unit>::headToHead() const { |
| return to_bool(!headToTail()); |
| } |
| |
| template <typename Unit> |
| 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 { |
| return solidToRight(); } |
| |
| template <typename Unit> |
| inline bool PolyLine<Unit>::solidToRight() const { |
| return to_bool(state_ & SOLID_TO_RIGHT) != 0; |
| } |
| |
| template <typename Unit> |
| inline bool PolyLine<Unit>::active() const { |
| return !to_bool(tailp_); |
| } |
| |
| template <typename Unit> |
| inline PolyLine<Unit>& PolyLine<Unit>::pushCoordinate(Unit coord) { |
| ptdata_.push_back(coord); |
| return *this; |
| } |
| |
| template <typename Unit> |
| inline PolyLine<Unit>& PolyLine<Unit>::popCoordinate() { |
| ptdata_.pop_back(); |
| return *this; |
| } |
| |
| template <typename Unit> |
| inline PolyLine<Unit>& PolyLine<Unit>::pushPoint(const point_data<Unit>& point) { |
| point_data<Unit> 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 <typename Unit> |
| inline PolyLine<Unit>& PolyLine<Unit>::extendTail(Unit delta) { |
| ptdata_.back() += delta; |
| return *this; |
| } |
| |
| //private member function that creates a link from this PolyLine to that |
| template <typename Unit> |
| inline PolyLine<Unit>& PolyLine<Unit>::joinTo_(End thisEnd, PolyLine<Unit>& 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 <typename Unit> |
| inline PolyLine<Unit>& PolyLine<Unit>::joinTo(End thisEnd, PolyLine<Unit>& that, End end) { |
| joinTo_(thisEnd, that, end); |
| that.joinTo_(end, *this, thisEnd); |
| return *this; |
| } |
| |
| //convenience functions for joining PolyLines |
| template <typename Unit> |
| inline PolyLine<Unit>& PolyLine<Unit>::joinToTail(PolyLine<Unit>& that, End end) { |
| return joinTo(TAIL, that, end); |
| } |
| template <typename Unit> |
| inline PolyLine<Unit>& PolyLine<Unit>::joinToHead(PolyLine<Unit>& that, End end) { |
| return joinTo(HEAD, that, end); |
| } |
| template <typename Unit> |
| inline PolyLine<Unit>& PolyLine<Unit>::joinHeadToHead(PolyLine<Unit>& that) { |
| return joinToHead(that, HEAD); |
| } |
| template <typename Unit> |
| inline PolyLine<Unit>& PolyLine<Unit>::joinHeadToTail(PolyLine<Unit>& that) { |
| return joinToHead(that, TAIL); |
| } |
| template <typename Unit> |
| inline PolyLine<Unit>& PolyLine<Unit>::joinTailToHead(PolyLine<Unit>& that) { |
| return joinToTail(that, HEAD); |
| } |
| template <typename Unit> |
| inline PolyLine<Unit>& PolyLine<Unit>::joinTailToTail(PolyLine<Unit>& that) { |
| return joinToTail(that, TAIL); |
| } |
| |
| template <typename Unit> |
| inline PolyLine<Unit>& PolyLine<Unit>::disconnectTails() { |
| next(TAIL)->state_ &= !TAIL_TO_TAIL; |
| next(TAIL)->tailp_ = 0; |
| state_ &= !TAIL_TO_TAIL; |
| tailp_ = 0; |
| return *this; |
| } |
| |
| template <typename Unit> |
| inline Unit PolyLine<Unit>::getEndCoord(End end) const { |
| if(end) |
| return ptdata_.back(); |
| return ptdata_.front(); |
| } |
| |
| template <typename Unit> |
| inline orientation_2d PolyLine<Unit>::segmentOrient(unsigned int index) const { |
| return (to_bool((unsigned int)verticalHead() ^ (index % 2)) ? VERTICAL : HORIZONTAL); |
| } |
| |
| template <typename Unit> |
| inline point_data<Unit> PolyLine<Unit>::getPoint(unsigned int index) const { |
| //assert(isValid() && headp_->isValid()) ("PolyLine: headp_ must be valid"); |
| point_data<Unit> 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 <typename Unit> |
| inline point_data<Unit> PolyLine<Unit>::getEndPoint(End end) const { |
| return getPoint((end ? numSegments() - 1 : (unsigned int)0)); |
| } |
| |
| template <typename Unit> |
| inline Unit PolyLine<Unit>::operator[] (unsigned int index) const { |
| //assert(ptdata_.size() > index) ("PolyLine: out of bounds index"); |
| return ptdata_[index]; |
| } |
| |
| template <typename Unit> |
| inline unsigned int PolyLine<Unit>::numSegments() const { |
| return ptdata_.size(); |
| } |
| |
| template <typename Unit> |
| inline PolyLine<Unit>* PolyLine<Unit>::next(End end) const { |
| return (end ? tailp_ : headp_); |
| } |
| |
| template <typename Unit> |
| inline ActiveTail<Unit>::ActiveTail() : tailp_(0), otherTailp_(0), holesList_() {} |
| |
| template <typename Unit> |
| inline ActiveTail<Unit>::ActiveTail(orientation_2d orient, Unit coord, Side solidToRight, ActiveTail* otherTailp) : |
| tailp_(0), otherTailp_(0), holesList_() { |
| tailp_ = createPolyLine(orient, coord, solidToRight); |
| otherTailp_ = otherTailp; |
| } |
| |
| template <typename Unit> |
| inline ActiveTail<Unit>::ActiveTail(PolyLine<Unit>* active, ActiveTail<Unit>* otherTailp) : |
| tailp_(active), otherTailp_(otherTailp), holesList_() {} |
| |
| //copy constructor |
| template <typename Unit> |
| inline ActiveTail<Unit>::ActiveTail(const ActiveTail<Unit>& that) : tailp_(that.tailp_), otherTailp_(that.otherTailp_), holesList_() {} |
| |
| //destructor |
| template <typename Unit> |
| inline ActiveTail<Unit>::~ActiveTail() { |
| //clear them in case the memory is read later |
| tailp_ = 0; otherTailp_ = 0; |
| } |
| |
| template <typename Unit> |
| inline ActiveTail<Unit>& ActiveTail<Unit>::operator=(const ActiveTail<Unit>& that) { |
| //self assignment is safe in this case |
| tailp_ = that.tailp_; |
| otherTailp_ = that.otherTailp_; |
| return *this; |
| } |
| |
| template <typename Unit> |
| inline bool ActiveTail<Unit>::operator==(const ActiveTail<Unit>& b) const { |
| return tailp_ == b.tailp_ && otherTailp_ == b.otherTailp_; |
| } |
| |
| template <typename Unit> |
| inline bool ActiveTail<Unit>::operator<(const ActiveTail<Unit>& b) const { |
| return tailp_->getEndPoint().get(VERTICAL) < b.tailp_->getEndPoint().get(VERTICAL); |
| } |
| |
| template <typename Unit> |
| 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 { |
| return b < (*this); } |
| |
| template <typename Unit> |
| inline bool ActiveTail<Unit>::operator>=(const ActiveTail<Unit>& b) const { |
| return !(*this < b); } |
| |
| template <typename Unit> |
| inline PolyLine<Unit>* ActiveTail<Unit>::getTail() const { |
| return tailp_; } |
| |
| template <typename Unit> |
| inline PolyLine<Unit>* ActiveTail<Unit>::getOtherTail() const { |
| return otherTailp_->tailp_; } |
| |
| template <typename Unit> |
| 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_)) |
| // ("ActiveTail: Active tails out of sync"); |
| return otherTailp_ == &b; |
| } |
| |
| template <typename Unit> |
| inline ActiveTail<Unit>& ActiveTail<Unit>::updateTail(PolyLine<Unit>* newTail) { |
| tailp_ = newTail; |
| return *this; |
| } |
| |
| template <typename Unit> |
| inline ActiveTail<Unit>* ActiveTail<Unit>::addHole(ActiveTail<Unit>* hole, bool fractureHoles) { |
| if(!fractureHoles){ |
| holesList_.push_back(hole); |
| copyHoles(*hole); |
| copyHoles(*(hole->getOtherActiveTail())); |
| return this; |
| } |
| ActiveTail<Unit>* h, *v; |
| ActiveTail<Unit>* 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<Unit> tmpVec; |
| ActiveTail<Unit>::joinChains(this, h, false, tmpVec); |
| return v; |
| } |
| |
| template <typename Unit> |
| inline const std::list<ActiveTail<Unit>*>& ActiveTail<Unit>::getHoles() const { |
| return holesList_; |
| } |
| |
| template <typename Unit> |
| inline void ActiveTail<Unit>::copyHoles(ActiveTail<Unit>& that) { |
| holesList_.splice(holesList_.end(), that.holesList_); //splice the two lists together |
| } |
| |
| template <typename Unit> |
| inline bool ActiveTail<Unit>::solidToRight() const { |
| return getTail()->solidToRight(); } |
| |
| template <typename Unit> |
| inline Unit ActiveTail<Unit>::getCoord() const { |
| return getTail()->getEndCoord(); } |
| |
| template <typename Unit> |
| inline Unit ActiveTail<Unit>::getCoordinate() const { |
| return getCoord(); } |
| |
| template <typename Unit> |
| inline orientation_2d ActiveTail<Unit>::getOrient() const { |
| return getTail()->tailOrient(); } |
| |
| template <typename Unit> |
| 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); |
| 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()); |
| tailp_->pushPoint(p); |
| } |
| |
| |
| //global utility functions |
| template <typename Unit> |
| inline PolyLine<Unit>* createPolyLine(orientation_2d orient, Unit coord, Side side) { |
| return new PolyLine<Unit>(orient, coord, side); |
| } |
| |
| template <typename Unit> |
| inline void destroyPolyLine(PolyLine<Unit>* pLine) { |
| delete pLine; |
| } |
| |
| template <typename Unit> |
| inline ActiveTail<Unit>* createActiveTail() { |
| //consider replacing system allocator with ActiveTail memory pool |
| return new ActiveTail<Unit>(); |
| } |
| |
| template <typename Unit> |
| inline void destroyActiveTail(ActiveTail<Unit>* aTail) { |
| delete aTail; |
| } |
| |
| |
| //no recursion, to prevent max recursion depth errors |
| template <typename Unit> |
| inline void ActiveTail<Unit>::destroyContents() { |
| tailp_->disconnectTails(); |
| PolyLine<Unit>* 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<Unit>* nextNextPolyLinep = nextPolyLinep->next(!end); //get the next polyline |
| destroyPolyLine(nextPolyLinep); //destroy the current polyline |
| end = nextEnd; |
| nextPolyLinep = nextNextPolyLinep; |
| } |
| } |
| |
| template <typename Unit> |
| inline typename ActiveTail<Unit>::iterator ActiveTail<Unit>::begin(bool isHole, orientation_2d orient) const { |
| return iterator(this, isHole, orient); |
| } |
| |
| template <typename Unit> |
| inline typename ActiveTail<Unit>::iterator ActiveTail<Unit>::end() const { |
| return iterator(); |
| } |
| |
| template <typename Unit> |
| inline typename ActiveTail<Unit>::iteratorHoles ActiveTail<Unit>::beginHoles() const { |
| return holesList_.begin(); |
| } |
| |
| template <typename Unit> |
| inline typename ActiveTail<Unit>::iteratorHoles ActiveTail<Unit>::endHoles() const { |
| return holesList_.end(); |
| } |
| |
| template <typename Unit> |
| inline void ActiveTail<Unit>::writeOutFigureItrs(iterator& beginOut, iterator& endOut, bool isHole, orientation_2d orient) const { |
| beginOut = begin(isHole, orient); |
| endOut = end(); |
| } |
| |
| template <typename Unit> |
| inline void ActiveTail<Unit>::writeOutFigureHoleItrs(iteratorHoles& beginOut, iteratorHoles& endOut) const { |
| beginOut = beginHoles(); |
| endOut = endHoles(); |
| } |
| |
| template <typename Unit> |
| inline void ActiveTail<Unit>::writeOutFigure(std::vector<Unit>& 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<Unit>* 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<Unit>::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 <typename Unit> |
| inline PolyLine<Unit>* PolyLine<Unit>::writeOut(std::vector<Unit>& 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 <typename Unit> |
| 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)){ |
| //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<ActiveTail<Unit>*>& holes = at1->getHoles(); |
| for(typename std::list<ActiveTail<Unit>*>::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()); |
| 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 <typename Unit> |
| template <typename PolygonT> |
| 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)){ |
| //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<Unit>(at1->getOtherTail(), at2->getOtherActiveTail()); |
| *(at2->getOtherActiveTail()) = ActiveTail<Unit>(at2->getOtherTail(), at1->getOtherActiveTail()); |
| at1->getOtherActiveTail()->copyHoles(*at1); |
| at1->getOtherActiveTail()->copyHoles(*at2); |
| destroyActiveTail(at1); |
| destroyActiveTail(at2); |
| 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) |
| { |
| 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 <typename Unit> |
| inline std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> createActiveTailsAsPair(Unit x, Unit y, bool solid, ActiveTail<Unit>* phole, bool fractureHoles) { |
| ActiveTail<Unit>* at1 = 0; |
| ActiveTail<Unit>* at2 = 0; |
| if(!phole || !fractureHoles){ |
| at1 = createActiveTail<Unit>(); |
| at2 = createActiveTail<Unit>(); |
| (*at1) = ActiveTail<Unit>(VERTICAL, x, solid, at2); |
| (*at2) = ActiveTail<Unit>(HORIZONTAL, y, !solid, at1); |
| //provide a function through activeTail class to provide this |
| at1->getTail()->joinHeadToHead(*(at2->getTail())); |
| if(phole) |
| at1->addHole(phole, fractureHoles); //assert fractureHoles == false |
| return std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*>(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<Unit>*, ActiveTail<Unit>*>(at1, at2); |
| } |
| |
| //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 |
| //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, |
| std::vector<interval_data<Unit> >& rightEdges) { |
| clearOutput_(); |
| typename std::map<Unit, ActiveTail<Unit>*>::iterator nextMapItr = tailMap_.begin(); |
| //foreach edge |
| unsigned int leftIndex = 0; |
| unsigned int rightIndex = 0; |
| bool bottomAlreadyProcessed = false; |
| ActiveTail<Unit>* currentTail = 0; |
| const Unit UnitMax = (std::numeric_limits<Unit>::max)(); |
| while(leftIndex < leftEdges.size() || rightIndex < rightEdges.size()) { |
| interval_data<Unit> edges[2] = {interval_data<Unit> (UnitMax, UnitMax), interval_data<Unit> (UnitMax, UnitMax)}; |
| bool haveNextEdge = true; |
| if(leftIndex < leftEdges.size()) |
| edges[0] = leftEdges[leftIndex]; |
| else |
| haveNextEdge = false; |
| if(rightIndex < rightEdges.size()) |
| edges[1] = rightEdges[rightIndex]; |
| else |
| haveNextEdge = false; |
| bool trailingEdge = edges[1].get(LOW) < edges[0].get(LOW); |
| interval_data<Unit> & edge = edges[trailingEdge]; |
| interval_data<Unit> & nextEdge = edges[!trailingEdge]; |
| //process this edge |
| if(!bottomAlreadyProcessed) { |
| //assert currentTail = 0 |
| |
| //process the bottom end of this edge |
| typename std::map<Unit, ActiveTail<Unit>*>::iterator thisMapItr = findAtNext(tailMap_, nextMapItr, edge.get(LOW)); |
| if(thisMapItr != tailMap_.end()) { |
| //there is an edge in the map at the low end of this edge |
| //it needs to turn upward and become the current tail |
| ActiveTail<Unit>* tail = thisMapItr->second; |
| if(currentTail) { |
| //stitch currentTail into this tail |
| currentTail = tail->addHole(currentTail, fractureHoles_); |
| if(!fractureHoles_) |
| currentTail->pushCoordinate(currentX); |
| } else { |
| currentTail = tail; |
| currentTail->pushCoordinate(currentX); |
| } |
| //assert currentTail->getOrient() == VERTICAL |
| nextMapItr = thisMapItr; //set nextMapItr to the next position after this one |
| ++nextMapItr; |
| //remove thisMapItr from the map |
| tailMap_.erase(thisMapItr); |
| } else { |
| //there is no edge in the map at the low end of this edge |
| //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 = |
| createActiveTailsAsPair(currentX, edge.get(LOW), !trailingEdge, currentTail, fractureHoles_); |
| currentTail = tailPair.first; |
| tailMap_.insert(nextMapItr, std::pair<Unit, ActiveTail<Unit>*>(edge.get(LOW), tailPair.second)); |
| // leave nextMapItr unchanged |
| } |
| |
| } |
| if(haveNextEdge && edge.get(HIGH) == nextEdge.get(LOW)) { |
| //the top of this edge is equal to the bottom of the next edge, process them both |
| bottomAlreadyProcessed = true; |
| typename std::map<Unit, ActiveTail<Unit>*>::iterator thisMapItr = findAtNext(tailMap_, nextMapItr, edge.get(HIGH)); |
| if(thisMapItr == tailMap_.end()) //assert this should never happen |
| return; |
| if(trailingEdge) { |
| //geometry at this position |
| // |## |
| // |## |
| // ----- |
| // ##| |
| // ##| |
| //current tail should join thisMapItr tail |
| ActiveTail<Unit>* tail = thisMapItr->second; |
| //pass false because they are being joined because space is to the right and it will close a solid figure |
| ActiveTail<Unit>::joinChains(currentTail, tail, false, outputPolygons_); |
| //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 = |
| createActiveTailsAsPair<Unit>(currentX, edge.get(HIGH), true, 0, fractureHoles_); |
| currentTail = tailPair.first; |
| thisMapItr->second = tailPair.second; |
| } else { |
| //geometry at this position |
| // ##| |
| // ##| |
| // ----- |
| // |## |
| // |## |
| //current tail should turn right |
| currentTail->pushCoordinate(edge.get(HIGH)); |
| //thisMapItr tail should turn up |
| thisMapItr->second->pushCoordinate(currentX); |
| //thisMapItr tail becomes current tail and current tail becomes thisMapItr tail |
| std::swap(currentTail, thisMapItr->second); |
| } |
| nextMapItr = thisMapItr; //set nextMapItr to the next position after this one |
| ++nextMapItr; |
| } else { |
| //there is a gap between the top of this edge and the bottom of the next, process the top of this edge |
| bottomAlreadyProcessed = false; |
| //process the top of this edge |
| typename std::map<Unit, ActiveTail<Unit>*>::iterator thisMapItr = findAtNext(tailMap_, nextMapItr, edge.get(HIGH)); |
| if(thisMapItr != tailMap_.end()) { |
| //thisMapItr is pointing to a horizontal edge in the map at the top of this vertical edge |
| //we need to join them and potentially close a figure |
| //assert currentTail != 0 |
| ActiveTail<Unit>* tail = thisMapItr->second; |
| //pass the opositve of trailing edge to mean that they are joined because of solid to the right |
| currentTail = ActiveTail<Unit>::joinChains(currentTail, tail, !trailingEdge, outputPolygons_); |
| nextMapItr = thisMapItr; //set nextMapItr to the next position after this one |
| ++nextMapItr; |
| if(currentTail) { |
| Unit nextItrY = UnitMax; |
| if(nextMapItr != tailMap_.end()) { |
| nextItrY = nextMapItr->first; |
| } |
| //for it to be a hole this must have been a left edge |
| Unit leftY = UnitMax; |
| if(leftIndex + 1 < leftEdges.size()) |
| leftY = leftEdges[leftIndex+1].get(LOW); |
| Unit rightY = nextEdge.get(LOW); |
| if(!haveNextEdge || (nextItrY < leftY && nextItrY < rightY)) { |
| //we need to add it to the next edge above it in the map |
| tail = nextMapItr->second; |
| tail = tail->addHole(currentTail, fractureHoles_); |
| if(fractureHoles_) { |
| //some small additional work stitching in the filament |
| tail->pushCoordinate(nextItrY); |
| nextMapItr->second = tail; |
| } |
| //set current tail to null |
| currentTail = 0; |
| } |
| } |
| //delete thisMapItr from the map |
| tailMap_.erase(thisMapItr); |
| } else { |
| //currentTail must turn right and be added into the map |
| currentTail->pushCoordinate(edge.get(HIGH)); |
| //assert currentTail->getOrient() == HORIZONTAL |
| tailMap_.insert(nextMapItr, std::pair<Unit, ActiveTail<Unit>*>(edge.get(HIGH), currentTail)); |
| //set currentTail to null |
| currentTail = 0; |
| //leave nextMapItr unchanged, it is still next |
| } |
| } |
| |
| //increment index |
| leftIndex += !trailingEdge; |
| rightIndex += trailingEdge; |
| } //end while |
| beginOutput = outputPolygons_.begin(); |
| endOutput = outputPolygons_.end(); |
| } //end function |
| |
| template<bool orientT, typename Unit, typename polygon_concept_type> |
| inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>::clearOutput_() { |
| for(std::size_t i = 0; i < outputPolygons_.size(); ++i) { |
| ActiveTail<Unit>* at1 = outputPolygons_[i].yield(); |
| const std::list<ActiveTail<Unit>*>& holes = at1->getHoles(); |
| for(typename std::list<ActiveTail<Unit>*>::const_iterator litr = holes.begin(); litr != holes.end(); ++litr) { |
| //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)->getOtherActiveTail()); |
| destroyActiveTail(at1); |
| } |
| outputPolygons_.clear(); |
| } |
| |
| } //polygon_formation namespace |
| |
| template <bool orientT, typename Unit> |
| struct geometry_concept<polygon_formation::PolyLinePolygonWithHolesData<orientT, Unit> > { |
| typedef polygon_90_with_holes_concept type; |
| }; |
| |
| template <bool orientT, typename Unit> |
| struct geometry_concept<polygon_formation::PolyLineHoleData<orientT, Unit> > { |
| typedef polygon_90_concept type; |
| }; |
| |
| //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 ) { |
| typedef typename output_container::value_type polygon_type; |
| typedef typename std::iterator_traits<iterator_type>::value_type::first_type coordinate_type; |
| polygon_type poly; |
| unsigned int countPolygons = 0; |
| typedef typename geometry_concept<polygon_type>::type polygon_concept_type; |
| polygon_formation::ScanLineToPolygonItrs<true, coordinate_type, polygon_concept_type> scanlineToPolygonItrsV(fracture_holes); |
| polygon_formation::ScanLineToPolygonItrs<false, coordinate_type, polygon_concept_type> scanlineToPolygonItrsH(fracture_holes); |
| std::vector<interval_data<coordinate_type> > leftEdges; |
| std::vector<interval_data<coordinate_type> > rightEdges; |
| coordinate_type prevPos = (std::numeric_limits<coordinate_type>::max)(); |
| coordinate_type prevY = (std::numeric_limits<coordinate_type>::max)(); |
| int count = 0; |
| for(iterator_type itr = begin; |
| itr != end; ++ itr) { |
| coordinate_type pos = (*itr).first; |
| if(pos != prevPos) { |
| if(orient == VERTICAL) { |
| typename polygon_formation::ScanLineToPolygonItrs<true, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd; |
| scanlineToPolygonItrsV.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges); |
| for( ; itrPoly != itrPolyEnd; ++ itrPoly) { |
| ++countPolygons; |
| assign(poly, *itrPoly); |
| container.insert(container.end(), poly); |
| } |
| } else { |
| typename polygon_formation::ScanLineToPolygonItrs<false, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd; |
| scanlineToPolygonItrsH.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges); |
| for( ; itrPoly != itrPolyEnd; ++ itrPoly) { |
| ++countPolygons; |
| assign(poly, *itrPoly); |
| container.insert(container.end(), poly); |
| } |
| } |
| leftEdges.clear(); |
| rightEdges.clear(); |
| prevPos = pos; |
| prevY = (*itr).second.first; |
| count = (*itr).second.second; |
| continue; |
| } |
| coordinate_type y = (*itr).second.first; |
| if(count != 0 && y != prevY) { |
| std::pair<interval_data<coordinate_type>, int> element(interval_data<coordinate_type>(prevY, y), count); |
| if(element.second == 1) { |
| if(leftEdges.size() && leftEdges.back().high() == element.first.low()) { |
| encompass(leftEdges.back(), element.first); |
| } else { |
| leftEdges.push_back(element.first); |
| } |
| } else { |
| if(rightEdges.size() && rightEdges.back().high() == element.first.low()) { |
| encompass(rightEdges.back(), element.first); |
| } else { |
| rightEdges.push_back(element.first); |
| } |
| } |
| |
| } |
| prevY = y; |
| count += (*itr).second.second; |
| } |
| if(orient == VERTICAL) { |
| typename polygon_formation::ScanLineToPolygonItrs<true, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd; |
| scanlineToPolygonItrsV.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges); |
| for( ; itrPoly != itrPolyEnd; ++ itrPoly) { |
| ++countPolygons; |
| assign(poly, *itrPoly); |
| container.insert(container.end(), poly); |
| } |
| } else { |
| typename polygon_formation::ScanLineToPolygonItrs<false, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd; |
| scanlineToPolygonItrsH.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges); |
| for( ; itrPoly != itrPolyEnd; ++ itrPoly) { |
| ++countPolygons; |
| assign(poly, *itrPoly); |
| container.insert(container.end(), poly); |
| } |
| } |
| return countPolygons; |
| } |
| |
| } |
| } |
| #endif |
| |