| /* |
| 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_45_FORMATION_HPP |
| #define BOOST_POLYGON_POLYGON_45_FORMATION_HPP |
| namespace boost { namespace polygon{ |
| |
| template <typename T, typename T2> |
| struct PolyLineByConcept {}; |
| |
| template <typename T> |
| class PolyLine45PolygonData; |
| template <typename T> |
| class PolyLine45HoleData; |
| |
| //polygon45formation algorithm |
| template <typename Unit> |
| struct polygon_45_formation : public boolean_op_45<Unit> { |
| typedef point_data<Unit> Point; |
| typedef polygon_45_data<Unit> Polygon45; |
| typedef polygon_45_with_holes_data<Unit> Polygon45WithHoles; |
| typedef typename boolean_op_45<Unit>::Vertex45 Vertex45; |
| typedef typename boolean_op_45<Unit>::lessVertex45 lessVertex45; |
| typedef typename boolean_op_45<Unit>::Count2 Count2; |
| typedef typename boolean_op_45<Unit>::Scan45Count Scan45Count; |
| typedef std::pair<Point, Scan45Count> Scan45Vertex; |
| typedef typename boolean_op_45<Unit>::template |
| Scan45<Count2, typename boolean_op_45<Unit>::template boolean_op_45_output_functor<0> > Scan45; |
| |
| class PolyLine45 { |
| public: |
| typedef typename std::list<Point>::const_iterator iterator; |
| |
| // default constructor of point does not initialize x and y |
| inline PolyLine45() : points() {} //do nothing default constructor |
| |
| // 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 PolyLine45& set(iT inputBegin, iT inputEnd) { |
| points.clear(); //just in case there was some old data there |
| while(inputBegin != inputEnd) { |
| points.insert(points.end(), *inputBegin); |
| ++inputBegin; |
| } |
| return *this; |
| } |
| |
| // copy constructor (since we have dynamic memory) |
| inline PolyLine45(const PolyLine45& that) : points(that.points) {} |
| |
| // assignment operator (since we have dynamic memory do a deep copy) |
| inline PolyLine45& operator=(const PolyLine45& that) { |
| points = that.points; |
| return *this; |
| } |
| |
| // get begin iterator, returns a pointer to a const Unit |
| inline iterator begin() const { return points.begin(); } |
| |
| // get end iterator, returns a pointer to a const Unit |
| inline iterator end() const { return points.end(); } |
| |
| inline std::size_t size() const { return points.size(); } |
| |
| //public data member |
| std::list<Point> points; |
| }; |
| |
| class ActiveTail45 { |
| private: |
| //data |
| PolyLine45* tailp_; |
| ActiveTail45 *otherTailp_; |
| std::list<ActiveTail45*> holesList_; |
| bool head_; |
| public: |
| |
| /** |
| * @brief iterator over coordinates of the figure |
| */ |
| typedef typename PolyLine45::iterator iterator; |
| |
| /** |
| * @brief iterator over holes contained within the figure |
| */ |
| typedef typename std::list<ActiveTail45*>::const_iterator iteratorHoles; |
| |
| //default constructor |
| inline ActiveTail45() : tailp_(0), otherTailp_(0), holesList_(), head_(0) {} |
| |
| //constructor |
| inline ActiveTail45(const Vertex45& vertex, ActiveTail45* otherTailp = 0) : |
| tailp_(0), otherTailp_(0), holesList_(), head_(0) { |
| tailp_ = new PolyLine45; |
| tailp_->points.push_back(vertex.pt); |
| bool headArray[4] = {false, true, true, true}; |
| bool inverted = vertex.count == -1; |
| head_ = headArray[vertex.rise+1] ^ inverted; |
| otherTailp_ = otherTailp; |
| } |
| |
| inline ActiveTail45(Point point, ActiveTail45* otherTailp, bool head = true) : |
| tailp_(0), otherTailp_(0), holesList_(), head_(0) { |
| tailp_ = new PolyLine45; |
| tailp_->points.push_back(point); |
| head_ = head; |
| otherTailp_ = otherTailp; |
| |
| } |
| inline ActiveTail45(ActiveTail45* otherTailp) : |
| tailp_(0), otherTailp_(0), holesList_(), head_(0) { |
| tailp_ = otherTailp->tailp_; |
| otherTailp_ = otherTailp; |
| } |
| |
| //copy constructor |
| inline ActiveTail45(const ActiveTail45& that) : |
| tailp_(0), otherTailp_(0), holesList_(), head_(0) { (*this) = that; } |
| |
| //destructor |
| inline ~ActiveTail45() { |
| destroyContents(); |
| } |
| |
| //assignment operator |
| inline ActiveTail45& operator=(const ActiveTail45& that) { |
| tailp_ = new PolyLine45(*(that.tailp_)); |
| head_ = that.head_; |
| otherTailp_ = that.otherTailp_; |
| holesList_ = that.holesList_; |
| return *this; |
| } |
| |
| //equivalence operator |
| inline bool operator==(const ActiveTail45& b) const { |
| return tailp_ == b.tailp_ && head_ == b.head_; |
| } |
| |
| /** |
| * @brief get the pointer to the polyline that this is an active tail of |
| */ |
| inline PolyLine45* getTail() const { return tailp_; } |
| |
| /** |
| * @brief get the pointer to the polyline at the other end of the chain |
| */ |
| inline PolyLine45* getOtherTail() const { return otherTailp_->tailp_; } |
| |
| /** |
| * @brief get the pointer to the activetail at the other end of the chain |
| */ |
| inline ActiveTail45* getOtherActiveTail() const { return otherTailp_; } |
| |
| /** |
| * @brief test if another active tail is the other end of the chain |
| */ |
| inline bool isOtherTail(const ActiveTail45& b) const { return &b == otherTailp_; } |
| |
| /** |
| * @brief update this end of chain pointer to new polyline |
| */ |
| inline ActiveTail45& updateTail(PolyLine45* newTail) { tailp_ = newTail; return *this; } |
| |
| inline bool join(ActiveTail45* tail) { |
| if(tail == otherTailp_) { |
| //std::cout << "joining to other tail!\n"; |
| return false; |
| } |
| if(tail->head_ == head_) { |
| //std::cout << "joining head to head!\n"; |
| return false; |
| } |
| if(!tailp_) { |
| //std::cout << "joining empty tail!\n"; |
| return false; |
| } |
| if(!(otherTailp_->head_)) { |
| otherTailp_->copyHoles(*tail); |
| otherTailp_->copyHoles(*this); |
| } else { |
| tail->otherTailp_->copyHoles(*this); |
| tail->otherTailp_->copyHoles(*tail); |
| } |
| PolyLine45* tail1 = tailp_; |
| PolyLine45* tail2 = tail->tailp_; |
| if(head_) std::swap(tail1, tail2); |
| tail1->points.splice(tail1->points.end(), tail2->points); |
| delete tail2; |
| otherTailp_->tailp_ = tail1; |
| tail->otherTailp_->tailp_ = tail1; |
| otherTailp_->otherTailp_ = tail->otherTailp_; |
| tail->otherTailp_->otherTailp_ = otherTailp_; |
| tailp_ = 0; |
| tail->tailp_ = 0; |
| tail->otherTailp_ = 0; |
| otherTailp_ = 0; |
| return true; |
| } |
| |
| /** |
| * @brief associate a hole to this active tail by the specified policy |
| */ |
| inline ActiveTail45* addHole(ActiveTail45* hole) { |
| holesList_.push_back(hole); |
| copyHoles(*hole); |
| copyHoles(*(hole->otherTailp_)); |
| return this; |
| } |
| |
| /** |
| * @brief get the list of holes |
| */ |
| inline const std::list<ActiveTail45*>& getHoles() const { return holesList_; } |
| |
| /** |
| * @brief copy holes from that to this |
| */ |
| inline void copyHoles(ActiveTail45& that) { holesList_.splice(holesList_.end(), that.holesList_); } |
| |
| /** |
| * @brief find out if solid to right |
| */ |
| inline bool solidToRight() const { return !head_; } |
| inline bool solidToLeft() const { return head_; } |
| |
| /** |
| * @brief get vertex |
| */ |
| inline Point getPoint() const { |
| if(head_) return tailp_->points.front(); |
| return tailp_->points.back(); |
| } |
| |
| /** |
| * @brief add a coordinate to the polygon at this active tail end, properly handle degenerate edges by removing redundant coordinate |
| */ |
| inline void pushPoint(Point point) { |
| if(head_) { |
| //if(tailp_->points.size() < 2) { |
| // tailp_->points.push_front(point); |
| // return; |
| //} |
| typename std::list<Point>::iterator iter = tailp_->points.begin(); |
| if(iter == tailp_->points.end()) { |
| tailp_->points.push_front(point); |
| return; |
| } |
| Unit firstY = (*iter).y(); |
| Unit firstX = (*iter).x(); |
| ++iter; |
| if(iter == tailp_->points.end()) { |
| tailp_->points.push_front(point); |
| return; |
| } |
| if((iter->y() == point.y() && firstY == point.y()) || |
| (iter->x() == point.x() && firstX == point.x())){ |
| --iter; |
| *iter = point; |
| } else { |
| tailp_->points.push_front(point); |
| } |
| return; |
| } |
| //if(tailp_->points.size() < 2) { |
| // tailp_->points.push_back(point); |
| // return; |
| //} |
| typename std::list<Point>::reverse_iterator iter = tailp_->points.rbegin(); |
| if(iter == tailp_->points.rend()) { |
| tailp_->points.push_back(point); |
| return; |
| } |
| Unit firstY = (*iter).y(); |
| Unit firstX = (*iter).x(); |
| ++iter; |
| if(iter == tailp_->points.rend()) { |
| tailp_->points.push_back(point); |
| return; |
| } |
| if((iter->y() == point.y() && firstY == point.y()) || |
| (iter->x() == point.x() && firstX == point.x())){ |
| --iter; |
| *iter = point; |
| } else { |
| tailp_->points.push_back(point); |
| } |
| } |
| |
| /** |
| * @brief 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 |
| */ |
| |
| template <class cT> |
| static inline ActiveTail45* joinChains(Point point, ActiveTail45* at1, ActiveTail45* at2, bool solid, |
| cT& output) { |
| if(at1->otherTailp_ == at2) { |
| //if(at2->otherTailp_ != at1) std::cout << "half closed error\n"; |
| //we are closing a figure |
| at1->pushPoint(point); |
| at2->pushPoint(point); |
| if(solid) { |
| //we are closing a solid figure, write to output |
| //std::cout << "test1\n"; |
| at1->copyHoles(*(at1->otherTailp_)); |
| //std::cout << "test2\n"; |
| //Polygon45WithHolesImpl<PolyLine45PolygonData> poly(polyData); |
| //std::cout << poly << std::endl; |
| //std::cout << "test3\n"; |
| typedef typename cT::value_type pType; |
| output.push_back(pType()); |
| typedef typename geometry_concept<pType>::type cType; |
| typename PolyLineByConcept<Unit, cType>::type polyData(at1); |
| assign(output.back(), polyData); |
| //std::cout << "test4\n"; |
| //std::cout << "delete " << at1->otherTailp_ << std::endl; |
| //at1->print(); |
| //at1->otherTailp_->print(); |
| delete at1->otherTailp_; |
| //at1->print(); |
| //at1->otherTailp_->print(); |
| //std::cout << "test5\n"; |
| //std::cout << "delete " << at1 << std::endl; |
| delete at1; |
| //std::cout << "test6\n"; |
| return 0; |
| } else { |
| //we are closing a hole, return the tail end active tail of the figure |
| return at1; |
| } |
| } |
| //we are not closing a figure |
| at1->pushPoint(point); |
| at1->join(at2); |
| delete at1; |
| delete at2; |
| return 0; |
| } |
| |
| inline void destroyContents() { |
| if(otherTailp_) { |
| //std::cout << "delete p " << tailp_ << std::endl; |
| if(tailp_) delete tailp_; |
| tailp_ = 0; |
| otherTailp_->otherTailp_ = 0; |
| otherTailp_->tailp_ = 0; |
| otherTailp_ = 0; |
| } |
| for(typename std::list<ActiveTail45*>::iterator itr = holesList_.begin(); itr != holesList_.end(); ++itr) { |
| //std::cout << "delete p " << (*itr) << std::endl; |
| if(*itr) { |
| if((*itr)->otherTailp_) { |
| delete (*itr)->otherTailp_; |
| (*itr)->otherTailp_ = 0; |
| } |
| delete (*itr); |
| } |
| (*itr) = 0; |
| } |
| holesList_.clear(); |
| } |
| |
| // inline void print() { |
| // std::cout << this << " " << tailp_ << " " << otherTailp_ << " " << holesList_.size() << " " << head_ << std::endl; |
| // } |
| |
| static inline std::pair<ActiveTail45*, ActiveTail45*> createActiveTail45sAsPair(Point point, bool solid, |
| ActiveTail45* phole, bool fractureHoles) { |
| ActiveTail45* at1 = 0; |
| ActiveTail45* at2 = 0; |
| if(phole && fractureHoles) { |
| //std::cout << "adding hole\n"; |
| at1 = phole; |
| //assert solid == false, we should be creating a corner with solid below and to the left if there was a hole |
| at2 = at1->getOtherActiveTail(); |
| at2->pushPoint(point); |
| at1->pushPoint(point); |
| } else { |
| at1 = new ActiveTail45(point, at2, solid); |
| at2 = new ActiveTail45(at1); |
| at1->otherTailp_ = at2; |
| at2->head_ = !solid; |
| if(phole) |
| at2->addHole(phole); //assert fractureHoles == false |
| } |
| return std::pair<ActiveTail45*, ActiveTail45*>(at1, at2); |
| } |
| |
| }; |
| |
| template <typename ct> |
| class Vertex45CountT { |
| public: |
| typedef ct count_type; |
| inline Vertex45CountT() |
| #ifndef BOOST_POLYGON_MSVC |
| : counts() |
| #endif |
| { counts[0] = counts[1] = counts[2] = counts[3] = 0; } |
| //inline Vertex45CountT(ct count) { counts[0] = counts[1] = counts[2] = counts[3] = count; } |
| inline Vertex45CountT(const ct& count1, const ct& count2, const ct& count3, |
| const ct& count4) |
| #ifndef BOOST_POLYGON_MSVC |
| : counts() |
| #endif |
| { |
| counts[0] = count1; |
| counts[1] = count2; |
| counts[2] = count3; |
| counts[3] = count4; |
| } |
| inline Vertex45CountT(const Vertex45& vertex) |
| #ifndef BOOST_POLYGON_MSVC |
| : counts() |
| #endif |
| { |
| counts[0] = counts[1] = counts[2] = counts[3] = 0; |
| (*this) += vertex; |
| } |
| inline Vertex45CountT(const Vertex45CountT& count) |
| #ifndef BOOST_POLYGON_MSVC |
| : counts() |
| #endif |
| { |
| (*this) = count; |
| } |
| inline bool operator==(const Vertex45CountT& count) const { |
| for(unsigned int i = 0; i < 4; ++i) { |
| if(counts[i] != count.counts[i]) return false; |
| } |
| return true; |
| } |
| inline bool operator!=(const Vertex45CountT& count) const { return !((*this) == count); } |
| inline Vertex45CountT& operator=(ct count) { |
| counts[0] = counts[1] = counts[2] = counts[3] = count; return *this; } |
| inline Vertex45CountT& operator=(const Vertex45CountT& count) { |
| for(unsigned int i = 0; i < 4; ++i) { |
| counts[i] = count.counts[i]; |
| } |
| return *this; |
| } |
| inline ct& operator[](int index) { return counts[index]; } |
| inline ct operator[](int index) const {return counts[index]; } |
| inline Vertex45CountT& operator+=(const Vertex45CountT& count){ |
| for(unsigned int i = 0; i < 4; ++i) { |
| counts[i] += count.counts[i]; |
| } |
| return *this; |
| } |
| inline Vertex45CountT& operator-=(const Vertex45CountT& count){ |
| for(unsigned int i = 0; i < 4; ++i) { |
| counts[i] -= count.counts[i]; |
| } |
| return *this; |
| } |
| inline Vertex45CountT operator+(const Vertex45CountT& count) const { |
| return Vertex45CountT(*this)+=count; |
| } |
| inline Vertex45CountT operator-(const Vertex45CountT& count) const { |
| return Vertex45CountT(*this)-=count; |
| } |
| inline Vertex45CountT invert() const { |
| return Vertex45CountT()-=(*this); |
| } |
| inline Vertex45CountT& operator+=(const Vertex45& element){ |
| counts[element.rise+1] += element.count; return *this; |
| } |
| inline bool is_45() const { |
| return counts[0] != 0 || counts[2] != 0; |
| } |
| private: |
| ct counts[4]; |
| }; |
| |
| typedef Vertex45CountT<int> Vertex45Count; |
| |
| // inline std::ostream& operator<< (std::ostream& o, const Vertex45Count& c) { |
| // o << c[0] << ", " << c[1] << ", "; |
| // o << c[2] << ", " << c[3]; |
| // return o; |
| // } |
| |
| template <typename ct> |
| class Vertex45CompactT { |
| public: |
| Point pt; |
| ct count; |
| typedef typename boolean_op_45<Unit>::template Vertex45T<typename ct::count_type> Vertex45T; |
| inline Vertex45CompactT() : pt(), count() {} |
| inline Vertex45CompactT(const Point& point, int riseIn, int countIn) : pt(point), count() { |
| count[riseIn+1] = countIn; |
| } |
| template <typename ct2> |
| inline Vertex45CompactT(const typename boolean_op_45<Unit>::template Vertex45T<ct2>& vertex) : pt(vertex.pt), count() { |
| count[vertex.rise+1] = vertex.count; |
| } |
| inline Vertex45CompactT(const Vertex45CompactT& vertex) : pt(vertex.pt), count(vertex.count) {} |
| inline Vertex45CompactT& operator=(const Vertex45CompactT& vertex){ |
| pt = vertex.pt; count = vertex.count; return *this; } |
| inline bool operator==(const Vertex45CompactT& vertex) const { |
| return pt == vertex.pt && count == vertex.count; } |
| inline bool operator!=(const Vertex45CompactT& vertex) const { return !((*this) == vertex); } |
| inline bool operator==(const std::pair<Point, Point>& vertex) const { return false; } |
| inline bool operator!=(const std::pair<Point, Point>& vertex) const { return !((*this) == vertex); } |
| inline bool operator<(const Vertex45CompactT& vertex) const { |
| if(pt.x() < vertex.pt.x()) return true; |
| if(pt.x() == vertex.pt.x()) { |
| return pt.y() < vertex.pt.y(); |
| } |
| return false; |
| } |
| inline bool operator>(const Vertex45CompactT& vertex) const { return vertex < (*this); } |
| inline bool operator<=(const Vertex45CompactT& vertex) const { return !((*this) > vertex); } |
| inline bool operator>=(const Vertex45CompactT& vertex) const { return !((*this) < vertex); } |
| inline bool haveVertex45(int index) const { return count[index]; } |
| inline Vertex45T operator[](int index) const { |
| return Vertex45T(pt, index-1, count[index]); } |
| }; |
| |
| typedef Vertex45CompactT<Vertex45Count> Vertex45Compact; |
| |
| // inline std::ostream& operator<< (std::ostream& o, const Vertex45Compact& c) { |
| // o << c.pt << ", " << c.count; |
| // return o; |
| // } |
| |
| class Polygon45Formation { |
| private: |
| //definitions |
| typedef std::map<Vertex45, ActiveTail45*, lessVertex45> Polygon45FormationData; |
| typedef typename Polygon45FormationData::iterator iterator; |
| typedef typename Polygon45FormationData::const_iterator const_iterator; |
| |
| //data |
| Polygon45FormationData scanData_; |
| Unit x_; |
| int justBefore_; |
| int fractureHoles_; |
| public: |
| inline Polygon45Formation() : scanData_(), x_((std::numeric_limits<Unit>::min)()), justBefore_(false), fractureHoles_(0) { |
| lessVertex45 lessElm(&x_, &justBefore_); |
| scanData_ = Polygon45FormationData(lessElm); |
| } |
| inline Polygon45Formation(bool fractureHoles) : scanData_(), x_((std::numeric_limits<Unit>::min)()), justBefore_(false), fractureHoles_(fractureHoles) { |
| lessVertex45 lessElm(&x_, &justBefore_); |
| scanData_ = Polygon45FormationData(lessElm); |
| } |
| inline Polygon45Formation(const Polygon45Formation& that) : |
| scanData_(), x_((std::numeric_limits<Unit>::min)()), justBefore_(false), fractureHoles_(0) { (*this) = that; } |
| inline Polygon45Formation& operator=(const Polygon45Formation& that) { |
| x_ = that.x_; |
| justBefore_ = that.justBefore_; |
| fractureHoles_ = that.fractureHoles_; |
| lessVertex45 lessElm(&x_, &justBefore_); |
| scanData_ = Polygon45FormationData(lessElm); |
| for(const_iterator itr = that.scanData_.begin(); itr != that.scanData_.end(); ++itr){ |
| scanData_.insert(scanData_.end(), *itr); |
| } |
| return *this; |
| } |
| |
| //cT is an output container of Polygon45 or Polygon45WithHoles |
| //iT is an iterator over Vertex45 elements |
| //inputBegin - inputEnd is a range of sorted iT that represents |
| //one or more scanline stops worth of data |
| template <class cT, class iT> |
| void scan(cT& output, iT inputBegin, iT inputEnd) { |
| //std::cout << "1\n"; |
| while(inputBegin != inputEnd) { |
| //std::cout << "2\n"; |
| x_ = (*inputBegin).pt.x(); |
| //std::cout << "SCAN FORMATION " << x_ << std::endl; |
| //std::cout << "x_ = " << x_ << std::endl; |
| //std::cout << "scan line size: " << scanData_.size() << std::endl; |
| inputBegin = processEvent_(output, inputBegin, inputEnd); |
| } |
| } |
| |
| private: |
| //functions |
| template <class cT, class cT2> |
| inline std::pair<int, ActiveTail45*> processPoint_(cT& output, cT2& elements, Point point, |
| Vertex45Count& counts, ActiveTail45** tails, Vertex45Count& incoming) { |
| //std::cout << point << std::endl; |
| //std::cout << counts[0] << " "; |
| //std::cout << counts[1] << " "; |
| //std::cout << counts[2] << " "; |
| //std::cout << counts[3] << "\n"; |
| //std::cout << incoming[0] << " "; |
| //std::cout << incoming[1] << " "; |
| //std::cout << incoming[2] << " "; |
| //std::cout << incoming[3] << "\n"; |
| //join any closing solid corners |
| ActiveTail45* returnValue = 0; |
| int returnCount = 0; |
| for(int i = 0; i < 3; ++i) { |
| //std::cout << i << std::endl; |
| if(counts[i] == -1) { |
| //std::cout << "fixed i\n"; |
| for(int j = i + 1; j < 4; ++j) { |
| //std::cout << j << std::endl; |
| if(counts[j]) { |
| if(counts[j] == 1) { |
| //std::cout << "case1: " << i << " " << j << std::endl; |
| //if a figure is closed it will be written out by this function to output |
| ActiveTail45::joinChains(point, tails[i], tails[j], true, output); |
| counts[i] = 0; |
| counts[j] = 0; |
| tails[i] = 0; |
| tails[j] = 0; |
| } |
| break; |
| } |
| } |
| } |
| } |
| //find any pairs of incoming edges that need to create pair for leading solid |
| //std::cout << "checking case2\n"; |
| for(int i = 0; i < 3; ++i) { |
| //std::cout << i << std::endl; |
| if(incoming[i] == 1) { |
| //std::cout << "fixed i\n"; |
| for(int j = i + 1; j < 4; ++j) { |
| //std::cout << j << std::endl; |
| if(incoming[j]) { |
| if(incoming[j] == -1) { |
| //std::cout << "case2: " << i << " " << j << std::endl; |
| //std::cout << "creating active tail pair\n"; |
| std::pair<ActiveTail45*, ActiveTail45*> tailPair = |
| ActiveTail45::createActiveTail45sAsPair(point, true, 0, fractureHoles_ != 0); |
| //tailPair.first->print(); |
| //tailPair.second->print(); |
| if(j == 3) { |
| //vertical active tail becomes return value |
| returnValue = tailPair.first; |
| returnCount = 1; |
| } else { |
| Vertex45 vertex(point, i -1, incoming[i]); |
| //std::cout << "new element " << j-1 << " " << -1 << std::endl; |
| elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, j -1, -1), tailPair.first)); |
| } |
| //std::cout << "new element " << i-1 << " " << 1 << std::endl; |
| elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, i -1, 1), tailPair.second)); |
| incoming[i] = 0; |
| incoming[j] = 0; |
| } |
| break; |
| } |
| } |
| } |
| } |
| |
| //find any active tail that needs to pass through to an incoming edge |
| //we expect to find no more than two pass through |
| |
| //find pass through with solid on top |
| //std::cout << "checking case 3\n"; |
| for(int i = 0; i < 4; ++i) { |
| //std::cout << i << std::endl; |
| if(counts[i] != 0) { |
| if(counts[i] == 1) { |
| //std::cout << "fixed i\n"; |
| for(int j = 3; j >= 0; --j) { |
| if(incoming[j] != 0) { |
| if(incoming[j] == 1) { |
| //std::cout << "case3: " << i << " " << j << std::endl; |
| //tails[i]->print(); |
| //pass through solid on top |
| tails[i]->pushPoint(point); |
| //std::cout << "after push\n"; |
| if(j == 3) { |
| returnValue = tails[i]; |
| returnCount = -1; |
| } else { |
| elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, j -1, incoming[j]), tails[i])); |
| } |
| tails[i] = 0; |
| counts[i] = 0; |
| incoming[j] = 0; |
| } |
| break; |
| } |
| } |
| } |
| break; |
| } |
| } |
| //std::cout << "checking case 4\n"; |
| //find pass through with solid on bottom |
| for(int i = 3; i >= 0; --i) { |
| if(counts[i] != 0) { |
| if(counts[i] == -1) { |
| for(int j = 0; j < 4; ++j) { |
| if(incoming[j] != 0) { |
| if(incoming[j] == -1) { |
| //std::cout << "case4: " << i << " " << j << std::endl; |
| //pass through solid on bottom |
| tails[i]->pushPoint(point); |
| if(j == 3) { |
| returnValue = tails[i]; |
| returnCount = 1; |
| } else { |
| //std::cout << "new element " << j-1 << " " << incoming[j] << std::endl; |
| elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, j -1, incoming[j]), tails[i])); |
| } |
| tails[i] = 0; |
| counts[i] = 0; |
| incoming[j] = 0; |
| } |
| break; |
| } |
| } |
| } |
| break; |
| } |
| } |
| |
| //find the end of a hole or the beginning of a hole |
| |
| //find end of a hole |
| for(int i = 0; i < 3; ++i) { |
| if(counts[i] != 0) { |
| for(int j = i+1; j < 4; ++j) { |
| if(counts[j] != 0) { |
| //std::cout << "case5: " << i << " " << j << std::endl; |
| //we are ending a hole and may potentially close a figure and have to handle the hole |
| returnValue = ActiveTail45::joinChains(point, tails[i], tails[j], false, output); |
| tails[i] = 0; |
| tails[j] = 0; |
| counts[i] = 0; |
| counts[j] = 0; |
| break; |
| } |
| } |
| break; |
| } |
| } |
| //find beginning of a hole |
| for(int i = 0; i < 3; ++i) { |
| if(incoming[i] != 0) { |
| for(int j = i+1; j < 4; ++j) { |
| if(incoming[j] != 0) { |
| //std::cout << "case6: " << i << " " << j << std::endl; |
| //we are beginning a empty space |
| ActiveTail45* holep = 0; |
| if(counts[3] == 0) holep = tails[3]; |
| std::pair<ActiveTail45*, ActiveTail45*> tailPair = |
| ActiveTail45::createActiveTail45sAsPair(point, false, holep, fractureHoles_ != 0); |
| if(j == 3) { |
| returnValue = tailPair.first; |
| returnCount = -1; |
| } else { |
| //std::cout << "new element " << j-1 << " " << incoming[j] << std::endl; |
| elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, j -1, incoming[j]), tailPair.first)); |
| } |
| //std::cout << "new element " << i-1 << " " << incoming[i] << std::endl; |
| elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, i -1, incoming[i]), tailPair.second)); |
| incoming[i] = 0; |
| incoming[j] = 0; |
| break; |
| } |
| } |
| break; |
| } |
| } |
| //assert that tails, counts and incoming are all null |
| return std::pair<int, ActiveTail45*>(returnCount, returnValue); |
| } |
| |
| template <class cT, class iT> |
| inline iT processEvent_(cT& output, iT inputBegin, iT inputEnd) { |
| //std::cout << "processEvent_\n"; |
| justBefore_ = true; |
| //collect up all elements from the tree that are at the y |
| //values of events in the input queue |
| //create vector of new elements to add into tree |
| ActiveTail45* verticalTail = 0; |
| int verticalCount = 0; |
| iT currentIter = inputBegin; |
| std::vector<iterator> elementIters; |
| std::vector<std::pair<Vertex45, ActiveTail45*> > elements; |
| while(currentIter != inputEnd && currentIter->pt.x() == x_) { |
| //std::cout << "loop\n"; |
| Unit currentY = (*currentIter).pt.y(); |
| iterator iter = lookUp_(currentY); |
| //int counts[4] = {0, 0, 0, 0}; |
| Vertex45Count counts; |
| ActiveTail45* tails[4] = {0, 0, 0, verticalTail}; |
| //std::cout << "finding elements in tree\n"; |
| while(iter != scanData_.end() && |
| iter->first.evalAtX(x_) == currentY) { |
| //std::cout << "loop2\n"; |
| elementIters.push_back(iter); |
| int index = iter->first.rise + 1; |
| //std::cout << index << " " << iter->first.count << std::endl; |
| counts[index] = iter->first.count; |
| tails[index] = iter->second; |
| ++iter; |
| } |
| //int incoming[4] = {0, 0, 0, 0}; |
| Vertex45Count incoming; |
| //std::cout << "aggregating\n"; |
| do { |
| //std::cout << "loop3\n"; |
| Vertex45Compact currentVertex(*currentIter); |
| incoming += currentVertex.count; |
| ++currentIter; |
| } while(currentIter != inputEnd && currentIter->pt.y() == currentY && |
| currentIter->pt.x() == x_); |
| //now counts and tails have the data from the left and |
| //incoming has the data from the right at this point |
| //cancel out any end points |
| //std::cout << counts[0] << " "; |
| //std::cout << counts[1] << " "; |
| //std::cout << counts[2] << " "; |
| //std::cout << counts[3] << "\n"; |
| //std::cout << incoming[0] << " "; |
| //std::cout << incoming[1] << " "; |
| //std::cout << incoming[2] << " "; |
| //std::cout << incoming[3] << "\n"; |
| if(verticalTail) { |
| counts[3] = -verticalCount; |
| } |
| incoming[3] *= -1; |
| for(unsigned int i = 0; i < 4; ++i) incoming[i] += counts[i]; |
| //std::cout << "calling processPoint_\n"; |
| std::pair<int, ActiveTail45*> result = processPoint_(output, elements, Point(x_, currentY), counts, tails, incoming); |
| verticalCount = result.first; |
| verticalTail = result.second; |
| //if(verticalTail) std::cout << "have vertical tail\n"; |
| //std::cout << "verticalCount: " << verticalCount << std::endl; |
| if(verticalTail && !verticalCount) { |
| //we got a hole out of the point we just processed |
| //iter is still at the next y element above the current y value in the tree |
| //std::cout << "checking whether ot handle hole\n"; |
| if(currentIter == inputEnd || |
| currentIter->pt.x() != x_ || |
| currentIter->pt.y() >= iter->first.evalAtX(x_)) { |
| //std::cout << "handle hole here\n"; |
| if(fractureHoles_) { |
| //std::cout << "fracture hole here\n"; |
| //we need to handle the hole now and not at the next input vertex |
| ActiveTail45* at = iter->second; |
| Point point(x_, iter->first.evalAtX(x_)); |
| verticalTail->getOtherActiveTail()->pushPoint(point); |
| iter->second = verticalTail->getOtherActiveTail(); |
| at->pushPoint(point); |
| verticalTail->join(at); |
| delete at; |
| delete verticalTail; |
| verticalTail = 0; |
| } else { |
| //std::cout << "push hole onto list\n"; |
| iter->second->addHole(verticalTail); |
| verticalTail = 0; |
| } |
| } |
| } |
| } |
| //std::cout << "erasing\n"; |
| //erase all elements from the tree |
| for(typename std::vector<iterator>::iterator iter = elementIters.begin(); |
| iter != elementIters.end(); ++iter) { |
| //std::cout << "erasing loop\n"; |
| scanData_.erase(*iter); |
| } |
| //switch comparison tie breaking policy |
| justBefore_ = false; |
| //add new elements into tree |
| //std::cout << "inserting\n"; |
| for(typename std::vector<std::pair<Vertex45, ActiveTail45*> >::iterator iter = elements.begin(); |
| iter != elements.end(); ++iter) { |
| //std::cout << "inserting loop\n"; |
| scanData_.insert(scanData_.end(), *iter); |
| } |
| //std::cout << "end processEvent\n"; |
| return currentIter; |
| } |
| |
| inline iterator lookUp_(Unit y){ |
| //if just before then we need to look from 1 not -1 |
| return scanData_.lower_bound(Vertex45(Point(x_, y), -1+2*justBefore_, 0)); |
| } |
| |
| }; |
| |
| template <typename stream_type> |
| static inline bool testPolygon45FormationRect(stream_type& stdcout) { |
| stdcout << "testing polygon formation\n"; |
| Polygon45Formation pf(true); |
| std::vector<Polygon45> polys; |
| std::vector<Vertex45> data; |
| data.push_back(Vertex45(Point(0, 0), 0, 1)); |
| data.push_back(Vertex45(Point(0, 0), 2, 1)); |
| data.push_back(Vertex45(Point(0, 10), 2, -1)); |
| data.push_back(Vertex45(Point(0, 10), 0, -1)); |
| data.push_back(Vertex45(Point(10, 0), 0, -1)); |
| data.push_back(Vertex45(Point(10, 0), 2, -1)); |
| data.push_back(Vertex45(Point(10, 10), 2, 1)); |
| data.push_back(Vertex45(Point(10, 10), 0, 1)); |
| gtlsort(data.begin(), data.end()); |
| pf.scan(polys, data.begin(), data.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon formation\n"; |
| return true; |
| } |
| |
| template <typename stream_type> |
| static inline bool testPolygon45FormationP1(stream_type& stdcout) { |
| stdcout << "testing polygon formation\n"; |
| Polygon45Formation pf(true); |
| std::vector<Polygon45> polys; |
| std::vector<Vertex45> data; |
| data.push_back(Vertex45(Point(0, 0), 1, 1)); |
| data.push_back(Vertex45(Point(0, 0), 2, 1)); |
| data.push_back(Vertex45(Point(0, 10), 2, -1)); |
| data.push_back(Vertex45(Point(0, 10), 1, -1)); |
| data.push_back(Vertex45(Point(10, 10), 1, -1)); |
| data.push_back(Vertex45(Point(10, 10), 2, -1)); |
| data.push_back(Vertex45(Point(10, 20), 2, 1)); |
| data.push_back(Vertex45(Point(10, 20), 1, 1)); |
| gtlsort(data.begin(), data.end()); |
| pf.scan(polys, data.begin(), data.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon formation\n"; |
| return true; |
| } |
| //polygon45set class |
| |
| template <typename stream_type> |
| static inline bool testPolygon45FormationP2(stream_type& stdcout) { |
| stdcout << "testing polygon formation\n"; |
| Polygon45Formation pf(true); |
| std::vector<Polygon45> polys; |
| std::vector<Vertex45> data; |
| data.push_back(Vertex45(Point(0, 0), 0, 1)); |
| data.push_back(Vertex45(Point(0, 0), 1, -1)); |
| data.push_back(Vertex45(Point(10, 0), 0, -1)); |
| data.push_back(Vertex45(Point(10, 0), 1, 1)); |
| data.push_back(Vertex45(Point(10, 10), 1, 1)); |
| data.push_back(Vertex45(Point(10, 10), 0, -1)); |
| data.push_back(Vertex45(Point(20, 10), 1, -1)); |
| data.push_back(Vertex45(Point(20, 10), 0, 1)); |
| gtlsort(data.begin(), data.end()); |
| pf.scan(polys, data.begin(), data.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon formation\n"; |
| return true; |
| } |
| //polygon45set class |
| |
| template <typename stream_type> |
| static inline bool testPolygon45FormationStar1(stream_type& stdcout) { |
| stdcout << "testing polygon formation\n"; |
| Polygon45Formation pf(true); |
| std::vector<Polygon45> polys; |
| std::vector<Vertex45> data; |
| // result == 0 8 -1 1 |
| data.push_back(Vertex45(Point(0, 8), -1, 1)); |
| // result == 0 8 1 -1 |
| data.push_back(Vertex45(Point(0, 8), 1, -1)); |
| // result == 4 0 1 1 |
| data.push_back(Vertex45(Point(4, 0), 1, 1)); |
| // result == 4 0 2 1 |
| data.push_back(Vertex45(Point(4, 0), 2, 1)); |
| // result == 4 4 2 -1 |
| data.push_back(Vertex45(Point(4, 4), 2, -1)); |
| // result == 4 4 -1 -1 |
| data.push_back(Vertex45(Point(4, 4), -1, -1)); |
| // result == 4 12 1 1 |
| data.push_back(Vertex45(Point(4, 12), 1, 1)); |
| // result == 4 12 2 1 |
| data.push_back(Vertex45(Point(4, 12), 2, 1)); |
| // result == 4 16 2 -1 |
| data.push_back(Vertex45(Point(4, 16), 2, 1)); |
| // result == 4 16 -1 -1 |
| data.push_back(Vertex45(Point(4, 16), -1, -1)); |
| // result == 6 2 1 -1 |
| data.push_back(Vertex45(Point(6, 2), 1, -1)); |
| // result == 6 14 -1 1 |
| data.push_back(Vertex45(Point(6, 14), -1, 1)); |
| // result == 6 2 -1 1 |
| data.push_back(Vertex45(Point(6, 2), -1, 1)); |
| // result == 6 14 1 -1 |
| data.push_back(Vertex45(Point(6, 14), 1, -1)); |
| // result == 8 0 -1 -1 |
| data.push_back(Vertex45(Point(8, 0), -1, -1)); |
| // result == 8 0 2 -1 |
| data.push_back(Vertex45(Point(8, 0), 2, -1)); |
| // result == 8 4 2 1 |
| data.push_back(Vertex45(Point(8, 4), 2, 1)); |
| // result == 8 4 1 1 |
| data.push_back(Vertex45(Point(8, 4), 1, 1)); |
| // result == 8 12 -1 -1 |
| data.push_back(Vertex45(Point(8, 12), -1, -1)); |
| // result == 8 12 2 -1 |
| data.push_back(Vertex45(Point(8, 12), 2, -1)); |
| // result == 8 16 2 1 |
| data.push_back(Vertex45(Point(8, 16), 2, 1)); |
| // result == 8 16 1 1 |
| data.push_back(Vertex45(Point(8, 16), 1, 1)); |
| // result == 12 8 1 -1 |
| data.push_back(Vertex45(Point(12, 8), 1, -1)); |
| // result == 12 8 -1 1 |
| data.push_back(Vertex45(Point(12, 8), -1, 1)); |
| gtlsort(data.begin(), data.end()); |
| pf.scan(polys, data.begin(), data.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon formation\n"; |
| return true; |
| } |
| |
| template <typename stream_type> |
| static inline bool testPolygon45FormationStar2(stream_type& stdcout) { |
| stdcout << "testing polygon formation\n"; |
| Polygon45Formation pf(true); |
| std::vector<Polygon45> polys; |
| Scan45 scan45; |
| std::vector<Vertex45 > result; |
| std::vector<Scan45Vertex> vertices; |
| //is a Rectnagle(0, 0, 10, 10); |
| Count2 count(1, 0); |
| Count2 ncount(-1, 0); |
| vertices.push_back(Scan45Vertex(Point(0,4), Scan45Count(Count2(0, 0), count, ncount, Count2(0, 0)))); |
| vertices.push_back(Scan45Vertex(Point(16,4), Scan45Count(count, ncount, Count2(0, 0), Count2(0, 0)))); |
| vertices.push_back(Scan45Vertex(Point(8,12), Scan45Count(ncount, Count2(0, 0), count, Count2(0, 0)))); |
| count = Count2(0, 1); |
| ncount = count.invert(); |
| vertices.push_back(Scan45Vertex(Point(0,8), Scan45Count(count, ncount, Count2(0, 0), Count2(0, 0)))); |
| vertices.push_back(Scan45Vertex(Point(16,8), Scan45Count(Count2(0, 0), count, ncount, Count2(0, 0)))); |
| vertices.push_back(Scan45Vertex(Point(8,0), Scan45Count(ncount, Count2(0, 0), count, Count2(0, 0)))); |
| sortScan45Vector(vertices); |
| stdcout << "scanning\n"; |
| scan45.scan(result, vertices.begin(), vertices.end()); |
| |
| gtlsort(result.begin(), result.end()); |
| pf.scan(polys, result.begin(), result.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon formation\n"; |
| return true; |
| } |
| |
| template <typename stream_type> |
| static inline bool testPolygon45FormationStarHole1(stream_type& stdcout) { |
| stdcout << "testing polygon formation\n"; |
| Polygon45Formation pf(true); |
| std::vector<Polygon45> polys; |
| std::vector<Vertex45> data; |
| // result == 0 8 -1 1 |
| data.push_back(Vertex45(Point(0, 8), -1, 1)); |
| // result == 0 8 1 -1 |
| data.push_back(Vertex45(Point(0, 8), 1, -1)); |
| // result == 4 0 1 1 |
| data.push_back(Vertex45(Point(4, 0), 1, 1)); |
| // result == 4 0 2 1 |
| data.push_back(Vertex45(Point(4, 0), 2, 1)); |
| // result == 4 4 2 -1 |
| data.push_back(Vertex45(Point(4, 4), 2, -1)); |
| // result == 4 4 -1 -1 |
| data.push_back(Vertex45(Point(4, 4), -1, -1)); |
| // result == 4 12 1 1 |
| data.push_back(Vertex45(Point(4, 12), 1, 1)); |
| // result == 4 12 2 1 |
| data.push_back(Vertex45(Point(4, 12), 2, 1)); |
| // result == 4 16 2 -1 |
| data.push_back(Vertex45(Point(4, 16), 2, 1)); |
| // result == 4 16 -1 -1 |
| data.push_back(Vertex45(Point(4, 16), -1, -1)); |
| // result == 6 2 1 -1 |
| data.push_back(Vertex45(Point(6, 2), 1, -1)); |
| // result == 6 14 -1 1 |
| data.push_back(Vertex45(Point(6, 14), -1, 1)); |
| // result == 6 2 -1 1 |
| data.push_back(Vertex45(Point(6, 2), -1, 1)); |
| // result == 6 14 1 -1 |
| data.push_back(Vertex45(Point(6, 14), 1, -1)); |
| // result == 8 0 -1 -1 |
| data.push_back(Vertex45(Point(8, 0), -1, -1)); |
| // result == 8 0 2 -1 |
| data.push_back(Vertex45(Point(8, 0), 2, -1)); |
| // result == 8 4 2 1 |
| data.push_back(Vertex45(Point(8, 4), 2, 1)); |
| // result == 8 4 1 1 |
| data.push_back(Vertex45(Point(8, 4), 1, 1)); |
| // result == 8 12 -1 -1 |
| data.push_back(Vertex45(Point(8, 12), -1, -1)); |
| // result == 8 12 2 -1 |
| data.push_back(Vertex45(Point(8, 12), 2, -1)); |
| // result == 8 16 2 1 |
| data.push_back(Vertex45(Point(8, 16), 2, 1)); |
| // result == 8 16 1 1 |
| data.push_back(Vertex45(Point(8, 16), 1, 1)); |
| // result == 12 8 1 -1 |
| data.push_back(Vertex45(Point(12, 8), 1, -1)); |
| // result == 12 8 -1 1 |
| data.push_back(Vertex45(Point(12, 8), -1, 1)); |
| |
| data.push_back(Vertex45(Point(6, 4), 1, -1)); |
| data.push_back(Vertex45(Point(6, 4), 2, -1)); |
| data.push_back(Vertex45(Point(6, 8), -1, 1)); |
| data.push_back(Vertex45(Point(6, 8), 2, 1)); |
| data.push_back(Vertex45(Point(8, 6), -1, -1)); |
| data.push_back(Vertex45(Point(8, 6), 1, 1)); |
| |
| gtlsort(data.begin(), data.end()); |
| pf.scan(polys, data.begin(), data.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon formation\n"; |
| return true; |
| } |
| |
| template <typename stream_type> |
| static inline bool testPolygon45FormationStarHole2(stream_type& stdcout) { |
| stdcout << "testing polygon formation\n"; |
| Polygon45Formation pf(false); |
| std::vector<Polygon45WithHoles> polys; |
| std::vector<Vertex45> data; |
| // result == 0 8 -1 1 |
| data.push_back(Vertex45(Point(0, 8), -1, 1)); |
| // result == 0 8 1 -1 |
| data.push_back(Vertex45(Point(0, 8), 1, -1)); |
| // result == 4 0 1 1 |
| data.push_back(Vertex45(Point(4, 0), 1, 1)); |
| // result == 4 0 2 1 |
| data.push_back(Vertex45(Point(4, 0), 2, 1)); |
| // result == 4 4 2 -1 |
| data.push_back(Vertex45(Point(4, 4), 2, -1)); |
| // result == 4 4 -1 -1 |
| data.push_back(Vertex45(Point(4, 4), -1, -1)); |
| // result == 4 12 1 1 |
| data.push_back(Vertex45(Point(4, 12), 1, 1)); |
| // result == 4 12 2 1 |
| data.push_back(Vertex45(Point(4, 12), 2, 1)); |
| // result == 4 16 2 -1 |
| data.push_back(Vertex45(Point(4, 16), 2, 1)); |
| // result == 4 16 -1 -1 |
| data.push_back(Vertex45(Point(4, 16), -1, -1)); |
| // result == 6 2 1 -1 |
| data.push_back(Vertex45(Point(6, 2), 1, -1)); |
| // result == 6 14 -1 1 |
| data.push_back(Vertex45(Point(6, 14), -1, 1)); |
| // result == 6 2 -1 1 |
| data.push_back(Vertex45(Point(6, 2), -1, 1)); |
| // result == 6 14 1 -1 |
| data.push_back(Vertex45(Point(6, 14), 1, -1)); |
| // result == 8 0 -1 -1 |
| data.push_back(Vertex45(Point(8, 0), -1, -1)); |
| // result == 8 0 2 -1 |
| data.push_back(Vertex45(Point(8, 0), 2, -1)); |
| // result == 8 4 2 1 |
| data.push_back(Vertex45(Point(8, 4), 2, 1)); |
| // result == 8 4 1 1 |
| data.push_back(Vertex45(Point(8, 4), 1, 1)); |
| // result == 8 12 -1 -1 |
| data.push_back(Vertex45(Point(8, 12), -1, -1)); |
| // result == 8 12 2 -1 |
| data.push_back(Vertex45(Point(8, 12), 2, -1)); |
| // result == 8 16 2 1 |
| data.push_back(Vertex45(Point(8, 16), 2, 1)); |
| // result == 8 16 1 1 |
| data.push_back(Vertex45(Point(8, 16), 1, 1)); |
| // result == 12 8 1 -1 |
| data.push_back(Vertex45(Point(12, 8), 1, -1)); |
| // result == 12 8 -1 1 |
| data.push_back(Vertex45(Point(12, 8), -1, 1)); |
| |
| data.push_back(Vertex45(Point(6, 4), 1, -1)); |
| data.push_back(Vertex45(Point(6, 4), 2, -1)); |
| data.push_back(Vertex45(Point(6, 12), -1, 1)); |
| data.push_back(Vertex45(Point(6, 12), 2, 1)); |
| data.push_back(Vertex45(Point(10, 8), -1, -1)); |
| data.push_back(Vertex45(Point(10, 8), 1, 1)); |
| |
| gtlsort(data.begin(), data.end()); |
| pf.scan(polys, data.begin(), data.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon formation\n"; |
| return true; |
| } |
| |
| template <typename stream_type> |
| static inline bool testPolygon45Formation(stream_type& stdcout) { |
| stdcout << "testing polygon formation\n"; |
| Polygon45Formation pf(false); |
| std::vector<Polygon45WithHoles> polys; |
| std::vector<Vertex45> data; |
| |
| data.push_back(Vertex45(Point(0, 0), 0, 1)); |
| data.push_back(Vertex45(Point(0, 0), 2, 1)); |
| data.push_back(Vertex45(Point(0, 100), 2, -1)); |
| data.push_back(Vertex45(Point(0, 100), 0, -1)); |
| data.push_back(Vertex45(Point(100, 0), 0, -1)); |
| data.push_back(Vertex45(Point(100, 0), 2, -1)); |
| data.push_back(Vertex45(Point(100, 100), 2, 1)); |
| data.push_back(Vertex45(Point(100, 100), 0, 1)); |
| |
| data.push_back(Vertex45(Point(2, 2), 0, -1)); |
| data.push_back(Vertex45(Point(2, 2), 2, -1)); |
| data.push_back(Vertex45(Point(2, 10), 2, 1)); |
| data.push_back(Vertex45(Point(2, 10), 0, 1)); |
| data.push_back(Vertex45(Point(10, 2), 0, 1)); |
| data.push_back(Vertex45(Point(10, 2), 2, 1)); |
| data.push_back(Vertex45(Point(10, 10), 2, -1)); |
| data.push_back(Vertex45(Point(10, 10), 0, -1)); |
| |
| data.push_back(Vertex45(Point(2, 12), 0, -1)); |
| data.push_back(Vertex45(Point(2, 12), 2, -1)); |
| data.push_back(Vertex45(Point(2, 22), 2, 1)); |
| data.push_back(Vertex45(Point(2, 22), 0, 1)); |
| data.push_back(Vertex45(Point(10, 12), 0, 1)); |
| data.push_back(Vertex45(Point(10, 12), 2, 1)); |
| data.push_back(Vertex45(Point(10, 22), 2, -1)); |
| data.push_back(Vertex45(Point(10, 22), 0, -1)); |
| |
| gtlsort(data.begin(), data.end()); |
| pf.scan(polys, data.begin(), data.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon formation\n"; |
| return true; |
| } |
| |
| |
| class Polygon45Tiling { |
| private: |
| //definitions |
| typedef std::map<Vertex45, ActiveTail45*, lessVertex45> Polygon45FormationData; |
| typedef typename Polygon45FormationData::iterator iterator; |
| typedef typename Polygon45FormationData::const_iterator const_iterator; |
| |
| //data |
| Polygon45FormationData scanData_; |
| Unit x_; |
| int justBefore_; |
| public: |
| inline Polygon45Tiling() : scanData_(), x_((std::numeric_limits<Unit>::min)()), justBefore_(false) { |
| lessVertex45 lessElm(&x_, &justBefore_); |
| scanData_ = Polygon45FormationData(lessElm); |
| } |
| inline Polygon45Tiling(const Polygon45Tiling& that) : |
| scanData_(), x_((std::numeric_limits<Unit>::min)()), justBefore_(false) { (*this) = that; } |
| inline Polygon45Tiling& operator=(const Polygon45Tiling& that) { |
| x_ = that.x_; |
| justBefore_ = that.justBefore_; |
| lessVertex45 lessElm(&x_, &justBefore_); |
| scanData_ = Polygon45FormationData(lessElm); |
| for(const_iterator itr = that.scanData_.begin(); itr != that.scanData_.end(); ++itr){ |
| scanData_.insert(scanData_.end(), *itr); |
| } |
| return *this; |
| } |
| |
| //cT is an output container of Polygon45 or Polygon45WithHoles |
| //iT is an iterator over Vertex45 elements |
| //inputBegin - inputEnd is a range of sorted iT that represents |
| //one or more scanline stops worth of data |
| template <class cT, class iT> |
| void scan(cT& output, iT inputBegin, iT inputEnd) { |
| //std::cout << "1\n"; |
| while(inputBegin != inputEnd) { |
| //std::cout << "2\n"; |
| x_ = (*inputBegin).pt.x(); |
| //std::cout << "SCAN FORMATION " << x_ << std::endl; |
| //std::cout << "x_ = " << x_ << std::endl; |
| //std::cout << "scan line size: " << scanData_.size() << std::endl; |
| inputBegin = processEvent_(output, inputBegin, inputEnd); |
| } |
| } |
| |
| private: |
| //functions |
| |
| inline void getVerticalPair_(std::pair<ActiveTail45*, ActiveTail45*>& verticalPair, |
| iterator previter) { |
| ActiveTail45* iterTail = (*previter).second; |
| Point prevPoint(x_, previter->first.evalAtX(x_)); |
| iterTail->pushPoint(prevPoint); |
| std::pair<ActiveTail45*, ActiveTail45*> tailPair = |
| ActiveTail45::createActiveTail45sAsPair(prevPoint, true, 0, false); |
| verticalPair.first = iterTail; |
| verticalPair.second = tailPair.first; |
| (*previter).second = tailPair.second; |
| } |
| |
| template <class cT, class cT2> |
| inline std::pair<int, ActiveTail45*> processPoint_(cT& output, cT2& elements, |
| std::pair<ActiveTail45*, ActiveTail45*>& verticalPair, |
| iterator previter, Point point, |
| Vertex45Count& counts, ActiveTail45** tails, Vertex45Count& incoming) { |
| //std::cout << point << std::endl; |
| //std::cout << counts[0] << " "; |
| //std::cout << counts[1] << " "; |
| //std::cout << counts[2] << " "; |
| //std::cout << counts[3] << "\n"; |
| //std::cout << incoming[0] << " "; |
| //std::cout << incoming[1] << " "; |
| //std::cout << incoming[2] << " "; |
| //std::cout << incoming[3] << "\n"; |
| //join any closing solid corners |
| ActiveTail45* returnValue = 0; |
| std::pair<ActiveTail45*, ActiveTail45*> verticalPairOut; |
| verticalPairOut.first = 0; |
| verticalPairOut.second = 0; |
| int returnCount = 0; |
| for(int i = 0; i < 3; ++i) { |
| //std::cout << i << std::endl; |
| if(counts[i] == -1) { |
| //std::cout << "fixed i\n"; |
| for(int j = i + 1; j < 4; ++j) { |
| //std::cout << j << std::endl; |
| if(counts[j]) { |
| if(counts[j] == 1) { |
| //std::cout << "case1: " << i << " " << j << std::endl; |
| //if a figure is closed it will be written out by this function to output |
| ActiveTail45::joinChains(point, tails[i], tails[j], true, output); |
| counts[i] = 0; |
| counts[j] = 0; |
| tails[i] = 0; |
| tails[j] = 0; |
| } |
| break; |
| } |
| } |
| } |
| } |
| //find any pairs of incoming edges that need to create pair for leading solid |
| //std::cout << "checking case2\n"; |
| for(int i = 0; i < 3; ++i) { |
| //std::cout << i << std::endl; |
| if(incoming[i] == 1) { |
| //std::cout << "fixed i\n"; |
| for(int j = i + 1; j < 4; ++j) { |
| //std::cout << j << std::endl; |
| if(incoming[j]) { |
| if(incoming[j] == -1) { |
| //std::cout << "case2: " << i << " " << j << std::endl; |
| //std::cout << "creating active tail pair\n"; |
| std::pair<ActiveTail45*, ActiveTail45*> tailPair = |
| ActiveTail45::createActiveTail45sAsPair(point, true, 0, false); |
| //tailPair.first->print(); |
| //tailPair.second->print(); |
| if(j == 3) { |
| //vertical active tail becomes return value |
| returnValue = tailPair.first; |
| returnCount = 1; |
| } else { |
| Vertex45 vertex(point, i -1, incoming[i]); |
| //std::cout << "new element " << j-1 << " " << -1 << std::endl; |
| elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, j -1, -1), tailPair.first)); |
| } |
| //std::cout << "new element " << i-1 << " " << 1 << std::endl; |
| elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, i -1, 1), tailPair.second)); |
| incoming[i] = 0; |
| incoming[j] = 0; |
| } |
| break; |
| } |
| } |
| } |
| } |
| |
| //find any active tail that needs to pass through to an incoming edge |
| //we expect to find no more than two pass through |
| |
| //find pass through with solid on top |
| //std::cout << "checking case 3\n"; |
| for(int i = 0; i < 4; ++i) { |
| //std::cout << i << std::endl; |
| if(counts[i] != 0) { |
| if(counts[i] == 1) { |
| //std::cout << "fixed i\n"; |
| for(int j = 3; j >= 0; --j) { |
| if(incoming[j] != 0) { |
| if(incoming[j] == 1) { |
| //std::cout << "case3: " << i << " " << j << std::endl; |
| //tails[i]->print(); |
| //pass through solid on top |
| if(i != 3) |
| tails[i]->pushPoint(point); |
| //std::cout << "after push\n"; |
| if(j == 3) { |
| returnValue = tails[i]; |
| returnCount = -1; |
| } else { |
| verticalPairOut.first = tails[i]; |
| std::pair<ActiveTail45*, ActiveTail45*> tailPair = |
| ActiveTail45::createActiveTail45sAsPair(point, true, 0, false); |
| verticalPairOut.second = tailPair.first; |
| elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, j -1, incoming[j]), |
| tailPair.second)); |
| } |
| tails[i] = 0; |
| counts[i] = 0; |
| incoming[j] = 0; |
| } |
| break; |
| } |
| } |
| } |
| break; |
| } |
| } |
| //std::cout << "checking case 4\n"; |
| //find pass through with solid on bottom |
| for(int i = 3; i >= 0; --i) { |
| if(counts[i] != 0) { |
| if(counts[i] == -1) { |
| for(int j = 0; j < 4; ++j) { |
| if(incoming[j] != 0) { |
| if(incoming[j] == -1) { |
| //std::cout << "case4: " << i << " " << j << std::endl; |
| //pass through solid on bottom |
| if(i == 3) { |
| //std::cout << "new element " << j-1 << " " << incoming[j] << std::endl; |
| if(j == 3) { |
| returnValue = tails[i]; |
| returnCount = 1; |
| } else { |
| tails[i]->pushPoint(point); |
| elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, j -1, incoming[j]), tails[i])); |
| } |
| } else if(j == 3) { |
| if(verticalPair.first == 0) { |
| getVerticalPair_(verticalPair, previter); |
| } |
| ActiveTail45::joinChains(point, tails[i], verticalPair.first, true, output); |
| returnValue = verticalPair.second; |
| returnCount = 1; |
| } else { |
| if(verticalPair.first == 0) { |
| getVerticalPair_(verticalPair, previter); |
| } |
| ActiveTail45::joinChains(point, tails[i], verticalPair.first, true, output); |
| verticalPair.second->pushPoint(point); |
| elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, j -1, incoming[j]), |
| verticalPair.second)); |
| } |
| tails[i] = 0; |
| counts[i] = 0; |
| incoming[j] = 0; |
| } |
| break; |
| } |
| } |
| } |
| break; |
| } |
| } |
| |
| //find the end of a hole or the beginning of a hole |
| |
| //find end of a hole |
| for(int i = 0; i < 3; ++i) { |
| if(counts[i] != 0) { |
| for(int j = i+1; j < 4; ++j) { |
| if(counts[j] != 0) { |
| //std::cout << "case5: " << i << " " << j << std::endl; |
| //we are ending a hole and may potentially close a figure and have to handle the hole |
| tails[i]->pushPoint(point); |
| verticalPairOut.first = tails[i]; |
| if(j == 3) { |
| verticalPairOut.second = tails[j]; |
| } else { |
| if(verticalPair.first == 0) { |
| getVerticalPair_(verticalPair, previter); |
| } |
| ActiveTail45::joinChains(point, tails[j], verticalPair.first, true, output); |
| verticalPairOut.second = verticalPair.second; |
| } |
| tails[i] = 0; |
| tails[j] = 0; |
| counts[i] = 0; |
| counts[j] = 0; |
| break; |
| } |
| } |
| break; |
| } |
| } |
| //find beginning of a hole |
| for(int i = 0; i < 3; ++i) { |
| if(incoming[i] != 0) { |
| for(int j = i+1; j < 4; ++j) { |
| if(incoming[j] != 0) { |
| //std::cout << "case6: " << i << " " << j << std::endl; |
| //we are beginning a empty space |
| if(verticalPair.first == 0) { |
| getVerticalPair_(verticalPair, previter); |
| } |
| verticalPair.second->pushPoint(point); |
| if(j == 3) { |
| returnValue = verticalPair.first; |
| returnCount = -1; |
| } else { |
| std::pair<ActiveTail45*, ActiveTail45*> tailPair = |
| ActiveTail45::createActiveTail45sAsPair(point, true, 0, false); |
| //std::cout << "new element " << j-1 << " " << incoming[j] << std::endl; |
| elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, j -1, incoming[j]), tailPair.second)); |
| verticalPairOut.second = tailPair.first; |
| verticalPairOut.first = verticalPair.first; |
| } |
| //std::cout << "new element " << i-1 << " " << incoming[i] << std::endl; |
| elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, i -1, incoming[i]), verticalPair.second)); |
| incoming[i] = 0; |
| incoming[j] = 0; |
| break; |
| } |
| } |
| break; |
| } |
| } |
| verticalPair = verticalPairOut; |
| //assert that verticalPair is either both null, or neither null |
| //assert that returnValue is null if verticalPair is not null |
| //assert that tails, counts and incoming are all null |
| return std::pair<int, ActiveTail45*>(returnCount, returnValue); |
| } |
| |
| template <class cT, class iT> |
| inline iT processEvent_(cT& output, iT inputBegin, iT inputEnd) { |
| //std::cout << "processEvent_\n"; |
| justBefore_ = true; |
| //collect up all elements from the tree that are at the y |
| //values of events in the input queue |
| //create vector of new elements to add into tree |
| ActiveTail45* verticalTail = 0; |
| std::pair<ActiveTail45*, ActiveTail45*> verticalPair; |
| verticalPair.first = 0; |
| verticalPair.second = 0; |
| int verticalCount = 0; |
| iT currentIter = inputBegin; |
| std::vector<iterator> elementIters; |
| std::vector<std::pair<Vertex45, ActiveTail45*> > elements; |
| while(currentIter != inputEnd && currentIter->pt.x() == x_) { |
| //std::cout << "loop\n"; |
| Unit currentY = (*currentIter).pt.y(); |
| iterator iter = lookUp_(currentY); |
| //int counts[4] = {0, 0, 0, 0}; |
| Vertex45Count counts; |
| ActiveTail45* tails[4] = {0, 0, 0, verticalTail}; |
| //std::cout << "finding elements in tree\n"; |
| iterator previter = iter; |
| if(previter != scanData_.end() && |
| previter->first.evalAtX(x_) >= currentY && |
| previter != scanData_.begin()) |
| --previter; |
| while(iter != scanData_.end() && |
| iter->first.evalAtX(x_) == currentY) { |
| //std::cout << "loop2\n"; |
| elementIters.push_back(iter); |
| int index = iter->first.rise + 1; |
| //std::cout << index << " " << iter->first.count << std::endl; |
| counts[index] = iter->first.count; |
| tails[index] = iter->second; |
| ++iter; |
| } |
| //int incoming[4] = {0, 0, 0, 0}; |
| Vertex45Count incoming; |
| //std::cout << "aggregating\n"; |
| do { |
| //std::cout << "loop3\n"; |
| Vertex45Compact currentVertex(*currentIter); |
| incoming += currentVertex.count; |
| ++currentIter; |
| } while(currentIter != inputEnd && currentIter->pt.y() == currentY && |
| currentIter->pt.x() == x_); |
| //now counts and tails have the data from the left and |
| //incoming has the data from the right at this point |
| //cancel out any end points |
| //std::cout << counts[0] << " "; |
| //std::cout << counts[1] << " "; |
| //std::cout << counts[2] << " "; |
| //std::cout << counts[3] << "\n"; |
| //std::cout << incoming[0] << " "; |
| //std::cout << incoming[1] << " "; |
| //std::cout << incoming[2] << " "; |
| //std::cout << incoming[3] << "\n"; |
| if(verticalTail) { |
| counts[3] = -verticalCount; |
| } |
| incoming[3] *= -1; |
| for(unsigned int i = 0; i < 4; ++i) incoming[i] += counts[i]; |
| //std::cout << "calling processPoint_\n"; |
| std::pair<int, ActiveTail45*> result = processPoint_(output, elements, verticalPair, previter, |
| Point(x_, currentY), counts, tails, incoming); |
| verticalCount = result.first; |
| verticalTail = result.second; |
| if(verticalPair.first != 0 && iter != scanData_.end() && |
| (currentIter == inputEnd || currentIter->pt.x() != x_ || |
| currentIter->pt.y() > (*iter).first.evalAtX(x_))) { |
| //splice vertical pair into edge above |
| ActiveTail45* tailabove = (*iter).second; |
| Point point(x_, (*iter).first.evalAtX(x_)); |
| verticalPair.second->pushPoint(point); |
| ActiveTail45::joinChains(point, tailabove, verticalPair.first, true, output); |
| (*iter).second = verticalPair.second; |
| verticalPair.first = 0; |
| verticalPair.second = 0; |
| } |
| } |
| //std::cout << "erasing\n"; |
| //erase all elements from the tree |
| for(typename std::vector<iterator>::iterator iter = elementIters.begin(); |
| iter != elementIters.end(); ++iter) { |
| //std::cout << "erasing loop\n"; |
| scanData_.erase(*iter); |
| } |
| //switch comparison tie breaking policy |
| justBefore_ = false; |
| //add new elements into tree |
| //std::cout << "inserting\n"; |
| for(typename std::vector<std::pair<Vertex45, ActiveTail45*> >::iterator iter = elements.begin(); |
| iter != elements.end(); ++iter) { |
| //std::cout << "inserting loop\n"; |
| scanData_.insert(scanData_.end(), *iter); |
| } |
| //std::cout << "end processEvent\n"; |
| return currentIter; |
| } |
| |
| inline iterator lookUp_(Unit y){ |
| //if just before then we need to look from 1 not -1 |
| return scanData_.lower_bound(Vertex45(Point(x_, y), -1+2*justBefore_, 0)); |
| } |
| |
| }; |
| |
| template <typename stream_type> |
| static inline bool testPolygon45TilingRect(stream_type& stdcout) { |
| stdcout << "testing polygon tiling\n"; |
| Polygon45Tiling pf; |
| std::vector<Polygon45> polys; |
| std::vector<Vertex45> data; |
| data.push_back(Vertex45(Point(0, 0), 0, 1)); |
| data.push_back(Vertex45(Point(0, 0), 2, 1)); |
| data.push_back(Vertex45(Point(0, 10), 2, -1)); |
| data.push_back(Vertex45(Point(0, 10), 0, -1)); |
| data.push_back(Vertex45(Point(10, 0), 0, -1)); |
| data.push_back(Vertex45(Point(10, 0), 2, -1)); |
| data.push_back(Vertex45(Point(10, 10), 2, 1)); |
| data.push_back(Vertex45(Point(10, 10), 0, 1)); |
| gtlsort(data.begin(), data.end()); |
| pf.scan(polys, data.begin(), data.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon tiling\n"; |
| return true; |
| } |
| |
| template <typename stream_type> |
| static inline bool testPolygon45TilingP1(stream_type& stdcout) { |
| stdcout << "testing polygon tiling\n"; |
| Polygon45Tiling pf; |
| std::vector<Polygon45> polys; |
| std::vector<Vertex45> data; |
| data.push_back(Vertex45(Point(0, 0), 1, 1)); |
| data.push_back(Vertex45(Point(0, 0), 2, 1)); |
| data.push_back(Vertex45(Point(0, 10), 2, -1)); |
| data.push_back(Vertex45(Point(0, 10), 1, -1)); |
| data.push_back(Vertex45(Point(10, 10), 1, -1)); |
| data.push_back(Vertex45(Point(10, 10), 2, -1)); |
| data.push_back(Vertex45(Point(10, 20), 2, 1)); |
| data.push_back(Vertex45(Point(10, 20), 1, 1)); |
| gtlsort(data.begin(), data.end()); |
| pf.scan(polys, data.begin(), data.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon tiling\n"; |
| return true; |
| } |
| |
| template <typename stream_type> |
| static inline bool testPolygon45TilingP2(stream_type& stdcout) { |
| stdcout << "testing polygon tiling\n"; |
| Polygon45Tiling pf; |
| std::vector<Polygon45> polys; |
| std::vector<Vertex45> data; |
| data.push_back(Vertex45(Point(0, 0), 0, 1)); |
| data.push_back(Vertex45(Point(0, 0), 1, -1)); |
| data.push_back(Vertex45(Point(10, 0), 0, -1)); |
| data.push_back(Vertex45(Point(10, 0), 1, 1)); |
| data.push_back(Vertex45(Point(10, 10), 1, 1)); |
| data.push_back(Vertex45(Point(10, 10), 0, -1)); |
| data.push_back(Vertex45(Point(20, 10), 1, -1)); |
| data.push_back(Vertex45(Point(20, 10), 0, 1)); |
| gtlsort(data.begin(), data.end()); |
| pf.scan(polys, data.begin(), data.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon tiling\n"; |
| return true; |
| } |
| |
| template <typename stream_type> |
| static inline bool testPolygon45TilingP3(stream_type& stdcout) { |
| stdcout << "testing polygon tiling\n"; |
| Polygon45Tiling pf; |
| std::vector<Polygon45> polys; |
| std::vector<Vertex45> data; |
| data.push_back(Vertex45(Point(0, 0), 0, 1)); |
| data.push_back(Vertex45(Point(0, 0), 2, 1)); |
| data.push_back(Vertex45(Point(0, 10), 2, -1)); |
| data.push_back(Vertex45(Point(0, 10), 0, -1)); |
| data.push_back(Vertex45(Point(20, 0), 0, -1)); |
| data.push_back(Vertex45(Point(20, 0), 2, -1)); |
| data.push_back(Vertex45(Point(10, 10), 1, -1)); |
| data.push_back(Vertex45(Point(10, 10), 0, 1)); |
| data.push_back(Vertex45(Point(20, 20), 1, 1)); |
| data.push_back(Vertex45(Point(20, 20), 2, 1)); |
| gtlsort(data.begin(), data.end()); |
| pf.scan(polys, data.begin(), data.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon tiling\n"; |
| return true; |
| } |
| |
| template <typename stream_type> |
| static inline bool testPolygon45TilingP4(stream_type& stdcout) { |
| stdcout << "testing polygon tiling p4\n"; |
| Polygon45Tiling pf; |
| std::vector<Polygon45> polys; |
| std::vector<Vertex45> data; |
| data.push_back(Vertex45(Point(0, 0), 0, 1)); |
| data.push_back(Vertex45(Point(0, 0), 2, 1)); |
| data.push_back(Vertex45(Point(0, 10), 2, -1)); |
| data.push_back(Vertex45(Point(0, 10), 0, -1)); |
| data.push_back(Vertex45(Point(10, 0), -1, 1)); |
| data.push_back(Vertex45(Point(10, 0), 0, -1)); |
| data.push_back(Vertex45(Point(20, 10), 2, 1)); |
| data.push_back(Vertex45(Point(20, 10), 0, 1)); |
| data.push_back(Vertex45(Point(20, -10), -1, -1)); |
| data.push_back(Vertex45(Point(20, -10), 2, -1)); |
| gtlsort(data.begin(), data.end()); |
| pf.scan(polys, data.begin(), data.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon tiling\n"; |
| return true; |
| } |
| |
| template <typename stream_type> |
| static inline bool testPolygon45TilingP5(stream_type& stdcout) { |
| stdcout << "testing polygon tiling P5\n"; |
| Polygon45Tiling pf; |
| std::vector<Polygon45> polys; |
| std::vector<Vertex45> data; |
| data.push_back(Vertex45(Point(0, 0), 0, 1)); |
| data.push_back(Vertex45(Point(0, 0), 2, 1)); |
| data.push_back(Vertex45(Point(0, 10), 2, -1)); |
| data.push_back(Vertex45(Point(0, 10), 0, -1)); |
| data.push_back(Vertex45(Point(10, 0), 0, -1)); |
| data.push_back(Vertex45(Point(10, 0), 2, -1)); |
| data.push_back(Vertex45(Point(10, 10), 2, 1)); |
| data.push_back(Vertex45(Point(10, 10), 0, 1)); |
| |
| data.push_back(Vertex45(Point(1, 1), 0, -1)); |
| data.push_back(Vertex45(Point(1, 1), 1, 1)); |
| data.push_back(Vertex45(Point(2, 1), 0, 1)); |
| data.push_back(Vertex45(Point(2, 1), 1, -1)); |
| data.push_back(Vertex45(Point(2, 2), 1, -1)); |
| data.push_back(Vertex45(Point(2, 2), 0, 1)); |
| data.push_back(Vertex45(Point(3, 2), 1, 1)); |
| data.push_back(Vertex45(Point(3, 2), 0, -1)); |
| gtlsort(data.begin(), data.end()); |
| pf.scan(polys, data.begin(), data.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon tiling\n"; |
| return true; |
| } |
| |
| template <typename stream_type> |
| static inline bool testPolygon45TilingP6(stream_type& stdcout) { |
| stdcout << "testing polygon tiling P6\n"; |
| Polygon45Tiling pf; |
| std::vector<Polygon45> polys; |
| std::vector<Vertex45> data; |
| data.push_back(Vertex45(Point(0, 0), 0, 1)); |
| data.push_back(Vertex45(Point(0, 0), 2, 1)); |
| data.push_back(Vertex45(Point(0, 10), 2, -1)); |
| data.push_back(Vertex45(Point(0, 10), 0, -1)); |
| data.push_back(Vertex45(Point(10, 0), 0, -1)); |
| data.push_back(Vertex45(Point(10, 0), 2, -1)); |
| data.push_back(Vertex45(Point(10, 10), 2, 1)); |
| data.push_back(Vertex45(Point(10, 10), 0, 1)); |
| |
| data.push_back(Vertex45(Point(1, 1), 0, -1)); |
| data.push_back(Vertex45(Point(1, 1), 2, -1)); |
| data.push_back(Vertex45(Point(1, 2), 2, 1)); |
| data.push_back(Vertex45(Point(1, 2), 0, 1)); |
| data.push_back(Vertex45(Point(2, 1), 0, 1)); |
| data.push_back(Vertex45(Point(2, 1), 2, 1)); |
| data.push_back(Vertex45(Point(2, 2), 2, -1)); |
| data.push_back(Vertex45(Point(2, 2), 0, -1)); |
| |
| gtlsort(data.begin(), data.end()); |
| pf.scan(polys, data.begin(), data.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon tiling\n"; |
| return true; |
| } |
| |
| template <typename stream_type> |
| static inline bool testPolygon45TilingStar1(stream_type& stdcout) { |
| stdcout << "testing polygon tiling star1\n"; |
| Polygon45Tiling pf; |
| std::vector<Polygon45> polys; |
| std::vector<Vertex45> data; |
| // result == 0 8 -1 1 |
| data.push_back(Vertex45(Point(0, 8), -1, 1)); |
| // result == 0 8 1 -1 |
| data.push_back(Vertex45(Point(0, 8), 1, -1)); |
| // result == 4 0 1 1 |
| data.push_back(Vertex45(Point(4, 0), 1, 1)); |
| // result == 4 0 2 1 |
| data.push_back(Vertex45(Point(4, 0), 2, 1)); |
| // result == 4 4 2 -1 |
| data.push_back(Vertex45(Point(4, 4), 2, -1)); |
| // result == 4 4 -1 -1 |
| data.push_back(Vertex45(Point(4, 4), -1, -1)); |
| // result == 4 12 1 1 |
| data.push_back(Vertex45(Point(4, 12), 1, 1)); |
| // result == 4 12 2 1 |
| data.push_back(Vertex45(Point(4, 12), 2, 1)); |
| // result == 4 16 2 -1 |
| data.push_back(Vertex45(Point(4, 16), 2, 1)); |
| // result == 4 16 -1 -1 |
| data.push_back(Vertex45(Point(4, 16), -1, -1)); |
| // result == 6 2 1 -1 |
| data.push_back(Vertex45(Point(6, 2), 1, -1)); |
| // result == 6 14 -1 1 |
| data.push_back(Vertex45(Point(6, 14), -1, 1)); |
| // result == 6 2 -1 1 |
| data.push_back(Vertex45(Point(6, 2), -1, 1)); |
| // result == 6 14 1 -1 |
| data.push_back(Vertex45(Point(6, 14), 1, -1)); |
| // result == 8 0 -1 -1 |
| data.push_back(Vertex45(Point(8, 0), -1, -1)); |
| // result == 8 0 2 -1 |
| data.push_back(Vertex45(Point(8, 0), 2, -1)); |
| // result == 8 4 2 1 |
| data.push_back(Vertex45(Point(8, 4), 2, 1)); |
| // result == 8 4 1 1 |
| data.push_back(Vertex45(Point(8, 4), 1, 1)); |
| // result == 8 12 -1 -1 |
| data.push_back(Vertex45(Point(8, 12), -1, -1)); |
| // result == 8 12 2 -1 |
| data.push_back(Vertex45(Point(8, 12), 2, -1)); |
| // result == 8 16 2 1 |
| data.push_back(Vertex45(Point(8, 16), 2, 1)); |
| // result == 8 16 1 1 |
| data.push_back(Vertex45(Point(8, 16), 1, 1)); |
| // result == 12 8 1 -1 |
| data.push_back(Vertex45(Point(12, 8), 1, -1)); |
| // result == 12 8 -1 1 |
| data.push_back(Vertex45(Point(12, 8), -1, 1)); |
| gtlsort(data.begin(), data.end()); |
| pf.scan(polys, data.begin(), data.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon tiling\n"; |
| return true; |
| } |
| |
| template <typename stream_type> |
| static inline bool testPolygon45TilingStar2(stream_type& stdcout) { |
| stdcout << "testing polygon tiling\n"; |
| Polygon45Tiling pf; |
| std::vector<Polygon45> polys; |
| |
| Scan45 scan45; |
| std::vector<Vertex45 > result; |
| std::vector<Scan45Vertex> vertices; |
| //is a Rectnagle(0, 0, 10, 10); |
| Count2 count(1, 0); |
| Count2 ncount(-1, 0); |
| vertices.push_back(Scan45Vertex(Point(0,4), Scan45Count(Count2(0, 0), count, ncount, Count2(0, 0)))); |
| vertices.push_back(Scan45Vertex(Point(16,4), Scan45Count(count, ncount, Count2(0, 0), Count2(0, 0)))); |
| vertices.push_back(Scan45Vertex(Point(8,12), Scan45Count(ncount, Count2(0, 0), count, Count2(0, 0)))); |
| count = Count2(0, 1); |
| ncount = count.invert(); |
| vertices.push_back(Scan45Vertex(Point(0,8), Scan45Count(count, ncount, Count2(0, 0), Count2(0, 0)))); |
| vertices.push_back(Scan45Vertex(Point(16,8), Scan45Count(Count2(0, 0), count, ncount, Count2(0, 0)))); |
| vertices.push_back(Scan45Vertex(Point(8,0), Scan45Count(ncount, Count2(0, 0), count, Count2(0, 0)))); |
| sortScan45Vector(vertices); |
| stdcout << "scanning\n"; |
| scan45.scan(result, vertices.begin(), vertices.end()); |
| |
| gtlsort(result.begin(), result.end()); |
| pf.scan(polys, result.begin(), result.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon tiling\n"; |
| return true; |
| } |
| |
| template <typename stream_type> |
| static inline bool testPolygon45TilingStarHole1(stream_type& stdcout) { |
| stdcout << "testing polygon tiling star hole 1\n"; |
| Polygon45Tiling pf; |
| std::vector<Polygon45> polys; |
| std::vector<Vertex45> data; |
| // result == 0 8 -1 1 |
| data.push_back(Vertex45(Point(0, 8), -1, 1)); |
| // result == 0 8 1 -1 |
| data.push_back(Vertex45(Point(0, 8), 1, -1)); |
| // result == 4 0 1 1 |
| data.push_back(Vertex45(Point(4, 0), 1, 1)); |
| // result == 4 0 2 1 |
| data.push_back(Vertex45(Point(4, 0), 2, 1)); |
| // result == 4 4 2 -1 |
| data.push_back(Vertex45(Point(4, 4), 2, -1)); |
| // result == 4 4 -1 -1 |
| data.push_back(Vertex45(Point(4, 4), -1, -1)); |
| // result == 4 12 1 1 |
| data.push_back(Vertex45(Point(4, 12), 1, 1)); |
| // result == 4 12 2 1 |
| data.push_back(Vertex45(Point(4, 12), 2, 1)); |
| // result == 4 16 2 -1 |
| data.push_back(Vertex45(Point(4, 16), 2, 1)); |
| // result == 4 16 -1 -1 |
| data.push_back(Vertex45(Point(4, 16), -1, -1)); |
| // result == 6 2 1 -1 |
| data.push_back(Vertex45(Point(6, 2), 1, -1)); |
| // result == 6 14 -1 1 |
| data.push_back(Vertex45(Point(6, 14), -1, 1)); |
| // result == 6 2 -1 1 |
| data.push_back(Vertex45(Point(6, 2), -1, 1)); |
| // result == 6 14 1 -1 |
| data.push_back(Vertex45(Point(6, 14), 1, -1)); |
| // result == 8 0 -1 -1 |
| data.push_back(Vertex45(Point(8, 0), -1, -1)); |
| // result == 8 0 2 -1 |
| data.push_back(Vertex45(Point(8, 0), 2, -1)); |
| // result == 8 4 2 1 |
| data.push_back(Vertex45(Point(8, 4), 2, 1)); |
| // result == 8 4 1 1 |
| data.push_back(Vertex45(Point(8, 4), 1, 1)); |
| // result == 8 12 -1 -1 |
| data.push_back(Vertex45(Point(8, 12), -1, -1)); |
| // result == 8 12 2 -1 |
| data.push_back(Vertex45(Point(8, 12), 2, -1)); |
| // result == 8 16 2 1 |
| data.push_back(Vertex45(Point(8, 16), 2, 1)); |
| // result == 8 16 1 1 |
| data.push_back(Vertex45(Point(8, 16), 1, 1)); |
| // result == 12 8 1 -1 |
| data.push_back(Vertex45(Point(12, 8), 1, -1)); |
| // result == 12 8 -1 1 |
| data.push_back(Vertex45(Point(12, 8), -1, 1)); |
| |
| data.push_back(Vertex45(Point(6, 4), 1, -1)); |
| data.push_back(Vertex45(Point(6, 4), 2, -1)); |
| data.push_back(Vertex45(Point(6, 8), -1, 1)); |
| data.push_back(Vertex45(Point(6, 8), 2, 1)); |
| data.push_back(Vertex45(Point(8, 6), -1, -1)); |
| data.push_back(Vertex45(Point(8, 6), 1, 1)); |
| |
| gtlsort(data.begin(), data.end()); |
| pf.scan(polys, data.begin(), data.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon tiling\n"; |
| return true; |
| } |
| |
| template <typename stream_type> |
| static inline bool testPolygon45TilingStarHole2(stream_type& stdcout) { |
| stdcout << "testing polygon tiling star hole 2\n"; |
| Polygon45Tiling pf; |
| std::vector<Polygon45WithHoles> polys; |
| std::vector<Vertex45> data; |
| // result == 0 8 -1 1 |
| data.push_back(Vertex45(Point(0, 8), -1, 1)); |
| // result == 0 8 1 -1 |
| data.push_back(Vertex45(Point(0, 8), 1, -1)); |
| // result == 4 0 1 1 |
| data.push_back(Vertex45(Point(4, 0), 1, 1)); |
| // result == 4 0 2 1 |
| data.push_back(Vertex45(Point(4, 0), 2, 1)); |
| // result == 4 4 2 -1 |
| data.push_back(Vertex45(Point(4, 4), 2, -1)); |
| // result == 4 4 -1 -1 |
| data.push_back(Vertex45(Point(4, 4), -1, -1)); |
| // result == 4 12 1 1 |
| data.push_back(Vertex45(Point(4, 12), 1, 1)); |
| // result == 4 12 2 1 |
| data.push_back(Vertex45(Point(4, 12), 2, 1)); |
| // result == 4 16 2 -1 |
| data.push_back(Vertex45(Point(4, 16), 2, 1)); |
| // result == 4 16 -1 -1 |
| data.push_back(Vertex45(Point(4, 16), -1, -1)); |
| // result == 6 2 1 -1 |
| data.push_back(Vertex45(Point(6, 2), 1, -1)); |
| // result == 6 14 -1 1 |
| data.push_back(Vertex45(Point(6, 14), -1, 1)); |
| // result == 6 2 -1 1 |
| data.push_back(Vertex45(Point(6, 2), -1, 1)); |
| // result == 6 14 1 -1 |
| data.push_back(Vertex45(Point(6, 14), 1, -1)); |
| // result == 8 0 -1 -1 |
| data.push_back(Vertex45(Point(8, 0), -1, -1)); |
| // result == 8 0 2 -1 |
| data.push_back(Vertex45(Point(8, 0), 2, -1)); |
| // result == 8 4 2 1 |
| data.push_back(Vertex45(Point(8, 4), 2, 1)); |
| // result == 8 4 1 1 |
| data.push_back(Vertex45(Point(8, 4), 1, 1)); |
| // result == 8 12 -1 -1 |
| data.push_back(Vertex45(Point(8, 12), -1, -1)); |
| // result == 8 12 2 -1 |
| data.push_back(Vertex45(Point(8, 12), 2, -1)); |
| // result == 8 16 2 1 |
| data.push_back(Vertex45(Point(8, 16), 2, 1)); |
| // result == 8 16 1 1 |
| data.push_back(Vertex45(Point(8, 16), 1, 1)); |
| // result == 12 8 1 -1 |
| data.push_back(Vertex45(Point(12, 8), 1, -1)); |
| // result == 12 8 -1 1 |
| data.push_back(Vertex45(Point(12, 8), -1, 1)); |
| |
| data.push_back(Vertex45(Point(6, 4), 1, -1)); |
| data.push_back(Vertex45(Point(6, 4), 2, -1)); |
| data.push_back(Vertex45(Point(6, 12), -1, 1)); |
| data.push_back(Vertex45(Point(6, 12), 2, 1)); |
| data.push_back(Vertex45(Point(10, 8), -1, -1)); |
| data.push_back(Vertex45(Point(10, 8), 1, 1)); |
| |
| gtlsort(data.begin(), data.end()); |
| pf.scan(polys, data.begin(), data.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon tiling\n"; |
| return true; |
| } |
| |
| template <typename stream_type> |
| static inline bool testPolygon45Tiling(stream_type& stdcout) { |
| stdcout << "testing polygon tiling\n"; |
| Polygon45Tiling pf; |
| std::vector<Polygon45WithHoles> polys; |
| std::vector<Vertex45> data; |
| |
| data.push_back(Vertex45(Point(0, 0), 0, 1)); |
| data.push_back(Vertex45(Point(0, 0), 2, 1)); |
| data.push_back(Vertex45(Point(0, 100), 2, -1)); |
| data.push_back(Vertex45(Point(0, 100), 0, -1)); |
| data.push_back(Vertex45(Point(100, 0), 0, -1)); |
| data.push_back(Vertex45(Point(100, 0), 2, -1)); |
| data.push_back(Vertex45(Point(100, 100), 2, 1)); |
| data.push_back(Vertex45(Point(100, 100), 0, 1)); |
| |
| data.push_back(Vertex45(Point(2, 2), 0, -1)); |
| data.push_back(Vertex45(Point(2, 2), 2, -1)); |
| data.push_back(Vertex45(Point(2, 10), 2, 1)); |
| data.push_back(Vertex45(Point(2, 10), 0, 1)); |
| data.push_back(Vertex45(Point(10, 2), 0, 1)); |
| data.push_back(Vertex45(Point(10, 2), 2, 1)); |
| data.push_back(Vertex45(Point(10, 10), 2, -1)); |
| data.push_back(Vertex45(Point(10, 10), 0, -1)); |
| |
| data.push_back(Vertex45(Point(2, 12), 0, -1)); |
| data.push_back(Vertex45(Point(2, 12), 2, -1)); |
| data.push_back(Vertex45(Point(2, 22), 2, 1)); |
| data.push_back(Vertex45(Point(2, 22), 0, 1)); |
| data.push_back(Vertex45(Point(10, 12), 0, 1)); |
| data.push_back(Vertex45(Point(10, 12), 2, 1)); |
| data.push_back(Vertex45(Point(10, 22), 2, -1)); |
| data.push_back(Vertex45(Point(10, 22), 0, -1)); |
| |
| gtlsort(data.begin(), data.end()); |
| pf.scan(polys, data.begin(), data.end()); |
| stdcout << "result size: " << polys.size() << std::endl; |
| for(std::size_t i = 0; i < polys.size(); ++i) { |
| stdcout << polys[i] << std::endl; |
| } |
| stdcout << "done testing polygon tiling\n"; |
| return true; |
| } |
| }; |
| |
| template <typename Unit> |
| class PolyLine45HoleData { |
| public: |
| typedef typename polygon_45_formation<Unit>::ActiveTail45 ActiveTail45; |
| typedef typename ActiveTail45::iterator iterator; |
| |
| typedef polygon_45_concept geometry_type; |
| typedef Unit coordinate_type; |
| typedef point_data<Unit> Point; |
| typedef Point point_type; |
| // typedef iterator_points_to_compact<iterator, Point> compact_iterator_type; |
| typedef iterator iterator_type; |
| typedef typename coordinate_traits<Unit>::area_type area_type; |
| |
| inline PolyLine45HoleData() : p_(0) {} |
| inline PolyLine45HoleData(ActiveTail45* p) : p_(p) {} |
| //use default copy and assign |
| inline iterator begin() const { return p_->getTail()->begin(); } |
| inline iterator end() const { return p_->getTail()->end(); } |
| inline std::size_t size() const { return 0; } |
| template<class iT> |
| inline PolyLine45HoleData& set(iT inputBegin, iT inputEnd) { |
| return *this; |
| } |
| private: |
| ActiveTail45* p_; |
| }; |
| |
| template <typename Unit> |
| class PolyLine45PolygonData { |
| public: |
| typedef typename polygon_45_formation<Unit>::ActiveTail45 ActiveTail45; |
| typedef typename ActiveTail45::iterator iterator; |
| typedef PolyLine45HoleData<Unit> holeType; |
| |
| typedef polygon_45_with_holes_concept geometry_type; |
| typedef Unit coordinate_type; |
| typedef point_data<Unit> Point; |
| typedef Point point_type; |
| // typedef iterator_points_to_compact<iterator, Point> compact_iterator_type; |
| typedef iterator iterator_type; |
| typedef holeType hole_type; |
| typedef typename coordinate_traits<Unit>::area_type area_type; |
| class iteratorHoles { |
| private: |
| typename ActiveTail45::iteratorHoles itr_; |
| public: |
| typedef PolyLine45HoleData<Unit> holeType; |
| typedef holeType value_type; |
| typedef std::forward_iterator_tag iterator_category; |
| typedef std::ptrdiff_t difference_type; |
| typedef const value_type* pointer; //immutable |
| typedef const value_type& reference; //immutable |
| inline iteratorHoles() : itr_() {} |
| inline iteratorHoles(typename ActiveTail45::iteratorHoles itr) : itr_(itr) {} |
| inline iteratorHoles(const iteratorHoles& that) : itr_(that.itr_) {} |
| inline iteratorHoles& operator=(const iteratorHoles& that) { |
| itr_ = that.itr_; |
| return *this; |
| } |
| inline bool operator==(const iteratorHoles& that) { return itr_ == that.itr_; } |
| inline bool operator!=(const iteratorHoles& that) { return itr_ != that.itr_; } |
| inline iteratorHoles& operator++() { |
| ++itr_; |
| return *this; |
| } |
| inline const iteratorHoles operator++(int) { |
| iteratorHoles tmp = *this; |
| ++(*this); |
| return tmp; |
| } |
| inline holeType operator*() { |
| return *itr_; |
| } |
| }; |
| typedef iteratorHoles iterator_holes_type; |
| |
| |
| inline PolyLine45PolygonData() : p_(0) {} |
| inline PolyLine45PolygonData(ActiveTail45* p) : p_(p) {} |
| //use default copy and assign |
| inline iterator begin() const { return p_->getTail()->begin(); } |
| inline iterator end() const { return p_->getTail()->end(); } |
| inline iteratorHoles begin_holes() const { return iteratorHoles(p_->getHoles().begin()); } |
| inline iteratorHoles end_holes() const { return iteratorHoles(p_->getHoles().end()); } |
| inline ActiveTail45* 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 PolyLine45PolygonData& set(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 PolyLine45PolygonData& set_holes(iT inputBegin, iT inputEnd) { |
| return *this; |
| } |
| private: |
| ActiveTail45* p_; |
| }; |
| |
| template <typename T> |
| struct PolyLineByConcept<T, polygon_45_with_holes_concept> { typedef PolyLine45PolygonData<T> type; }; |
| template <typename T> |
| struct PolyLineByConcept<T, polygon_with_holes_concept> { typedef PolyLine45PolygonData<T> type; }; |
| template <typename T> |
| struct PolyLineByConcept<T, polygon_45_concept> { typedef PolyLine45HoleData<T> type; }; |
| template <typename T> |
| struct PolyLineByConcept<T, polygon_concept> { typedef PolyLine45HoleData<T> type; }; |
| |
| template <typename T> |
| struct geometry_concept<PolyLine45PolygonData<T> > { typedef polygon_45_with_holes_concept type; }; |
| template <typename T> |
| struct geometry_concept<PolyLine45HoleData<T> > { typedef polygon_45_concept type; }; |
| |
| } |
| } |
| #endif |