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