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_BOOLEAN_OP_45_HPP
Chris@16: #define BOOST_POLYGON_BOOLEAN_OP_45_HPP
Chris@16: namespace boost { namespace polygon{
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   struct boolean_op_45 {
Chris@16:     typedef point_data<Unit> Point;
Chris@16:     typedef typename coordinate_traits<Unit>::manhattan_area_type LongUnit;
Chris@16: 
Chris@16:     class Count2 {
Chris@16:     public:
Chris@16:       inline Count2()
Chris@16: #ifndef BOOST_POLYGON_MSVC
Chris@16:       : counts()
Chris@16: #endif
Chris@16:       { counts[0] = counts[1] = 0; }
Chris@16:       //inline Count2(int count) { counts[0] = counts[1] = count; }
Chris@16:       inline Count2(int count1, int count2)
Chris@16: #ifndef BOOST_POLYGON_MSVC
Chris@16:       : counts()
Chris@16: #endif
Chris@16:       { counts[0] = count1; counts[1] = count2; }
Chris@16:       inline Count2(const Count2& count)
Chris@16: #ifndef BOOST_POLYGON_MSVC
Chris@16:       : counts()
Chris@16: #endif
Chris@16:       { counts[0] = count.counts[0]; counts[1] = count.counts[1]; }
Chris@16:       inline bool operator==(const Count2& count) const { return counts[0] == count.counts[0] && counts[1] == count.counts[1]; }
Chris@16:       inline bool operator!=(const Count2& count) const { return !((*this) == count); }
Chris@16:       inline Count2& operator=(int count) { counts[0] = counts[1] = count; return *this; }
Chris@16:       inline Count2& operator=(const Count2& count) { counts[0] = count.counts[0]; counts[1] = count.counts[1]; return *this; }
Chris@16:       inline int& operator[](bool index) { return counts[index]; }
Chris@16:       inline int operator[](bool index) const {return counts[index]; }
Chris@16:       inline Count2& operator+=(const Count2& count){
Chris@16:         counts[0] += count[0];
Chris@16:         counts[1] += count[1];
Chris@16:         return *this;
Chris@16:       }
Chris@16:       inline Count2& operator-=(const Count2& count){
Chris@16:         counts[0] -= count[0];
Chris@16:         counts[1] -= count[1];
Chris@16:         return *this;
Chris@16:       }
Chris@16:       inline Count2 operator+(const Count2& count) const {
Chris@16:         return Count2(*this)+=count;
Chris@16:       }
Chris@16:       inline Count2 operator-(const Count2& count) const {
Chris@16:         return Count2(*this)-=count;
Chris@16:       }
Chris@16:       inline Count2 invert() const {
Chris@16:         return Count2(-counts[0], -counts[1]);
Chris@16:       }
Chris@16:     private:
Chris@16:       int counts[2];
Chris@16:     };
Chris@16: 
Chris@16:     class Count1 {
Chris@16:     public:
Chris@16:       inline Count1() : count_(0) { }
Chris@16:       inline Count1(int count) : count_(count) { }
Chris@16:       inline Count1(const Count1& count) : count_(count.count_) { }
Chris@16:       inline bool operator==(const Count1& count) const { return count_ == count.count_; }
Chris@16:       inline bool operator!=(const Count1& count) const { return !((*this) == count); }
Chris@16:       inline Count1& operator=(int count) { count_ = count; return *this; }
Chris@16:       inline Count1& operator=(const Count1& count) { count_ = count.count_; return *this; }
Chris@16:       inline Count1& operator+=(const Count1& count){
Chris@16:         count_ += count.count_;
Chris@16:         return *this;
Chris@16:       }
Chris@16:       inline Count1& operator-=(const Count1& count){
Chris@16:         count_ -= count.count_;
Chris@16:         return *this;
Chris@16:       }
Chris@16:       inline Count1 operator+(const Count1& count) const {
Chris@16:         return Count1(*this)+=count;
Chris@16:       }
Chris@16:       inline Count1 operator-(const Count1& count) const {
Chris@16:         return Count1(*this)-=count;
Chris@16:       }
Chris@16:       inline Count1 invert() const {
Chris@16:         return Count1(-count_);
Chris@16:       }
Chris@16:       int count_;
Chris@16:     };
Chris@16: 
Chris@16:     //     inline std::ostream& operator<< (std::ostream& o, const Count2& c) {
Chris@16:     //       o << c[0] << " " << c[1];
Chris@16:     //       return o;
Chris@16:     //     }
Chris@16: 
Chris@16:     template <typename CountType>
Chris@16:     class Scan45ElementT {
Chris@16:     public:
Chris@16:       Unit x;
Chris@16:       Unit y;
Chris@16:       int rise; //-1, 0, +1
Chris@16:       mutable CountType count;
Chris@16:       inline Scan45ElementT() : x(), y(), rise(), count() {}
Chris@16:       inline Scan45ElementT(Unit xIn, Unit yIn, int riseIn, CountType countIn = CountType()) :
Chris@16:         x(xIn), y(yIn), rise(riseIn), count(countIn) {}
Chris@16:       inline Scan45ElementT(const Scan45ElementT& that) :
Chris@16:         x(that.x), y(that.y), rise(that.rise), count(that.count) {}
Chris@16:       inline Scan45ElementT& operator=(const Scan45ElementT& that) {
Chris@16:         x = that.x; y = that.y; rise = that.rise; count = that.count;
Chris@16:         return *this;
Chris@16:       }
Chris@16:       inline Unit evalAtX(Unit xIn) const {
Chris@16:         return y + rise * (xIn - x);
Chris@16:       }
Chris@16: 
Chris@16:       inline bool cross(Point& crossPoint, const Scan45ElementT& edge, Unit currentX) const {
Chris@16:         Unit y1 = evalAtX(currentX);
Chris@16:         Unit y2 = edge.evalAtX(currentX);
Chris@16:         int rise1 = rise;
Chris@16:         int rise2 = edge.rise;
Chris@16:         if(rise > edge.rise){
Chris@16:           if(y1 > y2) return false;
Chris@16:         } else if(rise < edge.rise){
Chris@16:           if(y2 > y1) return false;
Chris@16:           std::swap(y1, y2);
Chris@16:           std::swap(rise1, rise2);
Chris@16:         } else { return false; }
Chris@16:         if(rise1 == 1) {
Chris@16:           if(rise2 == 0) {
Chris@16:             crossPoint = Point(currentX + y2 - y1, y2);
Chris@16:           } else {
Chris@16:             //rise2 == -1
Chris@16:             Unit delta = (y2 - y1)/2;
Chris@16:             crossPoint = Point(currentX + delta, y1 + delta);
Chris@16:           }
Chris@16:         } else {
Chris@16:           //rise1 == 0 and rise2 == -1
Chris@16:           crossPoint = Point(currentX + y2 - y1, y1);
Chris@16:         }
Chris@16:         return true;
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     typedef Scan45ElementT<Count2> Scan45Element;
Chris@16: 
Chris@16:     //     inline std::ostream& operator<< (std::ostream& o, const Scan45Element& c) {
Chris@16:     //       o << c.x << " " << c.y << " " << c.rise << " " << c.count;
Chris@16:     //       return o;
Chris@16:     //     }
Chris@16: 
Chris@16:     class lessScan45ElementRise : public std::binary_function<Scan45Element, Scan45Element, bool> {
Chris@16:     public:
Chris@16:       inline lessScan45ElementRise() {} //default constructor is only constructor
Chris@16:       inline bool operator () (Scan45Element elm1, Scan45Element elm2) const {
Chris@16:         return elm1.rise < elm2.rise;
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     template <typename CountType>
Chris@16:     class lessScan45Element {
Chris@16:     private:
Chris@16:       Unit *x_; //x value at which to apply comparison
Chris@16:       int *justBefore_;
Chris@16:     public:
Chris@16:       inline lessScan45Element() : x_(0), justBefore_(0) {}
Chris@16:       inline lessScan45Element(Unit *x, int *justBefore) : x_(x), justBefore_(justBefore) {}
Chris@16:       inline lessScan45Element(const lessScan45Element& that) : x_(that.x_), justBefore_(that.justBefore_) {}
Chris@16:       inline lessScan45Element& operator=(const lessScan45Element& that) { x_ = that.x_; justBefore_ = that.justBefore_; return *this; }
Chris@16:       inline bool operator () (const Scan45ElementT<CountType>& elm1,
Chris@16:                                const Scan45ElementT<CountType>& elm2) const {
Chris@16:         Unit y1 = elm1.evalAtX(*x_);
Chris@16:         Unit y2 = elm2.evalAtX(*x_);
Chris@16:         if(y1 < y2) return true;
Chris@16:         if(y1 == y2) {
Chris@16:           //if justBefore is true we invert the result of the comparison of slopes
Chris@16:           if(*justBefore_) {
Chris@16:             return elm1.rise > elm2.rise;
Chris@16:           } else {
Chris@16:             return elm1.rise < elm2.rise;
Chris@16:           }
Chris@16:         }
Chris@16:         return false;
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     template <typename CountType>
Chris@16:     class Scan45CountT {
Chris@16:     public:
Chris@16:       inline Scan45CountT() : counts() {} //counts[0] = counts[1] = counts[2] = counts[3] = 0; }
Chris@16:       inline Scan45CountT(CountType count) : counts() { counts[0] = counts[1] = counts[2] = counts[3] = count; }
Chris@16:       inline Scan45CountT(const CountType& count1, const CountType& count2, const CountType& count3,
Chris@16:                           const CountType& count4) : counts() {
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 Scan45CountT(const Scan45CountT& count) : counts() {
Chris@16:         (*this) = count;
Chris@16:       }
Chris@16:       inline bool operator==(const Scan45CountT& 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 Scan45CountT& count) const { return !((*this) == count); }
Chris@16:       inline Scan45CountT& operator=(CountType count) {
Chris@16:         counts[0] = counts[1] = counts[2] = counts[3] = count; return *this; }
Chris@16:       inline Scan45CountT& operator=(const Scan45CountT& 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 CountType& operator[](int index) { return counts[index]; }
Chris@16:       inline CountType operator[](int index) const {return counts[index]; }
Chris@16:       inline Scan45CountT& operator+=(const Scan45CountT& 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 Scan45CountT& operator-=(const Scan45CountT& 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 Scan45CountT operator+(const Scan45CountT& count) const {
Chris@16:         return Scan45CountT(*this)+=count;
Chris@16:       }
Chris@16:       inline Scan45CountT operator-(const Scan45CountT& count) const {
Chris@16:         return Scan45CountT(*this)-=count;
Chris@16:       }
Chris@16:       inline Scan45CountT invert() const {
Chris@16:         return Scan45CountT(CountType())-=(*this);
Chris@16:       }
Chris@16:       inline Scan45CountT& operator+=(const Scan45ElementT<CountType>& element){
Chris@16:         counts[element.rise+1] += element.count; return *this;
Chris@16:       }
Chris@16:     private:
Chris@16:       CountType counts[4];
Chris@16:     };
Chris@16: 
Chris@16:     typedef Scan45CountT<Count2> Scan45Count;
Chris@16: 
Chris@16:     //     inline std::ostream& operator<< (std::ostream& o, const Scan45Count& 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: 
Chris@16:     //     inline std::ostream& operator<< (std::ostream& o, const Scan45Vertex& c) {
Chris@16:     //       o << c.first << ": " << c.second;
Chris@16:     //       return o;
Chris@16:     //     }
Chris@16: 
Chris@16: 
Chris@16:     //vetex45 is sortable
Chris@16:     template <typename ct>
Chris@16:     class Vertex45T {
Chris@16:     public:
Chris@16:       Point pt;
Chris@16:       int rise; // 1, 0 or -1
Chris@16:       ct count; //dxdydTheta
Chris@16:       inline Vertex45T() : pt(), rise(), count() {}
Chris@16:       inline Vertex45T(const Point& point, int riseIn, ct countIn) : pt(point), rise(riseIn), count(countIn) {}
Chris@16:       inline Vertex45T(const Vertex45T& vertex) : pt(vertex.pt), rise(vertex.rise), count(vertex.count) {}
Chris@16:       inline Vertex45T& operator=(const Vertex45T& vertex){
Chris@16:         pt = vertex.pt; rise = vertex.rise; count = vertex.count; return *this; }
Chris@16:       inline Vertex45T(const std::pair<Point, Point>& vertex) : pt(), rise(), count() {}
Chris@16:       inline Vertex45T& operator=(const std::pair<Point, Point>& vertex){ return *this; }
Chris@16:       inline bool operator==(const Vertex45T& vertex) const {
Chris@16:         return pt == vertex.pt && rise == vertex.rise && count == vertex.count; }
Chris@16:       inline bool operator!=(const Vertex45T& 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 Vertex45T& vertex) const {
Chris@16:         if(pt.x() < vertex.pt.x()) return true;
Chris@16:         if(pt.x() == vertex.pt.x()) {
Chris@16:           if(pt.y() < vertex.pt.y()) return true;
Chris@16:           if(pt.y() == vertex.pt.y()) { return rise < vertex.rise; }
Chris@16:         }
Chris@16:         return false;
Chris@16:       }
Chris@16:       inline bool operator>(const Vertex45T& vertex) const { return vertex < (*this); }
Chris@16:       inline bool operator<=(const Vertex45T& vertex) const { return !((*this) > vertex); }
Chris@16:       inline bool operator>=(const Vertex45T& vertex) const { return !((*this) < vertex); }
Chris@16:       inline Unit evalAtX(Unit xIn) const { return pt.y() + rise * (xIn - pt.x()); }
Chris@16:     };
Chris@16: 
Chris@16:     typedef Vertex45T<int> Vertex45;
Chris@16: 
Chris@16:     //     inline std::ostream& operator<< (std::ostream& o, const Vertex45& c) {
Chris@16:     //       o << c.pt << " " << c.rise << " " << c.count;
Chris@16:     //       return o;
Chris@16:     //     }
Chris@16: 
Chris@16:     //when scanning Vertex45 for polygon formation we need a scanline comparator functor
Chris@16:     class lessVertex45 {
Chris@16:     private:
Chris@16:       Unit *x_; //x value at which to apply comparison
Chris@16:       int *justBefore_;
Chris@16:     public:
Chris@16:       inline lessVertex45() : x_(0), justBefore_() {}
Chris@16: 
Chris@16:       inline lessVertex45(Unit *x, int *justBefore) : x_(x), justBefore_(justBefore) {}
Chris@16: 
Chris@16:       inline lessVertex45(const lessVertex45& that) : x_(that.x_), justBefore_(that.justBefore_) {}
Chris@16: 
Chris@16:       inline lessVertex45& operator=(const lessVertex45& that) { x_ = that.x_; justBefore_ = that.justBefore_; return *this; }
Chris@16: 
Chris@16:       template <typename ct>
Chris@16:       inline bool operator () (const Vertex45T<ct>& elm1, const Vertex45T<ct>& elm2) const {
Chris@16:         Unit y1 = elm1.evalAtX(*x_);
Chris@16:         Unit y2 = elm2.evalAtX(*x_);
Chris@16:         if(y1 < y2) return true;
Chris@16:         if(y1 == y2) {
Chris@16:           //if justBefore is true we invert the result of the comparison of slopes
Chris@16:           if(*justBefore_) {
Chris@16:             return elm1.rise > elm2.rise;
Chris@16:           } else {
Chris@16:             return elm1.rise < elm2.rise;
Chris@16:           }
Chris@16:         }
Chris@16:         return false;
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     // 0 right to left
Chris@16:     // 1 upper right to lower left
Chris@16:     // 2 high to low
Chris@16:     // 3 upper left to lower right
Chris@16:     // 4 left to right
Chris@16:     // 5 lower left to upper right
Chris@16:     // 6 low to high
Chris@16:     // 7 lower right to upper left
Chris@16:     static inline int classifyEdge45(const Point& prevPt, const Point& nextPt) {
Chris@16:       if(prevPt.x() == nextPt.x()) {
Chris@16:         //2 or 6
Chris@16:         return predicated_value(prevPt.y() < nextPt.y(), 6, 2);
Chris@16:       }
Chris@16:       if(prevPt.y() == nextPt.y()) {
Chris@16:         //0 or 4
Chris@16:         return predicated_value(prevPt.x() < nextPt.x(), 4, 0);
Chris@16:       }
Chris@16:       if(prevPt.x() < nextPt.x()) {
Chris@16:         //3 or 5
Chris@16:         return predicated_value(prevPt.y() < nextPt.y(), 5, 3);
Chris@16:       }
Chris@16:       //prevPt.x() > nextPt.y()
Chris@16:       //1 or 7
Chris@16:       return predicated_value(prevPt.y() < nextPt.y(), 7, 1);
Chris@16:     }
Chris@16: 
Chris@16:     template <int op, typename CountType>
Chris@16:     static int applyLogic(CountType count1, CountType count2){
Chris@16:       bool l1 = applyLogic<op>(count1);
Chris@16:       bool l2 = applyLogic<op>(count2);
Chris@16:       if(l1 && !l2)
Chris@16:         return -1; //was true before and became false like a trailing edge
Chris@16:       if(!l1 && l2)
Chris@16:         return 1; //was false before and became true like a leading edge
Chris@16:       return 0; //no change in logic between the two counts
Chris@16:     }
Chris@16:     template <int op>
Chris@16:     static bool applyLogic(Count2 count) {
Chris@16: #ifdef BOOST_POLYGON_MSVC
Chris@16: #pragma warning (push)
Chris@16: #pragma warning (disable: 4127)
Chris@16: #endif
Chris@16:       if(op == 0) { //apply or
Chris@16:         return count[0] > 0 || count[1] > 0;
Chris@16:       } else if(op == 1) { //apply and
Chris@16:         return count[0] > 0 && count[1] > 0;
Chris@16:       } else if(op == 2) { //apply not
Chris@16:         return count[0] > 0 && !(count[1] > 0);
Chris@16:       } else if(op == 3) { //apply xor
Chris@16:         return (count[0] > 0) ^ (count[1] > 0);
Chris@16:       } else
Chris@16:         return false;
Chris@16: #ifdef BOOST_POLYGON_MSVC
Chris@16: #pragma warning (pop)
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     template <int op>
Chris@16:     struct boolean_op_45_output_functor {
Chris@16:       template <typename cT>
Chris@16:       void operator()(cT& output, const Count2& count1, const Count2& count2,
Chris@16:                       const Point& pt, int rise, direction_1d end) {
Chris@16:         int edgeType = applyLogic<op>(count1, count2);
Chris@16:         if(edgeType) {
Chris@16:           int multiplier = end == LOW ? -1 : 1;
Chris@16:           //std::cout << "cross logic: " << edgeType << "\n";
Chris@16:           output.insert(output.end(), Vertex45(pt, rise, edgeType * multiplier));
Chris@16:           //std::cout << "write out: " << crossPoint << " " << Point(eraseItrs[i]->x, eraseItrs[i]->y) << "\n";
Chris@16:         }
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     template <int op>
Chris@16:     static bool applyLogic(Count1 count) {
Chris@16: #ifdef BOOST_POLYGON_MSVC
Chris@16: #pragma warning (push)
Chris@16: #pragma warning (disable: 4127)
Chris@16: #endif
Chris@16:       if(op == 0) { //apply or
Chris@16:         return count.count_ > 0;
Chris@16:       } else if(op == 1) { //apply and
Chris@16:         return count.count_ > 1;
Chris@16:       } else if(op == 3) { //apply xor
Chris@16:         return (count.count_ % 2) != 0;
Chris@16:       } else
Chris@16:         return false;
Chris@16: #ifdef BOOST_POLYGON_MSVC
Chris@16: #pragma warning (pop)
Chris@16: #endif
Chris@16:     }
Chris@16: 
Chris@16:     template <int op>
Chris@16:     struct unary_op_45_output_functor {
Chris@16:       template <typename cT>
Chris@16:       void operator()(cT& output, const Count1& count1, const Count1& count2,
Chris@16:                       const Point& pt, int rise, direction_1d end) {
Chris@16:         int edgeType = applyLogic<op>(count1, count2);
Chris@16:         if(edgeType) {
Chris@16:           int multiplier = end == LOW ? -1 : 1;
Chris@16:           //std::cout << "cross logic: " << edgeType << "\n";
Chris@16:           output.insert(output.end(), Vertex45(pt, rise, edgeType * multiplier));
Chris@16:           //std::cout << "write out: " << crossPoint << " " << Point(eraseItrs[i]->x, eraseItrs[i]->y) << "\n";
Chris@16:         }
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     class lessScan45Vertex {
Chris@16:     public:
Chris@16:       inline lessScan45Vertex() {} //default constructor is only constructor
Chris@16:       template <typename Scan45Vertex>
Chris@16:       inline bool operator () (const Scan45Vertex& v1, const Scan45Vertex& v2) const {
Chris@16:         return (v1.first.x() < v2.first.x()) || (v1.first.x() == v2.first.x() && v1.first.y() < v2.first.y());
Chris@16:       }
Chris@16:     };
Chris@16:     template <typename S45V>
Chris@16:     static inline void sortScan45Vector(S45V& vec) {
Chris@16:       polygon_sort(vec.begin(), vec.end(), lessScan45Vertex());
Chris@16:     }
Chris@16: 
Chris@16:     template <typename CountType, typename output_functor>
Chris@16:     class Scan45 {
Chris@16:     public:
Chris@16:       typedef Scan45CountT<CountType> Scan45Count;
Chris@16:       typedef std::pair<Point, Scan45Count> Scan45Vertex;
Chris@16: 
Chris@16:       //index is the index into the vertex
Chris@16:       static inline Scan45Element getElement(const Scan45Vertex& vertex, int index) {
Chris@16:         return Scan45Element(vertex.first.x(), vertex.first.y(), index - 1, vertex.second[index]);
Chris@16:       }
Chris@16: 
Chris@16:       class lessScan45Point : public std::binary_function<Point, Point, bool> {
Chris@16:       public:
Chris@16:         inline lessScan45Point() {} //default constructor is only constructor
Chris@16:         inline bool operator () (const Point& v1, const Point& v2) const {
Chris@16:           return (v1.x() < v2.x()) || (v1.x() == v2.x() && v1.y() < v2.y());
Chris@16:         }
Chris@16:       };
Chris@16: 
Chris@16:       typedef std::vector<Scan45Vertex> Scan45Vector;
Chris@16: 
Chris@16:       //definitions
Chris@16:       typedef std::set<Scan45ElementT<CountType>, lessScan45Element<CountType> > Scan45Data;
Chris@16:       typedef typename Scan45Data::iterator iterator;
Chris@16:       typedef typename Scan45Data::const_iterator const_iterator;
Chris@16:       typedef std::set<Point, lessScan45Point> CrossQueue;
Chris@16: 
Chris@16:       //data
Chris@16:       Scan45Data scanData_;
Chris@16:       CrossQueue crossQueue_;
Chris@16:       Scan45Vector crossVector_;
Chris@16:       Unit x_;
Chris@16:       int justBefore_;
Chris@16:     public:
Chris@16:       inline Scan45() : scanData_(), crossQueue_(), crossVector_(),
Chris@16:                         x_((std::numeric_limits<Unit>::min)()), justBefore_(false) {
Chris@16:         lessScan45Element<CountType>  lessElm(&x_, &justBefore_);
Chris@16:         scanData_ = std::set<Scan45ElementT<CountType>, lessScan45Element<CountType> >(lessElm);
Chris@16:       }
Chris@16:       inline Scan45(const Scan45& that) : scanData_(), crossQueue_(), crossVector_(),
Chris@16:                                           x_((std::numeric_limits<Unit>::min)()), justBefore_(false) {
Chris@16:         (*this) = that; }
Chris@16:       inline Scan45& operator=(const Scan45& that) {
Chris@16:         x_ = that.x_;
Chris@16:         justBefore_ = that.justBefore_;
Chris@16:         crossQueue_ = that.crossQueue_;
Chris@16:         crossVector_ = that.crossVector_;
Chris@16:         lessScan45Element<CountType>  lessElm(&x_, &justBefore_);
Chris@16:         scanData_ = std::set<Scan45ElementT<CountType>, lessScan45Element<CountType> >(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 Vertex45
Chris@16:       //iT is an iterator over Scan45Vertex elements
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:           //std::cout << "x_ = " << x_ << "\n";
Chris@16:           //std::cout << "scan line size: " << scanData_.size() << "\n";
Chris@16:           //for(iterator iter = scanData_.begin();
Chris@16:           //     iter != scanData_.end(); ++iter) {
Chris@16:           //   std::cout << "scan element\n";
Chris@16:           //   std::cout << *iter << " " << iter->evalAtX(x_) << "\n";
Chris@16:           // }
Chris@16:           // std::cout << "cross queue size: " << crossQueue_.size() << "\n";
Chris@16:           // std::cout << "cross vector size: " << crossVector_.size() << "\n";
Chris@16:           //for(CrossQueue::iterator cqitr = crossQueue_.begin(); cqitr != crossQueue_.end(); ++cqitr) {
Chris@16:           //   std::cout << *cqitr << " ";
Chris@16:           //} std::cout << "\n";
Chris@16:           Unit nextX = (*inputBegin).first.x();
Chris@16:           if(!crossVector_.empty() && crossVector_[0].first.x() < nextX) nextX = crossVector_[0].first.x();
Chris@16:           if(nextX != x_) {
Chris@16:             //std::cout << "3\n";
Chris@16:             //we need to move to the next scanline stop
Chris@16:             //we need to process end events then cross events
Chris@16:             //process end events
Chris@16:             if(!crossQueue_.empty() &&
Chris@16:                (*crossQueue_.begin()).x() < nextX) {
Chris@16:               //std::cout << "4\n";
Chris@16:               nextX = (std::min)(nextX, (*crossQueue_.begin()).x());
Chris@16:             }
Chris@16:             //std::cout << "6\n";
Chris@16:             justBefore_ = true;
Chris@16:             x_ = nextX;
Chris@16:             advance_(output);
Chris@16:             justBefore_ = false;
Chris@16:             if(!crossVector_.empty() &&
Chris@16:                nextX == (*inputBegin).first.x()) {
Chris@16:               inputBegin = mergeCross_(inputBegin, inputEnd);
Chris@16:             }
Chris@16:             processEvent_(output, crossVector_.begin(), crossVector_.end());
Chris@16:             crossVector_.clear();
Chris@16:           } else {
Chris@16:             //std::cout << "7\n";
Chris@16:             //our scanline has progressed to the event that is next in the queue
Chris@16:             inputBegin = processEvent_(output, inputBegin, inputEnd);
Chris@16:           }
Chris@16:         }
Chris@16:         //std::cout << "done scanning\n";
Chris@16:       }
Chris@16: 
Chris@16:     private:
Chris@16:       //functions
Chris@16: 
Chris@16:       template <class cT>
Chris@16:       inline void advance_(cT& output) {
Chris@16:         //process all cross points on the cross queue at the current x_
Chris@16:         //std::cout << "advance_\n";
Chris@16:         std::vector<iterator> eraseVec;
Chris@16:         while(!crossQueue_.empty() &&
Chris@16:               (*crossQueue_.begin()).x() == x_){
Chris@16:           //std::cout << "loop\n";
Chris@16:           //pop point off the cross queue
Chris@16:           Point crossPoint = *(crossQueue_.begin());
Chris@16:           //std::cout << crossPoint << "\n";
Chris@16:           //for(iterator iter = scanData_.begin();
Chris@16:           //    iter != scanData_.end(); ++iter) {
Chris@16:           //  std::cout << "scan element\n";
Chris@16:           //  std::cout << *iter << " " << iter->evalAtX(x_) << "\n";
Chris@16:           //}
Chris@16:           crossQueue_.erase(crossQueue_.begin());
Chris@16:           Scan45Vertex vertex(crossPoint, Scan45Count());
Chris@16:           iterator lowIter = lookUp_(vertex.first.y());
Chris@16:           //std::cout << "searching at: " << vertex.first.y() << "\n";
Chris@16:           //if(lowIter == scanData_.end()) std::cout << "could not find\n";
Chris@16:           //else std::cout << "found: " << *lowIter << "\n";
Chris@16:           if(lowIter == scanData_.end() ||
Chris@16:              lowIter->evalAtX(x_) != vertex.first.y()) {
Chris@16:             //   std::cout << "skipping\n";
Chris@16:             //there weren't any edges at this potential cross point
Chris@16:             continue;
Chris@16:           }
Chris@16:           CountType countBelow;
Chris@16:           iterator searchDownItr = lowIter;
Chris@16:           while(searchDownItr != scanData_.begin()
Chris@16:                 && searchDownItr->evalAtX(x_) == vertex.first.y()) {
Chris@16:             //get count from below
Chris@16:             --searchDownItr;
Chris@16:             countBelow = searchDownItr->count;
Chris@16:           }
Chris@16:           //std::cout << "Below Count: " << countBelow << "\n";
Chris@16:           Scan45Count count(countBelow);
Chris@16:           std::size_t numEdges = 0;
Chris@16:           iterator eraseItrs[3];
Chris@16:           while(lowIter != scanData_.end() &&
Chris@16:                 lowIter->evalAtX(x_) == vertex.first.y()) {
Chris@16:             for(int index = lowIter->rise +1; index >= 0; --index)
Chris@16:               count[index] = lowIter->count;
Chris@16:             //std::cout << count << "\n";
Chris@16:             eraseItrs[numEdges] = lowIter;
Chris@16:             ++numEdges;
Chris@16:             ++lowIter;
Chris@16:           }
Chris@16:           if(numEdges == 1) {
Chris@16:             //look for the next crossing point and continue
Chris@16:             //std::cout << "found only one edge\n";
Chris@16:             findCross_(eraseItrs[0]);
Chris@16:             continue;
Chris@16:           }
Chris@16:           //before we erase the elements we need to decide if they should be written out
Chris@16:           CountType currentCount = countBelow;
Chris@16:           for(std::size_t i = 0; i < numEdges; ++i) {
Chris@16:             output_functor f;
Chris@16:             f(output, currentCount, eraseItrs[i]->count, crossPoint, eraseItrs[i]->rise, LOW);
Chris@16:             currentCount = eraseItrs[i]->count;
Chris@16:           }
Chris@16:           //schedule erase of the elements
Chris@16:           for(std::size_t i = 0; i < numEdges; ++i) {
Chris@16:             eraseVec.push_back(eraseItrs[i]);
Chris@16:           }
Chris@16: 
Chris@16:           //take the derivative wrt theta of the count at the crossing point
Chris@16:           vertex.second[2] = count[2] - countBelow;
Chris@16:           vertex.second[1] = count[1] - count[2];
Chris@16:           vertex.second[0] = count[0] - count[1];
Chris@16:           //add the point, deriviative pair into the cross vector
Chris@16:           //std::cout << "LOOK HERE!\n";
Chris@16:           //std::cout << count << "\n";
Chris@16:           //std::cout << vertex << "\n";
Chris@16:           crossVector_.push_back(vertex);
Chris@16:         }
Chris@16:         //erase crossing elements
Chris@16:         std::vector<iterator> searchVec;
Chris@16:         for(std::size_t i = 0; i < eraseVec.size(); ++i) {
Chris@16:           if(eraseVec[i] != scanData_.begin()) {
Chris@16:             iterator searchItr = eraseVec[i];
Chris@16:             --searchItr;
Chris@16:             if(searchVec.empty() ||
Chris@16:                searchVec.back() != searchItr)
Chris@16:               searchVec.push_back(searchItr);
Chris@16:           }
Chris@16:           scanData_.erase(eraseVec[i]);
Chris@16:         }
Chris@16:         for(std::size_t i = 0; i < searchVec.size(); ++i) {
Chris@16:           findCross_(searchVec[i]);
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:       template <class iT>
Chris@16:       inline iT mergeCross_(iT inputBegin, iT inputEnd) {
Chris@16:         Scan45Vector vec;
Chris@16:         swap(vec, crossVector_);
Chris@16:         iT mergeEnd = inputBegin;
Chris@16:         std::size_t mergeCount = 0;
Chris@16:         while(mergeEnd != inputEnd &&
Chris@16:               (*mergeEnd).first.x() == x_) {
Chris@16:           ++mergeCount;
Chris@16:           ++mergeEnd;
Chris@16:         }
Chris@16:         crossVector_.reserve((std::max)(vec.capacity(), vec.size() + mergeCount));
Chris@16:         for(std::size_t i = 0; i < vec.size(); ++i){
Chris@16:           while(inputBegin != mergeEnd &&
Chris@16:                 (*inputBegin).first.y() < vec[i].first.y()) {
Chris@16:             crossVector_.push_back(*inputBegin);
Chris@16:             ++inputBegin;
Chris@16:           }
Chris@16:           crossVector_.push_back(vec[i]);
Chris@16:         }
Chris@16:         while(inputBegin != mergeEnd){
Chris@16:           crossVector_.push_back(*inputBegin);
Chris@16:           ++inputBegin;
Chris@16:         }
Chris@16:         return inputBegin;
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:         CountType verticalCount = CountType();
Chris@16:         Point prevPoint;
Chris@16:         iterator prevIter = scanData_.end();
Chris@16:         while(inputBegin != inputEnd &&
Chris@16:               (*inputBegin).first.x() == x_) {
Chris@16:           //std::cout << (*inputBegin) << "\n";
Chris@16:           //std::cout << "loop\n";
Chris@16:           Scan45Vertex vertex = *inputBegin;
Chris@16:           //std::cout << vertex.first << "\n";
Chris@16:           //if vertical count propigating up fake a null event at the next element
Chris@16:           if(verticalCount != CountType() && (prevIter != scanData_.end() &&
Chris@16:                                               prevIter->evalAtX(x_) < vertex.first.y())) {
Chris@16:             //std::cout << "faking null event\n";
Chris@16:             vertex = Scan45Vertex(Point(x_, prevIter->evalAtX(x_)), Scan45Count());
Chris@16:           } else {
Chris@16:             ++inputBegin;
Chris@16:             //std::cout << "after increment\n";
Chris@16:             //accumulate overlapping changes in Scan45Count
Chris@16:             while(inputBegin != inputEnd &&
Chris@16:                   (*inputBegin).first.x() == x_ &&
Chris@16:                   (*inputBegin).first.y() == vertex.first.y()) {
Chris@16:               //std::cout << "accumulate\n";
Chris@16:               vertex.second += (*inputBegin).second;
Chris@16:               ++inputBegin;
Chris@16:             }
Chris@16:           }
Chris@16:           //std::cout << vertex.second << "\n";
Chris@16:           //integrate vertex
Chris@16:           CountType currentCount = verticalCount;// + vertex.second[0];
Chris@16:           for(unsigned int i = 0; i < 3; ++i) {
Chris@16:             vertex.second[i] = currentCount += vertex.second[i];
Chris@16:           }
Chris@16:           //std::cout << vertex.second << "\n";
Chris@16:           //vertex represents the change in state at this point
Chris@16: 
Chris@16:           //get counts at current vertex
Chris@16:           CountType countBelow;
Chris@16:           iterator lowIter = lookUp_(vertex.first.y());
Chris@16:           if(lowIter != scanData_.begin()) {
Chris@16:             //get count from below
Chris@16:             --lowIter;
Chris@16:             countBelow = lowIter->count;
Chris@16:             ++lowIter;
Chris@16:           }
Chris@16:           //std::cout << "Count Below: " << countBelow[0] << " " << countBelow[1] << "\n";
Chris@16:           //std::cout << "vertical count: " << verticalCount[0] << " " << verticalCount[1] << "\n";
Chris@16:           Scan45Count countAt(countBelow - verticalCount);
Chris@16:           //check if the vertical edge should be written out
Chris@16:           if(verticalCount != CountType()) {
Chris@16:             output_functor f;
Chris@16:             f(output, countBelow - verticalCount, countBelow, prevPoint, 2, HIGH);
Chris@16:             f(output, countBelow - verticalCount, countBelow, vertex.first, 2, LOW);
Chris@16:           }
Chris@16:           currentCount = countBelow - verticalCount;
Chris@16:           while(lowIter != scanData_.end() &&
Chris@16:                 lowIter->evalAtX(x_) == vertex.first.y()) {
Chris@16:             for(unsigned int i = lowIter->rise + 1; i < 3; ++i) {
Chris@16:               countAt[i] = lowIter->count;
Chris@16:             }
Chris@16:             Point lp(lowIter->x, lowIter->y);
Chris@16:             if(lp != vertex.first) {
Chris@16:               output_functor f;
Chris@16:               f(output, currentCount, lowIter->count, vertex.first, lowIter->rise, LOW);
Chris@16:             }
Chris@16:             currentCount = lowIter->count;
Chris@16:             iterator nextIter = lowIter;
Chris@16:             ++nextIter;
Chris@16:             //std::cout << "erase\n";
Chris@16:             scanData_.erase(lowIter);
Chris@16:             if(nextIter != scanData_.end())
Chris@16:               findCross_(nextIter);
Chris@16:             lowIter = nextIter;
Chris@16:           }
Chris@16:           verticalCount += vertex.second[3];
Chris@16:           prevPoint = vertex.first;
Chris@16:           //std::cout << "new vertical count: " << verticalCount[0] << " " << verticalCount[1] << "\n";
Chris@16:           prevIter = lowIter;
Chris@16:           //count represents the current state at this point
Chris@16:           //std::cout << vertex.second << "\n";
Chris@16:           //std::cout << countAt << "\n";
Chris@16:           //std::cout << "ADD\n";
Chris@16:           vertex.second += countAt;
Chris@16:           //std::cout << vertex.second << "\n";
Chris@16: 
Chris@16:           //add elements to the scanline
Chris@16:           for(int i = 0; i < 3; ++i) {
Chris@16:             if(vertex.second[i] != countBelow) {
Chris@16:               //std::cout << "insert: " << vertex.first.x() << " " << vertex.first.y() << " " << i-1 <<
Chris@16:               //  " " << vertex.second[i][0] << " " << vertex.second[i][1] << "\n";
Chris@16:               iterator insertIter = scanData_.insert(scanData_.end(),
Chris@16:                                                      Scan45ElementT<CountType>(vertex.first.x(),
Chris@16:                                                                                vertex.first.y(),
Chris@16:                                                                                i - 1, vertex.second[i]));
Chris@16:               findCross_(insertIter);
Chris@16:               output_functor f;
Chris@16:               f(output, countBelow, vertex.second[i], vertex.first, i - 1, HIGH);
Chris@16:             }
Chris@16:             countBelow = vertex.second[i];
Chris@16:           }
Chris@16:         }
Chris@16:         //std::cout << "end processEvent\n";
Chris@16:         return inputBegin;
Chris@16:       }
Chris@16: 
Chris@16:       //iter1 is horizontal
Chris@16:       inline void scheduleCross0_(iterator iter1, iterator iter2) {
Chris@16:         //std::cout << "0, ";
Chris@16:         Unit y1 = iter1->evalAtX(x_);
Chris@16:         Unit y2 = iter2->evalAtX(x_);
Chris@16:         LongUnit delta = local_abs(LongUnit(y1) - LongUnit(y2));
Chris@16:         if(delta + static_cast<LongUnit>(x_) <= (std::numeric_limits<Unit>::max)())
Chris@16:           crossQueue_.insert(crossQueue_.end(), Point(x_ + static_cast<Unit>(delta), y1));
Chris@16:         //std::cout <<  Point(x_ + delta, y1);
Chris@16:       }
Chris@16: 
Chris@16:       //neither iter is horizontal
Chris@16:       inline void scheduleCross1_(iterator iter1, iterator iter2) {
Chris@16:         //std::cout << "1, ";
Chris@16:         Unit y1 = iter1->evalAtX(x_);
Chris@16:         Unit y2 = iter2->evalAtX(x_);
Chris@16:         //std::cout << y1 << " " << y2 << ": ";
Chris@16:         //note that half the delta cannot exceed the positive inter range
Chris@16:         LongUnit delta = y1;
Chris@16:         delta -= y2;
Chris@16:         Unit UnitMax = (std::numeric_limits<Unit>::max)();
Chris@16:         if((delta & 1) == 1) {
Chris@16:           //delta is odd, division by 2 will result in integer trunctaion
Chris@16:           if(delta == 1) {
Chris@16:             //the cross point is not on the integer grid and cannot be represented
Chris@16:             //we must throw an exception
Chris@16:             std::string msg = "GTL 45 Boolean error, precision insufficient to represent edge intersection coordinate value.";
Chris@16:             throw(msg);
Chris@16:           } else {
Chris@16:             //note that result of this subtraction is always positive because itr1 is above itr2 in scanline
Chris@16:             LongUnit halfDelta2 = (LongUnit)((((LongUnit)y1) - y2)/2);
Chris@16:             //note that halfDelta2 has been truncated
Chris@16:             if(halfDelta2 + x_ <= UnitMax && halfDelta2 + y2 <= UnitMax) {
Chris@16:               crossQueue_.insert(crossQueue_.end(), Point(x_+static_cast<Unit>(halfDelta2), y2+static_cast<Unit>(halfDelta2)));
Chris@16:               crossQueue_.insert(crossQueue_.end(), Point(x_+static_cast<Unit>(halfDelta2), y2+static_cast<Unit>(halfDelta2)+1));
Chris@16:             }
Chris@16:           }
Chris@16:         } else {
Chris@16:           LongUnit halfDelta = (LongUnit)((((LongUnit)y1) - y2)/2);
Chris@16:           if(halfDelta + x_ <= UnitMax && halfDelta + y2 <= UnitMax)
Chris@16:             crossQueue_.insert(crossQueue_.end(), Point(x_+static_cast<Unit>(halfDelta), y2+static_cast<Unit>(halfDelta)));
Chris@16:           //std::cout << Point(x_+halfDelta, y2+halfDelta);
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:       inline void findCross_(iterator iter) {
Chris@16:         //std::cout << "find cross ";
Chris@16:         iterator iteratorBelow = iter;
Chris@16:         iterator iteratorAbove = iter;
Chris@16:         if(iter != scanData_.begin() && iter->rise < 1) {
Chris@16:           --iteratorBelow;
Chris@16:           if(iter->rise == 0){
Chris@16:             if(iteratorBelow->rise == 1) {
Chris@16:               scheduleCross0_(iter, iteratorBelow);
Chris@16:             }
Chris@16:           } else {
Chris@16:             //iter->rise == -1
Chris@16:             if(iteratorBelow->rise == 1) {
Chris@16:               scheduleCross1_(iter, iteratorBelow);
Chris@16:             } else if(iteratorBelow->rise == 0) {
Chris@16:               scheduleCross0_(iteratorBelow, iter);
Chris@16:             }
Chris@16:           }
Chris@16:         }
Chris@16:         ++iteratorAbove;
Chris@16:         if(iteratorAbove != scanData_.end() && iter->rise > -1) {
Chris@16:           if(iter->rise == 0) {
Chris@16:             if(iteratorAbove->rise == -1) {
Chris@16:               scheduleCross0_(iter, iteratorAbove);
Chris@16:             }
Chris@16:           } else {
Chris@16:             //iter->rise == 1
Chris@16:             if(iteratorAbove->rise == -1) {
Chris@16:               scheduleCross1_(iteratorAbove, iter);
Chris@16:             } else if(iteratorAbove->rise == 0) {
Chris@16:               scheduleCross0_(iteratorAbove, iter);
Chris@16:             }
Chris@16:           }
Chris@16:         }
Chris@16:         //std::cout << "\n";
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(Scan45ElementT<CountType>(x_, y, -1+2*justBefore_));
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     //template <typename CountType>
Chris@16:     //static inline void print45Data(const std::set<Scan45ElementT<CountType>,
Chris@16:     //                               lessScan45Element<CountType> >& data) {
Chris@16:     //  typename std::set<Scan45ElementT<CountType>, lessScan45Element<CountType> >::const_iterator iter;
Chris@16:     //  for(iter = data.begin(); iter != data.end(); ++iter) {
Chris@16:     //    std::cout << iter->x << " " << iter->y << " " << iter->rise << "\n";
Chris@16:     //  }
Chris@16:     //}
Chris@16: 
Chris@16:     template <typename streamtype>
Chris@16:     static inline bool testScan45Data(streamtype& stdcout) {
Chris@16:       Unit x = 0;
Chris@16:       int justBefore = false;
Chris@16:       lessScan45Element<Count2> lessElm(&x, &justBefore);
Chris@16:       std::set<Scan45ElementT<Count2>, lessScan45Element<Count2> > testData(lessElm);
Chris@16:       //Unit size = testData.size();
Chris@16:       typedef std::set<Scan45ElementT<Count2>, lessScan45Element<Count2> > Scan45Data;
Chris@16:       typename Scan45Data::iterator itr10 = testData.insert(testData.end(), Scan45Element(0, 10, 1));
Chris@16:       typename Scan45Data::iterator itr20 = testData.insert(testData.end(), Scan45Element(0, 20, 1));
Chris@16:       typename Scan45Data::iterator itr30 = testData.insert(testData.end(), Scan45Element(0, 30, -1));
Chris@16:       typename Scan45Data::iterator itr40 = testData.insert(testData.end(), Scan45Element(0, 40, -1));
Chris@16:       typename Scan45Data::iterator itrA = testData.lower_bound(Scan45Element(0, 29, -1));
Chris@16:       typename Scan45Data::iterator itr1 = testData.lower_bound(Scan45Element(0, 10, -1));
Chris@16:       x = 4;
Chris@16:       //now at 14 24 26 36
Chris@16:       typename Scan45Data::iterator itrB = testData.lower_bound(Scan45Element(4, 29, -1));
Chris@16:       typename Scan45Data::iterator itr2 = testData.lower_bound(Scan45Element(4, 14, -1));
Chris@16:       if(itr1 != itr2) stdcout << "test1 failed\n";
Chris@16:       if(itrA == itrB) stdcout << "test2 failed\n";
Chris@16:       //remove crossing elements
Chris@16:       testData.erase(itr20);
Chris@16:       testData.erase(itr30);
Chris@16:       x = 5;
Chris@16:       itr20 = testData.insert(testData.end(), Scan45Element(0, 20, 1));
Chris@16:       itr30 = testData.insert(testData.end(), Scan45Element(0, 30, -1));
Chris@16:       //now at 15 25 25 35
Chris@16:       typename Scan45Data::iterator itr = testData.begin();
Chris@16:       if(itr != itr10) stdcout << "test3 failed\n";
Chris@16:       ++itr;
Chris@16:       if(itr != itr30) stdcout << "test4 failed\n";
Chris@16:       ++itr;
Chris@16:       if(itr != itr20) stdcout << "test5 failed\n";
Chris@16:       ++itr;
Chris@16:       if(itr != itr40) stdcout << "test6 failed\n";
Chris@16:       stdcout << "done testing Scan45Data\n";
Chris@16:       return true;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename stream_type>
Chris@16:     static inline bool testScan45Rect(stream_type& stdcout) {
Chris@16:       stdcout << "testing Scan45Rect\n";
Chris@16:       Scan45<Count2, boolean_op_45_output_functor<0> > scan45;
Chris@16:       std::vector<Vertex45 > result;
Chris@16:       typedef std::pair<Point, Scan45Count> Scan45Vertex;
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,0), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(0,10), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(10,0), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(10,10), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
Chris@16:       stdcout << "scanning\n";
Chris@16:       scan45.scan(result, vertices.begin(), vertices.end());
Chris@16:       stdcout << "done scanning\n";
Chris@16:       // result size == 8
Chris@16:       // result == 0 0 0 1
Chris@16:       // result == 0 0 2 1
Chris@16:       // result == 0 10 2 -1
Chris@16:       // result == 0 10 0 -1
Chris@16:       // result == 10 0 0 -1
Chris@16:       // result == 10 0 2 -1
Chris@16:       // result == 10 10 2 1
Chris@16:       // result == 10 10 0 1
Chris@16:       std::vector<Vertex45> reference;
Chris@16:       reference.push_back(Vertex45(Point(0, 0), 0, 1));
Chris@16:       reference.push_back(Vertex45(Point(0, 0), 2, 1));
Chris@16:       reference.push_back(Vertex45(Point(0, 10), 2, -1));
Chris@16:       reference.push_back(Vertex45(Point(0, 10), 0, -1));
Chris@16:       reference.push_back(Vertex45(Point(10, 0), 0, -1));
Chris@16:       reference.push_back(Vertex45(Point(10, 0), 2, -1));
Chris@16:       reference.push_back(Vertex45(Point(10, 10), 2, 1));
Chris@16:       reference.push_back(Vertex45(Point(10, 10), 0, 1));
Chris@16:       if(result != reference) {
Chris@16:         stdcout << "result size == " << result.size() << "\n";
Chris@16:         for(std::size_t i = 0; i < result.size(); ++i) {
Chris@16:           //std::cout << "result == " << result[i]<< "\n";
Chris@16:         }
Chris@16:         stdcout << "reference size == " << reference.size() << "\n";
Chris@16:         for(std::size_t i = 0; i < reference.size(); ++i) {
Chris@16:           //std::cout << "reference == " << reference[i]<< "\n";
Chris@16:         }
Chris@16:         return false;
Chris@16:       }
Chris@16:       stdcout << "done testing Scan45Rect\n";
Chris@16:       return true;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename stream_type>
Chris@16:     static inline bool testScan45P1(stream_type& stdcout) {
Chris@16:       stdcout << "testing Scan45P1\n";
Chris@16:       Scan45<Count2, boolean_op_45_output_functor<0> > scan45;
Chris@16:       std::vector<Vertex45 > result;
Chris@16:       typedef std::pair<Point, Scan45Count> Scan45Vertex;
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,0), Scan45Count(Count2(0, 0), Count2(0, 0), count, count)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(0,10), Scan45Count(Count2(0, 0), Count2(0, 0), ncount, ncount)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(10,10), Scan45Count(Count2(0, 0), Count2(0, 0), ncount, ncount)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(10,20), Scan45Count(Count2(0, 0), Count2(0, 0), count, count)));
Chris@16:       stdcout << "scanning\n";
Chris@16:       scan45.scan(result, vertices.begin(), vertices.end());
Chris@16:       stdcout << "done scanning\n";
Chris@16:       // result size == 8
Chris@16:       // result == 0 0 1 1
Chris@16:       // result == 0 0 2 1
Chris@16:       // result == 0 10 2 -1
Chris@16:       // result == 0 10 1 -1
Chris@16:       // result == 10 10 1 -1
Chris@16:       // result == 10 10 2 -1
Chris@16:       // result == 10 20 2 1
Chris@16:       // result == 10 20 1 1
Chris@16:       std::vector<Vertex45> reference;
Chris@16:       reference.push_back(Vertex45(Point(0, 0), 1, 1));
Chris@16:       reference.push_back(Vertex45(Point(0, 0), 2, 1));
Chris@16:       reference.push_back(Vertex45(Point(0, 10), 2, -1));
Chris@16:       reference.push_back(Vertex45(Point(0, 10), 1, -1));
Chris@16:       reference.push_back(Vertex45(Point(10, 10), 1, -1));
Chris@16:       reference.push_back(Vertex45(Point(10, 10), 2, -1));
Chris@16:       reference.push_back(Vertex45(Point(10, 20), 2, 1));
Chris@16:       reference.push_back(Vertex45(Point(10, 20), 1, 1));
Chris@16:       if(result != reference) {
Chris@16:         stdcout << "result size == " << result.size() << "\n";
Chris@16:         for(std::size_t i = 0; i < result.size(); ++i) {
Chris@16:           //std::cout << "result == " << result[i]<< "\n";
Chris@16:         }
Chris@16:         stdcout << "reference size == " << reference.size() << "\n";
Chris@16:         for(std::size_t i = 0; i < reference.size(); ++i) {
Chris@16:           //std::cout << "reference == " << reference[i]<< "\n";
Chris@16:         }
Chris@16:         return false;
Chris@16:       }
Chris@16:       stdcout << "done testing Scan45P1\n";
Chris@16:       return true;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename stream_type>
Chris@16:     static inline bool testScan45P2(stream_type& stdcout) {
Chris@16:       stdcout << "testing Scan45P2\n";
Chris@16:       Scan45<Count2, boolean_op_45_output_functor<0> > scan45;
Chris@16:       std::vector<Vertex45 > result;
Chris@16:       typedef std::pair<Point, Scan45Count> Scan45Vertex;
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,0), Scan45Count(Count2(0, 0), count, ncount, Count2(0, 0))));
Chris@16:       vertices.push_back(Scan45Vertex(Point(10,0), Scan45Count(Count2(0, 0), ncount, count, Count2(0, 0))));
Chris@16:       vertices.push_back(Scan45Vertex(Point(10,10), Scan45Count(Count2(0, 0), ncount, count, Count2(0, 0))));
Chris@16:       vertices.push_back(Scan45Vertex(Point(20,10), Scan45Count(Count2(0, 0), count, ncount, Count2(0, 0))));
Chris@16:       stdcout << "scanning\n";
Chris@16:       scan45.scan(result, vertices.begin(), vertices.end());
Chris@16:       stdcout << "done scanning\n";
Chris@16:       // result size == 8
Chris@16:       // result == 0 0 0 1
Chris@16:       // result == 0 0 1 -1
Chris@16:       // result == 10 0 0 -1
Chris@16:       // result == 10 0 1 1
Chris@16:       // result == 10 10 1 1
Chris@16:       // result == 10 10 0 -1
Chris@16:       // result == 20 10 1 -1
Chris@16:       // result == 20 10 0 1
Chris@16:       std::vector<Vertex45> reference;
Chris@16:       reference.push_back(Vertex45(Point(0, 0), 0, 1));
Chris@16:       reference.push_back(Vertex45(Point(0, 0), 1, -1));
Chris@16:       reference.push_back(Vertex45(Point(10, 0), 0, -1));
Chris@16:       reference.push_back(Vertex45(Point(10, 0), 1, 1));
Chris@16:       reference.push_back(Vertex45(Point(10, 10), 1, 1));
Chris@16:       reference.push_back(Vertex45(Point(10, 10), 0, -1));
Chris@16:       reference.push_back(Vertex45(Point(20, 10), 1, -1));
Chris@16:       reference.push_back(Vertex45(Point(20, 10), 0, 1));
Chris@16:       if(result != reference) {
Chris@16:         stdcout << "result size == " << result.size() << "\n";
Chris@16:         for(std::size_t i = 0; i < result.size(); ++i) {
Chris@16:           //stdcout << "result == " << result[i]<< "\n";
Chris@16:         }
Chris@16:         stdcout << "reference size == " << reference.size() << "\n";
Chris@16:         for(std::size_t i = 0; i < reference.size(); ++i) {
Chris@16:           //stdcout << "reference == " << reference[i]<< "\n";
Chris@16:         }
Chris@16:         return false;
Chris@16:       }
Chris@16:       stdcout << "done testing Scan45P2\n";
Chris@16:       return true;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename streamtype>
Chris@16:     static inline bool testScan45And(streamtype& stdcout) {
Chris@16:       stdcout << "testing Scan45And\n";
Chris@16:       Scan45<Count2, boolean_op_45_output_functor<1> > scan45;
Chris@16:       std::vector<Vertex45 > result;
Chris@16:       typedef std::pair<Point, Scan45Count> Scan45Vertex;
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,0), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(0,10), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(10,0), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(10,10), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
Chris@16:       count = Count2(0, 1);
Chris@16:       ncount = count.invert();
Chris@16:       vertices.push_back(Scan45Vertex(Point(2,2), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(2,12), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(12,2), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(12,12), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
Chris@16:       sortScan45Vector(vertices);
Chris@16:       stdcout << "scanning\n";
Chris@16:       scan45.scan(result, vertices.begin(), vertices.end());
Chris@16:       stdcout << "done scanning\n";
Chris@16:       //result size == 8
Chris@16:       //result == 2 2 0 1
Chris@16:       //result == 2 2 2 1
Chris@16:       //result == 2 10 2 -1
Chris@16:       //result == 2 10 0 -1
Chris@16:       //result == 10 2 0 -1
Chris@16:       //result == 10 2 2 -1
Chris@16:       //result == 10 10 2 1
Chris@16:       //result == 10 10 0 1
Chris@16:       std::vector<Vertex45> reference;
Chris@16:       reference.push_back(Vertex45(Point(2, 2), 0, 1));
Chris@16:       reference.push_back(Vertex45(Point(2, 2), 2, 1));
Chris@16:       reference.push_back(Vertex45(Point(2, 10), 2, -1));
Chris@16:       reference.push_back(Vertex45(Point(2, 10), 0, -1));
Chris@16:       reference.push_back(Vertex45(Point(10, 2), 0, -1));
Chris@16:       reference.push_back(Vertex45(Point(10, 2), 2, -1));
Chris@16:       reference.push_back(Vertex45(Point(10, 10), 2, 1));
Chris@16:       reference.push_back(Vertex45(Point(10, 10), 0, 1));
Chris@16:       if(result != reference) {
Chris@16:         stdcout << "result size == " << result.size() << "\n";
Chris@16:         for(std::size_t i = 0; i < result.size(); ++i) {
Chris@16:           //stdcout << "result == " << result[i]<< "\n";
Chris@16:         }
Chris@16:         stdcout << "reference size == " << reference.size() << "\n";
Chris@16:         for(std::size_t i = 0; i < reference.size(); ++i) {
Chris@16:           //stdcout << "reference == " << reference[i]<< "\n";
Chris@16:         }
Chris@16:         return false;
Chris@16:       }
Chris@16:       stdcout << "done testing Scan45And\n";
Chris@16:       return true;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename stream_type>
Chris@16:     static inline bool testScan45Star1(stream_type& stdcout) {
Chris@16:       stdcout << "testing Scan45Star1\n";
Chris@16:       Scan45<Count2, boolean_op_45_output_functor<0> > scan45;
Chris@16:       std::vector<Vertex45 > result;
Chris@16:       typedef std::pair<Point, Scan45Count> Scan45Vertex;
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,8), Scan45Count(count, Count2(0, 0), ncount, Count2(0, 0))));
Chris@16:       vertices.push_back(Scan45Vertex(Point(8,0), Scan45Count(ncount, Count2(0, 0), Count2(0, 0), ncount)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(8,16), Scan45Count(Count2(0, 0), Count2(0, 0), count, count)));
Chris@16:       count = Count2(0, 1);
Chris@16:       ncount = count.invert();
Chris@16:       vertices.push_back(Scan45Vertex(Point(12,8), Scan45Count(count, Count2(0, 0), ncount, Count2(0, 0))));
Chris@16:       vertices.push_back(Scan45Vertex(Point(4,0), Scan45Count(Count2(0, 0), Count2(0, 0), count, count)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(4,16), Scan45Count(ncount, Count2(0, 0), Count2(0, 0), ncount)));
Chris@16:       sortScan45Vector(vertices);
Chris@16:       stdcout << "scanning\n";
Chris@16:       scan45.scan(result, vertices.begin(), vertices.end());
Chris@16:       stdcout << "done scanning\n";
Chris@16:       // result size == 24
Chris@16:       // result == 0 8 -1 1
Chris@16:       // result == 0 8 1 -1
Chris@16:       // result == 4 0 1 1
Chris@16:       // result == 4 0 2 1
Chris@16:       // result == 4 4 2 -1
Chris@16:       // result == 4 4 -1 -1
Chris@16:       // result == 4 12 1 1
Chris@16:       // result == 4 12 2 1
Chris@16:       // result == 4 16 2 -1
Chris@16:       // result == 4 16 -1 -1
Chris@16:       // result == 6 2 1 -1
Chris@16:       // result == 6 14 -1 1
Chris@16:       // result == 6 2 -1 1
Chris@16:       // result == 6 14 1 -1
Chris@16:       // result == 8 0 -1 -1
Chris@16:       // result == 8 0 2 -1
Chris@16:       // result == 8 4 2 1
Chris@16:       // result == 8 4 1 1
Chris@16:       // result == 8 12 -1 -1
Chris@16:       // result == 8 12 2 -1
Chris@16:       // result == 8 16 2 1
Chris@16:       // result == 8 16 1 1
Chris@16:       // result == 12 8 1 -1
Chris@16:       // result == 12 8 -1 1
Chris@16:       if(result.size() != 24) {
Chris@16:         //stdcout << "result size == " << result.size() << "\n";
Chris@16:         //stdcout << "reference size == " << 24 << "\n";
Chris@16:         return false;
Chris@16:       }
Chris@16:       stdcout << "done testing Scan45Star1\n";
Chris@16:       return true;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename stream_type>
Chris@16:     static inline bool testScan45Star2(stream_type& stdcout) {
Chris@16:       stdcout << "testing Scan45Star2\n";
Chris@16:       Scan45<Count2, boolean_op_45_output_functor<0> > scan45;
Chris@16:       std::vector<Vertex45 > result;
Chris@16:       typedef std::pair<Point, Scan45Count> Scan45Vertex;
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:       stdcout << "done scanning\n";
Chris@16:       // result size == 24
Chris@16:       // result == 0 4 0 1
Chris@16:       // result == 0 4 1 -1
Chris@16:       // result == 0 8 -1 1
Chris@16:       // result == 0 8 0 -1
Chris@16:       // result == 2 6 1 1
Chris@16:       // result == 2 6 -1 -1
Chris@16:       // result == 4 4 0 -1
Chris@16:       // result == 4 8 0 1
Chris@16:       // result == 4 4 -1 1
Chris@16:       // result == 4 8 1 -1
Chris@16:       // result == 8 0 -1 -1
Chris@16:       // result == 8 0 1 1
Chris@16:       // result == 8 12 1 1
Chris@16:       // result == 8 12 -1 -1
Chris@16:       // result == 12 4 1 -1
Chris@16:       // result == 12 8 -1 1
Chris@16:       // result == 12 4 0 1
Chris@16:       // result == 12 8 0 -1
Chris@16:       // result == 14 6 -1 -1
Chris@16:       // result == 14 6 1 1
Chris@16:       // result == 16 4 0 -1
Chris@16:       // result == 16 4 -1 1
Chris@16:       // result == 16 8 1 -1
Chris@16:       // result == 16 8 0 1
Chris@16:       if(result.size() != 24) {
Chris@16:         //std::cout << "result size == " << result.size() << "\n";
Chris@16:         //std::cout << "reference size == " << 24 << "\n";
Chris@16:         return false;
Chris@16:       }
Chris@16:       stdcout << "done testing Scan45Star2\n";
Chris@16:       return true;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename stream_type>
Chris@16:     static inline bool testScan45Star3(stream_type& stdcout) {
Chris@16:       stdcout << "testing Scan45Star3\n";
Chris@16:       Scan45<Count2, boolean_op_45_output_functor<0> > scan45;
Chris@16:       std::vector<Vertex45 > result;
Chris@16:       typedef std::pair<Point, Scan45Count> Scan45Vertex;
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,8), Scan45Count(count, Count2(0, 0), ncount, Count2(0, 0))));
Chris@16:       vertices.push_back(Scan45Vertex(Point(8,0), Scan45Count(ncount, Count2(0, 0), Count2(0, 0), ncount)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(8,16), Scan45Count(Count2(0, 0), Count2(0, 0), count, count)));
Chris@16: 
Chris@16:       vertices.push_back(Scan45Vertex(Point(6,0), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(6,14), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(12,0), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(12,14), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
Chris@16:       count = Count2(0, 1);
Chris@16:       ncount = count.invert();
Chris@16:       vertices.push_back(Scan45Vertex(Point(12,8), Scan45Count(count, Count2(0, 0), ncount, Count2(0, 0))));
Chris@16:       vertices.push_back(Scan45Vertex(Point(4,0), Scan45Count(Count2(0, 0), Count2(0, 0), count, count)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(4,16), Scan45Count(ncount, Count2(0, 0), Count2(0, 0), ncount)));
Chris@16:       sortScan45Vector(vertices);
Chris@16:       stdcout << "scanning\n";
Chris@16:       scan45.scan(result, vertices.begin(), vertices.end());
Chris@16:       stdcout << "done scanning\n";
Chris@16:       // result size == 28
Chris@16:       // result == 0 8 -1 1
Chris@16:       // result == 0 8 1 -1
Chris@16:       // result == 4 0 1 1
Chris@16:       // result == 4 0 2 1
Chris@16:       // result == 4 4 2 -1
Chris@16:       // result == 4 4 -1 -1
Chris@16:       // result == 4 12 1 1
Chris@16:       // result == 4 12 2 1
Chris@16:       // result == 4 16 2 -1
Chris@16:       // result == 4 16 -1 -1
Chris@16:       // result == 6 2 1 -1
Chris@16:       // result == 6 14 -1 1
Chris@16:       // result == 6 0 0 1
Chris@16:       // result == 6 0 2 1
Chris@16:       // result == 6 2 2 -1
Chris@16:       // result == 6 14 1 -1
Chris@16:       // result == 8 0 0 -1
Chris@16:       // result == 8 0 0 1
Chris@16:       // result == 8 14 0 -1
Chris@16:       // result == 8 14 2 -1
Chris@16:       // result == 8 16 2 1
Chris@16:       // result == 8 16 1 1
Chris@16:       // result == 12 0 0 -1
Chris@16:       // result == 12 0 2 -1
Chris@16:       // result == 12 8 2 1
Chris@16:       // result == 12 8 2 -1
Chris@16:       // result == 12 14 2 1
Chris@16:       // result == 12 14 0 1
Chris@16:       if(result.size() != 28) {
Chris@16:         //std::cout << "result size == " << result.size() << "\n";
Chris@16:         //std::cout << "reference size == " << 28 << "\n";
Chris@16:         return false;
Chris@16:       }
Chris@16: 
Chris@16:       stdcout << "done testing Scan45Star3\n";
Chris@16:       return true;
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     template <typename stream_type>
Chris@16:     static inline bool testScan45Star4(stream_type& stdcout) {
Chris@16:       stdcout << "testing Scan45Star4\n";
Chris@16:       Scan45<Count2, boolean_op_45_output_functor<0> > scan45;
Chris@16:       std::vector<Vertex45 > result;
Chris@16:       typedef std::pair<Point, Scan45Count> Scan45Vertex;
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: 
Chris@16:       vertices.push_back(Scan45Vertex(Point(0,6), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(0,12), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(16,6), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
Chris@16:       vertices.push_back(Scan45Vertex(Point(16,12), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
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:       stdcout << "done scanning\n";
Chris@16:       // result size == 28
Chris@16:       // result == 0 4 0 1
Chris@16:       // result == 0 4 1 -1
Chris@16:       // result == 0 6 0 1
Chris@16:       // result == 0 6 2 1
Chris@16:       // result == 0 8 2 -1
Chris@16:       // result == 0 8 2 1
Chris@16:       // result == 0 12 2 -1
Chris@16:       // result == 0 12 0 -1
Chris@16:       // result == 2 6 1 1
Chris@16:       // result == 2 6 0 -1
Chris@16:       // result == 4 4 0 -1
Chris@16:       // result == 4 4 -1 1
Chris@16:       // result == 8 12 0 1
Chris@16:       // result == 8 0 -1 -1
Chris@16:       // result == 8 0 1 1
Chris@16:       // result == 8 12 0 -1
Chris@16:       // result == 12 4 1 -1
Chris@16:       // result == 12 4 0 1
Chris@16:       // result == 14 6 -1 -1
Chris@16:       // result == 14 6 0 1
Chris@16:       // result == 16 4 0 -1
Chris@16:       // result == 16 4 -1 1
Chris@16:       // result == 16 6 0 -1
Chris@16:       // result == 16 6 2 -1
Chris@16:       // result == 16 8 2 1
Chris@16:       // result == 16 8 2 -1
Chris@16:       // result == 16 12 2 1
Chris@16:       // result == 16 12 0 1
Chris@16:       if(result.size() != 28) {
Chris@16:         //stdcout << "result size == " << result.size() << "\n";
Chris@16:         //stdcout << "reference size == " << 28 << "\n";
Chris@16:         return false;
Chris@16:       }
Chris@16: 
Chris@16:       stdcout << "done testing Scan45Star4\n";
Chris@16:       return true;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename stream_type>
Chris@16:     static inline bool testScan45(stream_type& stdcout) {
Chris@16:       if(!testScan45Rect(stdcout)) return false;
Chris@16:       if(!testScan45P1(stdcout)) return false;
Chris@16:       if(!testScan45P2(stdcout)) return false;
Chris@16:       if(!testScan45And(stdcout)) return false;
Chris@16:       if(!testScan45Star1(stdcout)) return false;
Chris@16:       if(!testScan45Star2(stdcout)) return false;
Chris@16:       if(!testScan45Star3(stdcout)) return false;
Chris@16:       if(!testScan45Star4(stdcout)) return false;
Chris@16:       return true;
Chris@16:     }
Chris@16: 
Chris@16:   };
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: }
Chris@16: #endif