ceph/src/boost/libs/polygon/include/boost/polygon/detail/boolean_op_45.hpp

   1 /*
   2   Copyright 2008 Intel Corporation
   3
   4   Use, modification and distribution are subject to the Boost Software License,
   5   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6   http://www.boost.org/LICENSE_1_0.txt).
   7 */
   8 #ifndef BOOST_POLYGON_BOOLEAN_OP_45_HPP
   9 #define BOOST_POLYGON_BOOLEAN_OP_45_HPP
  10 namespace boost { namespace polygon{
  11
  12   template <typename Unit>
  13   struct boolean_op_45 {
  14     typedef point_data<Unit> Point;
  15     typedef typename coordinate_traits<Unit>::manhattan_area_type LongUnit;
  16
  17     class Count2 {
  18     public:
  19       inline Count2()
  20 #ifndef BOOST_POLYGON_MSVC
  21       : counts()
  22 #endif
  23       { counts[0] = counts[1] = 0; }
  24       //inline Count2(int count) { counts[0] = counts[1] = count; }
  25       inline Count2(int count1, int count2)
  26 #ifndef BOOST_POLYGON_MSVC
  27       : counts()
  28 #endif
  29       { counts[0] = count1; counts[1] = count2; }
  30       inline Count2(const Count2& count)
  31 #ifndef BOOST_POLYGON_MSVC
  32       : counts()
  33 #endif
  34       { counts[0] = count.counts[0]; counts[1] = count.counts[1]; }
  35       inline bool operator==(const Count2& count) const { return counts[0] == count.counts[0] && counts[1] == count.counts[1]; }
  36       inline bool operator!=(const Count2& count) const { return !((*this) == count); }
  37       inline Count2& operator=(int count) { counts[0] = counts[1] = count; return *this; }
  38       inline Count2& operator=(const Count2& count) { counts[0] = count.counts[0]; counts[1] = count.counts[1]; return *this; }
  39       inline int& operator[](bool index) { return counts[index]; }
  40       inline int operator[](bool index) const {return counts[index]; }
  41       inline Count2& operator+=(const Count2& count){
  42         counts[0] += count[0];
  43         counts[1] += count[1];
  44         return *this;
  45       }
  46       inline Count2& operator-=(const Count2& count){
  47         counts[0] -= count[0];
  48         counts[1] -= count[1];
  49         return *this;
  50       }
  51       inline Count2 operator+(const Count2& count) const {
  52         return Count2(*this)+=count;
  53       }
  54       inline Count2 operator-(const Count2& count) const {
  55         return Count2(*this)-=count;
  56       }
  57       inline Count2 invert() const {
  58         return Count2(-counts[0], -counts[1]);
  59       }
  60     private:
  61       int counts[2];
  62     };
  63
  64     class Count1 {
  65     public:
  66       inline Count1() : count_(0) { }
  67       inline Count1(int count) : count_(count) { }
  68       inline Count1(const Count1& count) : count_(count.count_) { }
  69       inline bool operator==(const Count1& count) const { return count_ == count.count_; }
  70       inline bool operator!=(const Count1& count) const { return !((*this) == count); }
  71       inline Count1& operator=(int count) { count_ = count; return *this; }
  72       inline Count1& operator=(const Count1& count) { count_ = count.count_; return *this; }
  73       inline Count1& operator+=(const Count1& count){
  74         count_ += count.count_;
  75         return *this;
  76       }
  77       inline Count1& operator-=(const Count1& count){
  78         count_ -= count.count_;
  79         return *this;
  80       }
  81       inline Count1 operator+(const Count1& count) const {
  82         return Count1(*this)+=count;
  83       }
  84       inline Count1 operator-(const Count1& count) const {
  85         return Count1(*this)-=count;
  86       }
  87       inline Count1 invert() const {
  88         return Count1(-count_);
  89       }
  90       int count_;
  91     };
  92
  93     //     inline std::ostream& operator<< (std::ostream& o, const Count2& c) {
  94     //       o << c[0] << " " << c[1];
  95     //       return o;
  96     //     }
  97
  98     template <typename CountType>
  99     class Scan45ElementT {
 100     public:
 101       Unit x;
 102       Unit y;
 103       int rise; //-1, 0, +1
 104       mutable CountType count;
 105       inline Scan45ElementT() : x(), y(), rise(), count() {}
 106       inline Scan45ElementT(Unit xIn, Unit yIn, int riseIn, CountType countIn = CountType()) :
 107         x(xIn), y(yIn), rise(riseIn), count(countIn) {}
 108       inline Scan45ElementT(const Scan45ElementT& that) :
 109         x(that.x), y(that.y), rise(that.rise), count(that.count) {}
 110       inline Scan45ElementT& operator=(const Scan45ElementT& that) {
 111         x = that.x; y = that.y; rise = that.rise; count = that.count;
 112         return *this;
 113       }
 114       inline Unit evalAtX(Unit xIn) const {
 115         return y + rise * (xIn - x);
 116       }
 117
 118       inline bool cross(Point& crossPoint, const Scan45ElementT& edge, Unit currentX) const {
 119         Unit y1 = evalAtX(currentX);
 120         Unit y2 = edge.evalAtX(currentX);
 121         int rise1 = rise;
 122         int rise2 = edge.rise;
 123         if(rise > edge.rise){
 124           if(y1 > y2) return false;
 125         } else if(rise < edge.rise){
 126           if(y2 > y1) return false;
 127           std::swap(y1, y2);
 128           std::swap(rise1, rise2);
 129         } else { return false; }
 130         if(rise1 == 1) {
 131           if(rise2 == 0) {
 132             crossPoint = Point(currentX + y2 - y1, y2);
 133           } else {
 134             //rise2 == -1
 135             Unit delta = (y2 - y1)/2;
 136             crossPoint = Point(currentX + delta, y1 + delta);
 137           }
 138         } else {
 139           //rise1 == 0 and rise2 == -1
 140           crossPoint = Point(currentX + y2 - y1, y1);
 141         }
 142         return true;
 143       }
 144     };
 145
 146     typedef Scan45ElementT<Count2> Scan45Element;
 147
 148     //     inline std::ostream& operator<< (std::ostream& o, const Scan45Element& c) {
 149     //       o << c.x << " " << c.y << " " << c.rise << " " << c.count;
 150     //       return o;
 151     //     }
 152
 153     class lessScan45ElementRise : public std::binary_function<Scan45Element, Scan45Element, bool> {
 154     public:
 155       inline lessScan45ElementRise() {} //default constructor is only constructor
 156       inline bool operator () (Scan45Element elm1, Scan45Element elm2) const {
 157         return elm1.rise < elm2.rise;
 158       }
 159     };
 160
 161     template <typename CountType>
 162     class lessScan45Element {
 163     private:
 164       Unit *x_; //x value at which to apply comparison
 165       int *justBefore_;
 166     public:
 167       inline lessScan45Element() : x_(0), justBefore_(0) {}
 168       inline lessScan45Element(Unit *x, int *justBefore) : x_(x), justBefore_(justBefore) {}
 169       inline lessScan45Element(const lessScan45Element& that) : x_(that.x_), justBefore_(that.justBefore_) {}
 170       inline lessScan45Element& operator=(const lessScan45Element& that) { x_ = that.x_; justBefore_ = that.justBefore_; return *this; }
 171       inline bool operator () (const Scan45ElementT<CountType>& elm1,
 172                                const Scan45ElementT<CountType>& elm2) const {
 173         Unit y1 = elm1.evalAtX(*x_);
 174         Unit y2 = elm2.evalAtX(*x_);
 175         if(y1 < y2) return true;
 176         if(y1 == y2) {
 177           //if justBefore is true we invert the result of the comparison of slopes
 178           if(*justBefore_) {
 179             return elm1.rise > elm2.rise;
 180           } else {
 181             return elm1.rise < elm2.rise;
 182           }
 183         }
 184         return false;
 185       }
 186     };
 187
 188     template <typename CountType>
 189     class Scan45CountT {
 190     public:
 191       inline Scan45CountT() : counts() {} //counts[0] = counts[1] = counts[2] = counts[3] = 0; }
 192       inline Scan45CountT(CountType count) : counts() { counts[0] = counts[1] = counts[2] = counts[3] = count; }
 193       inline Scan45CountT(const CountType& count1, const CountType& count2, const CountType& count3,
 194                           const CountType& count4) : counts() {
 195         counts[0] = count1;
 196         counts[1] = count2;
 197         counts[2] = count3;
 198         counts[3] = count4;
 199       }
 200       inline Scan45CountT(const Scan45CountT& count) : counts() {
 201         (*this) = count;
 202       }
 203       inline bool operator==(const Scan45CountT& count) const {
 204         for(unsigned int i = 0; i < 4; ++i) {
 205           if(counts[i] != count.counts[i]) return false;
 206         }
 207         return true;
 208       }
 209       inline bool operator!=(const Scan45CountT& count) const { return !((*this) == count); }
 210       inline Scan45CountT& operator=(CountType count) {
 211         counts[0] = counts[1] = counts[2] = counts[3] = count; return *this; }
 212       inline Scan45CountT& operator=(const Scan45CountT& count) {
 213         for(unsigned int i = 0; i < 4; ++i) {
 214           counts[i] = count.counts[i];
 215         }
 216         return *this;
 217       }
 218       inline CountType& operator[](int index) { return counts[index]; }
 219       inline CountType operator[](int index) const {return counts[index]; }
 220       inline Scan45CountT& operator+=(const Scan45CountT& count){
 221         for(unsigned int i = 0; i < 4; ++i) {
 222           counts[i] += count.counts[i];
 223         }
 224         return *this;
 225       }
 226       inline Scan45CountT& operator-=(const Scan45CountT& count){
 227         for(unsigned int i = 0; i < 4; ++i) {
 228           counts[i] -= count.counts[i];
 229         }
 230         return *this;
 231       }
 232       inline Scan45CountT operator+(const Scan45CountT& count) const {
 233         return Scan45CountT(*this)+=count;
 234       }
 235       inline Scan45CountT operator-(const Scan45CountT& count) const {
 236         return Scan45CountT(*this)-=count;
 237       }
 238       inline Scan45CountT invert() const {
 239         return Scan45CountT(CountType())-=(*this);
 240       }
 241       inline Scan45CountT& operator+=(const Scan45ElementT<CountType>& element){
 242         counts[element.rise+1] += element.count; return *this;
 243       }
 244     private:
 245       CountType counts[4];
 246     };
 247
 248     typedef Scan45CountT<Count2> Scan45Count;
 249
 250     //     inline std::ostream& operator<< (std::ostream& o, const Scan45Count& c) {
 251     //       o << c[0] << ", " << c[1] << ", ";
 252     //       o << c[2] << ", " << c[3];
 253     //       return o;
 254     //     }
 255
 256
 257     //     inline std::ostream& operator<< (std::ostream& o, const Scan45Vertex& c) {
 258     //       o << c.first << ": " << c.second;
 259     //       return o;
 260     //     }
 261
 262
 263     //vetex45 is sortable
 264     template <typename ct>
 265     class Vertex45T {
 266     public:
 267       Point pt;
 268       int rise; // 1, 0 or -1
 269       ct count; //dxdydTheta
 270       inline Vertex45T() : pt(), rise(), count() {}
 271       inline Vertex45T(const Point& point, int riseIn, ct countIn) : pt(point), rise(riseIn), count(countIn) {}
 272       inline Vertex45T(const Vertex45T& vertex) : pt(vertex.pt), rise(vertex.rise), count(vertex.count) {}
 273       inline Vertex45T& operator=(const Vertex45T& vertex){
 274         pt = vertex.pt; rise = vertex.rise; count = vertex.count; return *this; }
 275       inline bool operator==(const Vertex45T& vertex) const {
 276         return pt == vertex.pt && rise == vertex.rise && count == vertex.count; }
 277       inline bool operator!=(const Vertex45T& vertex) const { return !((*this) == vertex); }
 278       inline bool operator<(const Vertex45T& vertex) const {
 279         if(pt.x() < vertex.pt.x()) return true;
 280         if(pt.x() == vertex.pt.x()) {
 281           if(pt.y() < vertex.pt.y()) return true;
 282           if(pt.y() == vertex.pt.y()) { return rise < vertex.rise; }
 283         }
 284         return false;
 285       }
 286       inline bool operator>(const Vertex45T& vertex) const { return vertex < (*this); }
 287       inline bool operator<=(const Vertex45T& vertex) const { return !((*this) > vertex); }
 288       inline bool operator>=(const Vertex45T& vertex) const { return !((*this) < vertex); }
 289       inline Unit evalAtX(Unit xIn) const { return pt.y() + rise * (xIn - pt.x()); }
 290     };
 291
 292     typedef Vertex45T<int> Vertex45;
 293
 294     //     inline std::ostream& operator<< (std::ostream& o, const Vertex45& c) {
 295     //       o << c.pt << " " << c.rise << " " << c.count;
 296     //       return o;
 297     //     }
 298
 299     //when scanning Vertex45 for polygon formation we need a scanline comparator functor
 300     class lessVertex45 {
 301     private:
 302       Unit *x_; //x value at which to apply comparison
 303       int *justBefore_;
 304     public:
 305       inline lessVertex45() : x_(0), justBefore_() {}
 306
 307       inline lessVertex45(Unit *x, int *justBefore) : x_(x), justBefore_(justBefore) {}
 308
 309       inline lessVertex45(const lessVertex45& that) : x_(that.x_), justBefore_(that.justBefore_) {}
 310
 311       inline lessVertex45& operator=(const lessVertex45& that) { x_ = that.x_; justBefore_ = that.justBefore_; return *this; }
 312
 313       template <typename ct>
 314       inline bool operator () (const Vertex45T<ct>& elm1, const Vertex45T<ct>& elm2) const {
 315         Unit y1 = elm1.evalAtX(*x_);
 316         Unit y2 = elm2.evalAtX(*x_);
 317         if(y1 < y2) return true;
 318         if(y1 == y2) {
 319           //if justBefore is true we invert the result of the comparison of slopes
 320           if(*justBefore_) {
 321             return elm1.rise > elm2.rise;
 322           } else {
 323             return elm1.rise < elm2.rise;
 324           }
 325         }
 326         return false;
 327       }
 328     };
 329
 330     // 0 right to left
 331     // 1 upper right to lower left
 332     // 2 high to low
 333     // 3 upper left to lower right
 334     // 4 left to right
 335     // 5 lower left to upper right
 336     // 6 low to high
 337     // 7 lower right to upper left
 338     static inline int classifyEdge45(const Point& prevPt, const Point& nextPt) {
 339       if(prevPt.x() == nextPt.x()) {
 340         //2 or 6
 341         return predicated_value(prevPt.y() < nextPt.y(), 6, 2);
 342       }
 343       if(prevPt.y() == nextPt.y()) {
 344         //0 or 4
 345         return predicated_value(prevPt.x() < nextPt.x(), 4, 0);
 346       }
 347       if(prevPt.x() < nextPt.x()) {
 348         //3 or 5
 349         return predicated_value(prevPt.y() < nextPt.y(), 5, 3);
 350       }
 351       //prevPt.x() > nextPt.y()
 352       //1 or 7
 353       return predicated_value(prevPt.y() < nextPt.y(), 7, 1);
 354     }
 355
 356     template <int op, typename CountType>
 357     static int applyLogic(CountType count1, CountType count2){
 358       bool l1 = applyLogic<op>(count1);
 359       bool l2 = applyLogic<op>(count2);
 360       if(l1 && !l2)
 361         return -1; //was true before and became false like a trailing edge
 362       if(!l1 && l2)
 363         return 1; //was false before and became true like a leading edge
 364       return 0; //no change in logic between the two counts
 365     }
 366     template <int op>
 367     static bool applyLogic(Count2 count) {
 368 #ifdef BOOST_POLYGON_MSVC
 369 #pragma warning (push)
 370 #pragma warning (disable: 4127)
 371 #endif
 372       if(op == 0) { //apply or
 373         return count[0] > 0 || count[1] > 0;
 374       } else if(op == 1) { //apply and
 375         return count[0] > 0 && count[1] > 0;
 376       } else if(op == 2) { //apply not
 377         return count[0] > 0 && !(count[1] > 0);
 378       } else if(op == 3) { //apply xor
 379         return (count[0] > 0) ^ (count[1] > 0);
 380       } else
 381         return false;
 382 #ifdef BOOST_POLYGON_MSVC
 383 #pragma warning (pop)
 384 #endif
 385     }
 386
 387     template <int op>
 388     struct boolean_op_45_output_functor {
 389       template <typename cT>
 390       void operator()(cT& output, const Count2& count1, const Count2& count2,
 391                       const Point& pt, int rise, direction_1d end) {
 392         int edgeType = applyLogic<op>(count1, count2);
 393         if(edgeType) {
 394           int multiplier = end == LOW ? -1 : 1;
 395           //std::cout << "cross logic: " << edgeType << "\n";
 396           output.insert(output.end(), Vertex45(pt, rise, edgeType * multiplier));
 397           //std::cout << "write out: " << crossPoint << " " << Point(eraseItrs[i]->x, eraseItrs[i]->y) << "\n";
 398         }
 399       }
 400     };
 401
 402     template <int op>
 403     static bool applyLogic(Count1 count) {
 404 #ifdef BOOST_POLYGON_MSVC
 405 #pragma warning (push)
 406 #pragma warning (disable: 4127)
 407 #endif
 408       if(op == 0) { //apply or
 409         return count.count_ > 0;
 410       } else if(op == 1) { //apply and
 411         return count.count_ > 1;
 412       } else if(op == 3) { //apply xor
 413         return (count.count_ % 2) != 0;
 414       } else
 415         return false;
 416 #ifdef BOOST_POLYGON_MSVC
 417 #pragma warning (pop)
 418 #endif
 419     }
 420
 421     template <int op>
 422     struct unary_op_45_output_functor {
 423       template <typename cT>
 424       void operator()(cT& output, const Count1& count1, const Count1& count2,
 425                       const Point& pt, int rise, direction_1d end) {
 426         int edgeType = applyLogic<op>(count1, count2);
 427         if(edgeType) {
 428           int multiplier = end == LOW ? -1 : 1;
 429           //std::cout << "cross logic: " << edgeType << "\n";
 430           output.insert(output.end(), Vertex45(pt, rise, edgeType * multiplier));
 431           //std::cout << "write out: " << crossPoint << " " << Point(eraseItrs[i]->x, eraseItrs[i]->y) << "\n";
 432         }
 433       }
 434     };
 435
 436     class lessScan45Vertex {
 437     public:
 438       inline lessScan45Vertex() {} //default constructor is only constructor
 439       template <typename Scan45Vertex>
 440       inline bool operator () (const Scan45Vertex& v1, const Scan45Vertex& v2) const {
 441         return (v1.first.x() < v2.first.x()) || (v1.first.x() == v2.first.x() && v1.first.y() < v2.first.y());
 442       }
 443     };
 444     template <typename S45V>
 445     static inline void sortScan45Vector(S45V& vec) {
 446       polygon_sort(vec.begin(), vec.end(), lessScan45Vertex());
 447     }
 448
 449     template <typename CountType, typename output_functor>
 450     class Scan45 {
 451     public:
 452       typedef Scan45CountT<CountType> Scan45Count;
 453       typedef std::pair<Point, Scan45Count> Scan45Vertex;
 454
 455       //index is the index into the vertex
 456       static inline Scan45Element getElement(const Scan45Vertex& vertex, int index) {
 457         return Scan45Element(vertex.first.x(), vertex.first.y(), index - 1, vertex.second[index]);
 458       }
 459
 460       class lessScan45Point : public std::binary_function<Point, Point, bool> {
 461       public:
 462         inline lessScan45Point() {} //default constructor is only constructor
 463         inline bool operator () (const Point& v1, const Point& v2) const {
 464           return (v1.x() < v2.x()) || (v1.x() == v2.x() && v1.y() < v2.y());
 465         }
 466       };
 467
 468       typedef std::vector<Scan45Vertex> Scan45Vector;
 469
 470       //definitions
 471       typedef std::set<Scan45ElementT<CountType>, lessScan45Element<CountType> > Scan45Data;
 472       typedef typename Scan45Data::iterator iterator;
 473       typedef typename Scan45Data::const_iterator const_iterator;
 474       typedef std::set<Point, lessScan45Point> CrossQueue;
 475
 476       //data
 477       Scan45Data scanData_;
 478       CrossQueue crossQueue_;
 479       Scan45Vector crossVector_;
 480       Unit x_;
 481       int justBefore_;
 482     public:
 483       inline Scan45() : scanData_(), crossQueue_(), crossVector_(),
 484                         x_((std::numeric_limits<Unit>::min)()), justBefore_(false) {
 485         lessScan45Element<CountType>  lessElm(&x_, &justBefore_);
 486         scanData_ = std::set<Scan45ElementT<CountType>, lessScan45Element<CountType> >(lessElm);
 487       }
 488       inline Scan45(const Scan45& that) : scanData_(), crossQueue_(), crossVector_(),
 489                                           x_((std::numeric_limits<Unit>::min)()), justBefore_(false) {
 490         (*this) = that; }
 491       inline Scan45& operator=(const Scan45& that) {
 492         x_ = that.x_;
 493         justBefore_ = that.justBefore_;
 494         crossQueue_ = that.crossQueue_;
 495         crossVector_ = that.crossVector_;
 496         lessScan45Element<CountType>  lessElm(&x_, &justBefore_);
 497         scanData_ = std::set<Scan45ElementT<CountType>, lessScan45Element<CountType> >(lessElm);
 498         for(const_iterator itr = that.scanData_.begin(); itr != that.scanData_.end(); ++itr){
 499           scanData_.insert(scanData_.end(), *itr);
 500         }
 501         return *this;
 502       }
 503
 504       //cT is an output container of Vertex45
 505       //iT is an iterator over Scan45Vertex elements
 506       template <class cT, class iT>
 507       void scan(cT& output, iT inputBegin, iT inputEnd) {
 508         //std::cout << "1\n";
 509         while(inputBegin != inputEnd) {
 510           //std::cout << "2\n";
 511           //std::cout << "x_ = " << x_ << "\n";
 512           //std::cout << "scan line size: " << scanData_.size() << "\n";
 513           //for(iterator iter = scanData_.begin();
 514           //     iter != scanData_.end(); ++iter) {
 515           //   std::cout << "scan element\n";
 516           //   std::cout << *iter << " " << iter->evalAtX(x_) << "\n";
 517           // }
 518           // std::cout << "cross queue size: " << crossQueue_.size() << "\n";
 519           // std::cout << "cross vector size: " << crossVector_.size() << "\n";
 520           //for(CrossQueue::iterator cqitr = crossQueue_.begin(); cqitr != crossQueue_.end(); ++cqitr) {
 521           //   std::cout << *cqitr << " ";
 522           //} std::cout << "\n";
 523           Unit nextX = (*inputBegin).first.x();
 524           if(!crossVector_.empty() && crossVector_[0].first.x() < nextX) nextX = crossVector_[0].first.x();
 525           if(nextX != x_) {
 526             //std::cout << "3\n";
 527             //we need to move to the next scanline stop
 528             //we need to process end events then cross events
 529             //process end events
 530             if(!crossQueue_.empty() &&
 531                (*crossQueue_.begin()).x() < nextX) {
 532               //std::cout << "4\n";
 533               nextX = (std::min)(nextX, (*crossQueue_.begin()).x());
 534             }
 535             //std::cout << "6\n";
 536             justBefore_ = true;
 537             x_ = nextX;
 538             advance_(output);
 539             justBefore_ = false;
 540             if(!crossVector_.empty() &&
 541                nextX == (*inputBegin).first.x()) {
 542               inputBegin = mergeCross_(inputBegin, inputEnd);
 543             }
 544             processEvent_(output, crossVector_.begin(), crossVector_.end());
 545             crossVector_.clear();
 546           } else {
 547             //std::cout << "7\n";
 548             //our scanline has progressed to the event that is next in the queue
 549             inputBegin = processEvent_(output, inputBegin, inputEnd);
 550           }
 551         }
 552         //std::cout << "done scanning\n";
 553       }
 554
 555     private:
 556       //functions
 557
 558       template <class cT>
 559       inline void advance_(cT& output) {
 560         //process all cross points on the cross queue at the current x_
 561         //std::cout << "advance_\n";
 562         std::vector<iterator> eraseVec;
 563         while(!crossQueue_.empty() &&
 564               (*crossQueue_.begin()).x() == x_){
 565           //std::cout << "loop\n";
 566           //pop point off the cross queue
 567           Point crossPoint = *(crossQueue_.begin());
 568           //std::cout << crossPoint << "\n";
 569           //for(iterator iter = scanData_.begin();
 570           //    iter != scanData_.end(); ++iter) {
 571           //  std::cout << "scan element\n";
 572           //  std::cout << *iter << " " << iter->evalAtX(x_) << "\n";
 573           //}
 574           crossQueue_.erase(crossQueue_.begin());
 575           Scan45Vertex vertex(crossPoint, Scan45Count());
 576           iterator lowIter = lookUp_(vertex.first.y());
 577           //std::cout << "searching at: " << vertex.first.y() << "\n";
 578           //if(lowIter == scanData_.end()) std::cout << "could not find\n";
 579           //else std::cout << "found: " << *lowIter << "\n";
 580           if(lowIter == scanData_.end() ||
 581              lowIter->evalAtX(x_) != vertex.first.y()) {
 582             //   std::cout << "skipping\n";
 583             //there weren't any edges at this potential cross point
 584             continue;
 585           }
 586           CountType countBelow;
 587           iterator searchDownItr = lowIter;
 588           while(searchDownItr != scanData_.begin()
 589                 && searchDownItr->evalAtX(x_) == vertex.first.y()) {
 590             //get count from below
 591             --searchDownItr;
 592             countBelow = searchDownItr->count;
 593           }
 594           //std::cout << "Below Count: " << countBelow << "\n";
 595           Scan45Count count(countBelow);
 596           std::size_t numEdges = 0;
 597           iterator eraseItrs[3];
 598           while(lowIter != scanData_.end() &&
 599                 lowIter->evalAtX(x_) == vertex.first.y()) {
 600             for(int index = lowIter->rise +1; index >= 0; --index)
 601               count[index] = lowIter->count;
 602             //std::cout << count << "\n";
 603             eraseItrs[numEdges] = lowIter;
 604             ++numEdges;
 605             ++lowIter;
 606           }
 607           if(numEdges == 1) {
 608             //look for the next crossing point and continue
 609             //std::cout << "found only one edge\n";
 610             findCross_(eraseItrs[0]);
 611             continue;
 612           }
 613           //before we erase the elements we need to decide if they should be written out
 614           CountType currentCount = countBelow;
 615           for(std::size_t i = 0; i < numEdges; ++i) {
 616             output_functor f;
 617             f(output, currentCount, eraseItrs[i]->count, crossPoint, eraseItrs[i]->rise, LOW);
 618             currentCount = eraseItrs[i]->count;
 619           }
 620           //schedule erase of the elements
 621           for(std::size_t i = 0; i < numEdges; ++i) {
 622             eraseVec.push_back(eraseItrs[i]);
 623           }
 624
 625           //take the derivative wrt theta of the count at the crossing point
 626           vertex.second[2] = count[2] - countBelow;
 627           vertex.second[1] = count[1] - count[2];
 628           vertex.second[0] = count[0] - count[1];
 629           //add the point, deriviative pair into the cross vector
 630           //std::cout << "LOOK HERE!\n";
 631           //std::cout << count << "\n";
 632           //std::cout << vertex << "\n";
 633           crossVector_.push_back(vertex);
 634         }
 635         //erase crossing elements
 636         std::vector<iterator> searchVec;
 637         for(std::size_t i = 0; i < eraseVec.size(); ++i) {
 638           if(eraseVec[i] != scanData_.begin()) {
 639             iterator searchItr = eraseVec[i];
 640             --searchItr;
 641             if(searchVec.empty() ||
 642                searchVec.back() != searchItr)
 643               searchVec.push_back(searchItr);
 644           }
 645           scanData_.erase(eraseVec[i]);
 646         }
 647         for(std::size_t i = 0; i < searchVec.size(); ++i) {
 648           findCross_(searchVec[i]);
 649         }
 650       }
 651
 652       template <class iT>
 653       inline iT mergeCross_(iT inputBegin, iT inputEnd) {
 654         Scan45Vector vec;
 655         swap(vec, crossVector_);
 656         iT mergeEnd = inputBegin;
 657         std::size_t mergeCount = 0;
 658         while(mergeEnd != inputEnd &&
 659               (*mergeEnd).first.x() == x_) {
 660           ++mergeCount;
 661           ++mergeEnd;
 662         }
 663         crossVector_.reserve((std::max)(vec.capacity(), vec.size() + mergeCount));
 664         for(std::size_t i = 0; i < vec.size(); ++i){
 665           while(inputBegin != mergeEnd &&
 666                 (*inputBegin).first.y() < vec[i].first.y()) {
 667             crossVector_.push_back(*inputBegin);
 668             ++inputBegin;
 669           }
 670           crossVector_.push_back(vec[i]);
 671         }
 672         while(inputBegin != mergeEnd){
 673           crossVector_.push_back(*inputBegin);
 674           ++inputBegin;
 675         }
 676         return inputBegin;
 677       }
 678
 679       template <class cT, class iT>
 680       inline iT processEvent_(cT& output, iT inputBegin, iT inputEnd) {
 681         //std::cout << "processEvent_\n";
 682         CountType verticalCount = CountType();
 683         Point prevPoint;
 684         iterator prevIter = scanData_.end();
 685         while(inputBegin != inputEnd &&
 686               (*inputBegin).first.x() == x_) {
 687           //std::cout << (*inputBegin) << "\n";
 688           //std::cout << "loop\n";
 689           Scan45Vertex vertex = *inputBegin;
 690           //std::cout << vertex.first << "\n";
 691           //if vertical count propigating up fake a null event at the next element
 692           if(verticalCount != CountType() && (prevIter != scanData_.end() &&
 693                                               prevIter->evalAtX(x_) < vertex.first.y())) {
 694             //std::cout << "faking null event\n";
 695             vertex = Scan45Vertex(Point(x_, prevIter->evalAtX(x_)), Scan45Count());
 696           } else {
 697             ++inputBegin;
 698             //std::cout << "after increment\n";
 699             //accumulate overlapping changes in Scan45Count
 700             while(inputBegin != inputEnd &&
 701                   (*inputBegin).first.x() == x_ &&
 702                   (*inputBegin).first.y() == vertex.first.y()) {
 703               //std::cout << "accumulate\n";
 704               vertex.second += (*inputBegin).second;
 705               ++inputBegin;
 706             }
 707           }
 708           //std::cout << vertex.second << "\n";
 709           //integrate vertex
 710           CountType currentCount = verticalCount;// + vertex.second[0];
 711           for(unsigned int i = 0; i < 3; ++i) {
 712             vertex.second[i] = currentCount += vertex.second[i];
 713           }
 714           //std::cout << vertex.second << "\n";
 715           //vertex represents the change in state at this point
 716
 717           //get counts at current vertex
 718           CountType countBelow;
 719           iterator lowIter = lookUp_(vertex.first.y());
 720           if(lowIter != scanData_.begin()) {
 721             //get count from below
 722             --lowIter;
 723             countBelow = lowIter->count;
 724             ++lowIter;
 725           }
 726           //std::cout << "Count Below: " << countBelow[0] << " " << countBelow[1] << "\n";
 727           //std::cout << "vertical count: " << verticalCount[0] << " " << verticalCount[1] << "\n";
 728           Scan45Count countAt(countBelow - verticalCount);
 729           //check if the vertical edge should be written out
 730           if(verticalCount != CountType()) {
 731             output_functor f;
 732             f(output, countBelow - verticalCount, countBelow, prevPoint, 2, HIGH);
 733             f(output, countBelow - verticalCount, countBelow, vertex.first, 2, LOW);
 734           }
 735           currentCount = countBelow - verticalCount;
 736           while(lowIter != scanData_.end() &&
 737                 lowIter->evalAtX(x_) == vertex.first.y()) {
 738             for(unsigned int i = lowIter->rise + 1; i < 3; ++i) {
 739               countAt[i] = lowIter->count;
 740             }
 741             Point lp(lowIter->x, lowIter->y);
 742             if(lp != vertex.first) {
 743               output_functor f;
 744               f(output, currentCount, lowIter->count, vertex.first, lowIter->rise, LOW);
 745             }
 746             currentCount = lowIter->count;
 747             iterator nextIter = lowIter;
 748             ++nextIter;
 749             //std::cout << "erase\n";
 750             scanData_.erase(lowIter);
 751             if(nextIter != scanData_.end())
 752               findCross_(nextIter);
 753             lowIter = nextIter;
 754           }
 755           verticalCount += vertex.second[3];
 756           prevPoint = vertex.first;
 757           //std::cout << "new vertical count: " << verticalCount[0] << " " << verticalCount[1] << "\n";
 758           prevIter = lowIter;
 759           //count represents the current state at this point
 760           //std::cout << vertex.second << "\n";
 761           //std::cout << countAt << "\n";
 762           //std::cout << "ADD\n";
 763           vertex.second += countAt;
 764           //std::cout << vertex.second << "\n";
 765
 766           //add elements to the scanline
 767           for(int i = 0; i < 3; ++i) {
 768             if(vertex.second[i] != countBelow) {
 769               //std::cout << "insert: " << vertex.first.x() << " " << vertex.first.y() << " " << i-1 <<
 770               //  " " << vertex.second[i][0] << " " << vertex.second[i][1] << "\n";
 771               iterator insertIter = scanData_.insert(scanData_.end(),
 772                                                      Scan45ElementT<CountType>(vertex.first.x(),
 773                                                                                vertex.first.y(),
 774                                                                                i - 1, vertex.second[i]));
 775               findCross_(insertIter);
 776               output_functor f;
 777               f(output, countBelow, vertex.second[i], vertex.first, i - 1, HIGH);
 778             }
 779             countBelow = vertex.second[i];
 780           }
 781         }
 782         //std::cout << "end processEvent\n";
 783         return inputBegin;
 784       }
 785
 786       //iter1 is horizontal
 787       inline void scheduleCross0_(iterator iter1, iterator iter2) {
 788         //std::cout << "0, ";
 789         Unit y1 = iter1->evalAtX(x_);
 790         Unit y2 = iter2->evalAtX(x_);
 791         LongUnit delta = local_abs(LongUnit(y1) - LongUnit(y2));
 792         if(delta + static_cast<LongUnit>(x_) <= (std::numeric_limits<Unit>::max)())
 793           crossQueue_.insert(crossQueue_.end(), Point(x_ + static_cast<Unit>(delta), y1));
 794         //std::cout <<  Point(x_ + delta, y1);
 795       }
 796
 797       //neither iter is horizontal
 798       inline void scheduleCross1_(iterator iter1, iterator iter2) {
 799         //std::cout << "1, ";
 800         Unit y1 = iter1->evalAtX(x_);
 801         Unit y2 = iter2->evalAtX(x_);
 802         //std::cout << y1 << " " << y2 << ": ";
 803         //note that half the delta cannot exceed the positive inter range
 804         LongUnit delta = y1;
 805         delta -= y2;
 806         Unit UnitMax = (std::numeric_limits<Unit>::max)();
 807         if((delta & 1) == 1) {
 808           //delta is odd, division by 2 will result in integer trunctaion
 809           if(delta == 1) {
 810             //the cross point is not on the integer grid and cannot be represented
 811             //we must throw an exception
 812             std::string msg = "GTL 45 Boolean error, precision insufficient to represent edge intersection coordinate value.";
 813             throw(msg);
 814           } else {
 815             //note that result of this subtraction is always positive because itr1 is above itr2 in scanline
 816             LongUnit halfDelta2 = (LongUnit)((((LongUnit)y1) - y2)/2);
 817             //note that halfDelta2 has been truncated
 818             if(halfDelta2 + x_ <= UnitMax && halfDelta2 + y2 <= UnitMax) {
 819               crossQueue_.insert(crossQueue_.end(), Point(x_+static_cast<Unit>(halfDelta2), y2+static_cast<Unit>(halfDelta2)));
 820               crossQueue_.insert(crossQueue_.end(), Point(x_+static_cast<Unit>(halfDelta2), y2+static_cast<Unit>(halfDelta2)+1));
 821             }
 822           }
 823         } else {
 824           LongUnit halfDelta = (LongUnit)((((LongUnit)y1) - y2)/2);
 825           if(halfDelta + x_ <= UnitMax && halfDelta + y2 <= UnitMax)
 826             crossQueue_.insert(crossQueue_.end(), Point(x_+static_cast<Unit>(halfDelta), y2+static_cast<Unit>(halfDelta)));
 827           //std::cout << Point(x_+halfDelta, y2+halfDelta);
 828         }
 829       }
 830
 831       inline void findCross_(iterator iter) {
 832         //std::cout << "find cross ";
 833         iterator iteratorBelow = iter;
 834         iterator iteratorAbove = iter;
 835         if(iter != scanData_.begin() && iter->rise < 1) {
 836           --iteratorBelow;
 837           if(iter->rise == 0){
 838             if(iteratorBelow->rise == 1) {
 839               scheduleCross0_(iter, iteratorBelow);
 840             }
 841           } else {
 842             //iter->rise == -1
 843             if(iteratorBelow->rise == 1) {
 844               scheduleCross1_(iter, iteratorBelow);
 845             } else if(iteratorBelow->rise == 0) {
 846               scheduleCross0_(iteratorBelow, iter);
 847             }
 848           }
 849         }
 850         ++iteratorAbove;
 851         if(iteratorAbove != scanData_.end() && iter->rise > -1) {
 852           if(iter->rise == 0) {
 853             if(iteratorAbove->rise == -1) {
 854               scheduleCross0_(iter, iteratorAbove);
 855             }
 856           } else {
 857             //iter->rise == 1
 858             if(iteratorAbove->rise == -1) {
 859               scheduleCross1_(iteratorAbove, iter);
 860             } else if(iteratorAbove->rise == 0) {
 861               scheduleCross0_(iteratorAbove, iter);
 862             }
 863           }
 864         }
 865         //std::cout << "\n";
 866       }
 867
 868       inline iterator lookUp_(Unit y){
 869         //if just before then we need to look from 1 not -1
 870         return scanData_.lower_bound(Scan45ElementT<CountType>(x_, y, -1+2*justBefore_));
 871       }
 872     };
 873
 874     //template <typename CountType>
 875     //static inline void print45Data(const std::set<Scan45ElementT<CountType>,
 876     //                               lessScan45Element<CountType> >& data) {
 877     //  typename std::set<Scan45ElementT<CountType>, lessScan45Element<CountType> >::const_iterator iter;
 878     //  for(iter = data.begin(); iter != data.end(); ++iter) {
 879     //    std::cout << iter->x << " " << iter->y << " " << iter->rise << "\n";
 880     //  }
 881     //}
 882
 883     template <typename streamtype>
 884     static inline bool testScan45Data(streamtype& stdcout) {
 885       Unit x = 0;
 886       int justBefore = false;
 887       lessScan45Element<Count2> lessElm(&x, &justBefore);
 888       std::set<Scan45ElementT<Count2>, lessScan45Element<Count2> > testData(lessElm);
 889       //Unit size = testData.size();
 890       typedef std::set<Scan45ElementT<Count2>, lessScan45Element<Count2> > Scan45Data;
 891       typename Scan45Data::iterator itr10 = testData.insert(testData.end(), Scan45Element(0, 10, 1));
 892       typename Scan45Data::iterator itr20 = testData.insert(testData.end(), Scan45Element(0, 20, 1));
 893       typename Scan45Data::iterator itr30 = testData.insert(testData.end(), Scan45Element(0, 30, -1));
 894       typename Scan45Data::iterator itr40 = testData.insert(testData.end(), Scan45Element(0, 40, -1));
 895       typename Scan45Data::iterator itrA = testData.lower_bound(Scan45Element(0, 29, -1));
 896       typename Scan45Data::iterator itr1 = testData.lower_bound(Scan45Element(0, 10, -1));
 897       x = 4;
 898       //now at 14 24 26 36
 899       typename Scan45Data::iterator itrB = testData.lower_bound(Scan45Element(4, 29, -1));
 900       typename Scan45Data::iterator itr2 = testData.lower_bound(Scan45Element(4, 14, -1));
 901       if(itr1 != itr2) stdcout << "test1 failed\n";
 902       if(itrA == itrB) stdcout << "test2 failed\n";
 903       //remove crossing elements
 904       testData.erase(itr20);
 905       testData.erase(itr30);
 906       x = 5;
 907       itr20 = testData.insert(testData.end(), Scan45Element(0, 20, 1));
 908       itr30 = testData.insert(testData.end(), Scan45Element(0, 30, -1));
 909       //now at 15 25 25 35
 910       typename Scan45Data::iterator itr = testData.begin();
 911       if(itr != itr10) stdcout << "test3 failed\n";
 912       ++itr;
 913       if(itr != itr30) stdcout << "test4 failed\n";
 914       ++itr;
 915       if(itr != itr20) stdcout << "test5 failed\n";
 916       ++itr;
 917       if(itr != itr40) stdcout << "test6 failed\n";
 918       stdcout << "done testing Scan45Data\n";
 919       return true;
 920     }
 921
 922     template <typename stream_type>
 923     static inline bool testScan45Rect(stream_type& stdcout) {
 924       stdcout << "testing Scan45Rect\n";
 925       Scan45<Count2, boolean_op_45_output_functor<0> > scan45;
 926       std::vector<Vertex45 > result;
 927       typedef std::pair<Point, Scan45Count> Scan45Vertex;
 928       std::vector<Scan45Vertex> vertices;
 929       //is a Rectnagle(0, 0, 10, 10);
 930       Count2 count(1, 0);
 931       Count2 ncount(-1, 0);
 932       vertices.push_back(Scan45Vertex(Point(0,0), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
 933       vertices.push_back(Scan45Vertex(Point(0,10), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
 934       vertices.push_back(Scan45Vertex(Point(10,0), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
 935       vertices.push_back(Scan45Vertex(Point(10,10), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
 936       stdcout << "scanning\n";
 937       scan45.scan(result, vertices.begin(), vertices.end());
 938       stdcout << "done scanning\n";
 939       // result size == 8
 940       // result == 0 0 0 1
 941       // result == 0 0 2 1
 942       // result == 0 10 2 -1
 943       // result == 0 10 0 -1
 944       // result == 10 0 0 -1
 945       // result == 10 0 2 -1
 946       // result == 10 10 2 1
 947       // result == 10 10 0 1
 948       std::vector<Vertex45> reference;
 949       reference.push_back(Vertex45(Point(0, 0), 0, 1));
 950       reference.push_back(Vertex45(Point(0, 0), 2, 1));
 951       reference.push_back(Vertex45(Point(0, 10), 2, -1));
 952       reference.push_back(Vertex45(Point(0, 10), 0, -1));
 953       reference.push_back(Vertex45(Point(10, 0), 0, -1));
 954       reference.push_back(Vertex45(Point(10, 0), 2, -1));
 955       reference.push_back(Vertex45(Point(10, 10), 2, 1));
 956       reference.push_back(Vertex45(Point(10, 10), 0, 1));
 957       if(result != reference) {
 958         stdcout << "result size == " << result.size() << "\n";
 959         for(std::size_t i = 0; i < result.size(); ++i) {
 960           //std::cout << "result == " << result[i]<< "\n";
 961         }
 962         stdcout << "reference size == " << reference.size() << "\n";
 963         for(std::size_t i = 0; i < reference.size(); ++i) {
 964           //std::cout << "reference == " << reference[i]<< "\n";
 965         }
 966         return false;
 967       }
 968       stdcout << "done testing Scan45Rect\n";
 969       return true;
 970     }
 971
 972     template <typename stream_type>
 973     static inline bool testScan45P1(stream_type& stdcout) {
 974       stdcout << "testing Scan45P1\n";
 975       Scan45<Count2, boolean_op_45_output_functor<0> > scan45;
 976       std::vector<Vertex45 > result;
 977       typedef std::pair<Point, Scan45Count> Scan45Vertex;
 978       std::vector<Scan45Vertex> vertices;
 979       //is a Rectnagle(0, 0, 10, 10);
 980       Count2 count(1, 0);
 981       Count2 ncount(-1, 0);
 982       vertices.push_back(Scan45Vertex(Point(0,0), Scan45Count(Count2(0, 0), Count2(0, 0), count, count)));
 983       vertices.push_back(Scan45Vertex(Point(0,10), Scan45Count(Count2(0, 0), Count2(0, 0), ncount, ncount)));
 984       vertices.push_back(Scan45Vertex(Point(10,10), Scan45Count(Count2(0, 0), Count2(0, 0), ncount, ncount)));
 985       vertices.push_back(Scan45Vertex(Point(10,20), Scan45Count(Count2(0, 0), Count2(0, 0), count, count)));
 986       stdcout << "scanning\n";
 987       scan45.scan(result, vertices.begin(), vertices.end());
 988       stdcout << "done scanning\n";
 989       // result size == 8
 990       // result == 0 0 1 1
 991       // result == 0 0 2 1
 992       // result == 0 10 2 -1
 993       // result == 0 10 1 -1
 994       // result == 10 10 1 -1
 995       // result == 10 10 2 -1
 996       // result == 10 20 2 1
 997       // result == 10 20 1 1
 998       std::vector<Vertex45> reference;
 999       reference.push_back(Vertex45(Point(0, 0), 1, 1));
1000       reference.push_back(Vertex45(Point(0, 0), 2, 1));
1001       reference.push_back(Vertex45(Point(0, 10), 2, -1));
1002       reference.push_back(Vertex45(Point(0, 10), 1, -1));
1003       reference.push_back(Vertex45(Point(10, 10), 1, -1));
1004       reference.push_back(Vertex45(Point(10, 10), 2, -1));
1005       reference.push_back(Vertex45(Point(10, 20), 2, 1));
1006       reference.push_back(Vertex45(Point(10, 20), 1, 1));
1007       if(result != reference) {
1008         stdcout << "result size == " << result.size() << "\n";
1009         for(std::size_t i = 0; i < result.size(); ++i) {
1010           //std::cout << "result == " << result[i]<< "\n";
1011         }
1012         stdcout << "reference size == " << reference.size() << "\n";
1013         for(std::size_t i = 0; i < reference.size(); ++i) {
1014           //std::cout << "reference == " << reference[i]<< "\n";
1015         }
1016         return false;
1017       }
1018       stdcout << "done testing Scan45P1\n";
1019       return true;
1020     }
1021
1022     template <typename stream_type>
1023     static inline bool testScan45P2(stream_type& stdcout) {
1024       stdcout << "testing Scan45P2\n";
1025       Scan45<Count2, boolean_op_45_output_functor<0> > scan45;
1026       std::vector<Vertex45 > result;
1027       typedef std::pair<Point, Scan45Count> Scan45Vertex;
1028       std::vector<Scan45Vertex> vertices;
1029       //is a Rectnagle(0, 0, 10, 10);
1030       Count2 count(1, 0);
1031       Count2 ncount(-1, 0);
1032       vertices.push_back(Scan45Vertex(Point(0,0), Scan45Count(Count2(0, 0), count, ncount, Count2(0, 0))));
1033       vertices.push_back(Scan45Vertex(Point(10,0), Scan45Count(Count2(0, 0), ncount, count, Count2(0, 0))));
1034       vertices.push_back(Scan45Vertex(Point(10,10), Scan45Count(Count2(0, 0), ncount, count, Count2(0, 0))));
1035       vertices.push_back(Scan45Vertex(Point(20,10), Scan45Count(Count2(0, 0), count, ncount, Count2(0, 0))));
1036       stdcout << "scanning\n";
1037       scan45.scan(result, vertices.begin(), vertices.end());
1038       stdcout << "done scanning\n";
1039       // result size == 8
1040       // result == 0 0 0 1
1041       // result == 0 0 1 -1
1042       // result == 10 0 0 -1
1043       // result == 10 0 1 1
1044       // result == 10 10 1 1
1045       // result == 10 10 0 -1
1046       // result == 20 10 1 -1
1047       // result == 20 10 0 1
1048       std::vector<Vertex45> reference;
1049       reference.push_back(Vertex45(Point(0, 0), 0, 1));
1050       reference.push_back(Vertex45(Point(0, 0), 1, -1));
1051       reference.push_back(Vertex45(Point(10, 0), 0, -1));
1052       reference.push_back(Vertex45(Point(10, 0), 1, 1));
1053       reference.push_back(Vertex45(Point(10, 10), 1, 1));
1054       reference.push_back(Vertex45(Point(10, 10), 0, -1));
1055       reference.push_back(Vertex45(Point(20, 10), 1, -1));
1056       reference.push_back(Vertex45(Point(20, 10), 0, 1));
1057       if(result != reference) {
1058         stdcout << "result size == " << result.size() << "\n";
1059         for(std::size_t i = 0; i < result.size(); ++i) {
1060           //stdcout << "result == " << result[i]<< "\n";
1061         }
1062         stdcout << "reference size == " << reference.size() << "\n";
1063         for(std::size_t i = 0; i < reference.size(); ++i) {
1064           //stdcout << "reference == " << reference[i]<< "\n";
1065         }
1066         return false;
1067       }
1068       stdcout << "done testing Scan45P2\n";
1069       return true;
1070     }
1071
1072     template <typename streamtype>
1073     static inline bool testScan45And(streamtype& stdcout) {
1074       stdcout << "testing Scan45And\n";
1075       Scan45<Count2, boolean_op_45_output_functor<1> > scan45;
1076       std::vector<Vertex45 > result;
1077       typedef std::pair<Point, Scan45Count> Scan45Vertex;
1078       std::vector<Scan45Vertex> vertices;
1079       //is a Rectnagle(0, 0, 10, 10);
1080       Count2 count(1, 0);
1081       Count2 ncount(-1, 0);
1082       vertices.push_back(Scan45Vertex(Point(0,0), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
1083       vertices.push_back(Scan45Vertex(Point(0,10), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
1084       vertices.push_back(Scan45Vertex(Point(10,0), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
1085       vertices.push_back(Scan45Vertex(Point(10,10), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
1086       count = Count2(0, 1);
1087       ncount = count.invert();
1088       vertices.push_back(Scan45Vertex(Point(2,2), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
1089       vertices.push_back(Scan45Vertex(Point(2,12), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
1090       vertices.push_back(Scan45Vertex(Point(12,2), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
1091       vertices.push_back(Scan45Vertex(Point(12,12), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
1092       sortScan45Vector(vertices);
1093       stdcout << "scanning\n";
1094       scan45.scan(result, vertices.begin(), vertices.end());
1095       stdcout << "done scanning\n";
1096       //result size == 8
1097       //result == 2 2 0 1
1098       //result == 2 2 2 1
1099       //result == 2 10 2 -1
1100       //result == 2 10 0 -1
1101       //result == 10 2 0 -1
1102       //result == 10 2 2 -1
1103       //result == 10 10 2 1
1104       //result == 10 10 0 1
1105       std::vector<Vertex45> reference;
1106       reference.push_back(Vertex45(Point(2, 2), 0, 1));
1107       reference.push_back(Vertex45(Point(2, 2), 2, 1));
1108       reference.push_back(Vertex45(Point(2, 10), 2, -1));
1109       reference.push_back(Vertex45(Point(2, 10), 0, -1));
1110       reference.push_back(Vertex45(Point(10, 2), 0, -1));
1111       reference.push_back(Vertex45(Point(10, 2), 2, -1));
1112       reference.push_back(Vertex45(Point(10, 10), 2, 1));
1113       reference.push_back(Vertex45(Point(10, 10), 0, 1));
1114       if(result != reference) {
1115         stdcout << "result size == " << result.size() << "\n";
1116         for(std::size_t i = 0; i < result.size(); ++i) {
1117           //stdcout << "result == " << result[i]<< "\n";
1118         }
1119         stdcout << "reference size == " << reference.size() << "\n";
1120         for(std::size_t i = 0; i < reference.size(); ++i) {
1121           //stdcout << "reference == " << reference[i]<< "\n";
1122         }
1123         return false;
1124       }
1125       stdcout << "done testing Scan45And\n";
1126       return true;
1127     }
1128
1129     template <typename stream_type>
1130     static inline bool testScan45Star1(stream_type& stdcout) {
1131       stdcout << "testing Scan45Star1\n";
1132       Scan45<Count2, boolean_op_45_output_functor<0> > scan45;
1133       std::vector<Vertex45 > result;
1134       typedef std::pair<Point, Scan45Count> Scan45Vertex;
1135       std::vector<Scan45Vertex> vertices;
1136       //is a Rectnagle(0, 0, 10, 10);
1137       Count2 count(1, 0);
1138       Count2 ncount(-1, 0);
1139       vertices.push_back(Scan45Vertex(Point(0,8), Scan45Count(count, Count2(0, 0), ncount, Count2(0, 0))));
1140       vertices.push_back(Scan45Vertex(Point(8,0), Scan45Count(ncount, Count2(0, 0), Count2(0, 0), ncount)));
1141       vertices.push_back(Scan45Vertex(Point(8,16), Scan45Count(Count2(0, 0), Count2(0, 0), count, count)));
1142       count = Count2(0, 1);
1143       ncount = count.invert();
1144       vertices.push_back(Scan45Vertex(Point(12,8), Scan45Count(count, Count2(0, 0), ncount, Count2(0, 0))));
1145       vertices.push_back(Scan45Vertex(Point(4,0), Scan45Count(Count2(0, 0), Count2(0, 0), count, count)));
1146       vertices.push_back(Scan45Vertex(Point(4,16), Scan45Count(ncount, Count2(0, 0), Count2(0, 0), ncount)));
1147       sortScan45Vector(vertices);
1148       stdcout << "scanning\n";
1149       scan45.scan(result, vertices.begin(), vertices.end());
1150       stdcout << "done scanning\n";
1151       // result size == 24
1152       // result == 0 8 -1 1
1153       // result == 0 8 1 -1
1154       // result == 4 0 1 1
1155       // result == 4 0 2 1
1156       // result == 4 4 2 -1
1157       // result == 4 4 -1 -1
1158       // result == 4 12 1 1
1159       // result == 4 12 2 1
1160       // result == 4 16 2 -1
1161       // result == 4 16 -1 -1
1162       // result == 6 2 1 -1
1163       // result == 6 14 -1 1
1164       // result == 6 2 -1 1
1165       // result == 6 14 1 -1
1166       // result == 8 0 -1 -1
1167       // result == 8 0 2 -1
1168       // result == 8 4 2 1
1169       // result == 8 4 1 1
1170       // result == 8 12 -1 -1
1171       // result == 8 12 2 -1
1172       // result == 8 16 2 1
1173       // result == 8 16 1 1
1174       // result == 12 8 1 -1
1175       // result == 12 8 -1 1
1176       if(result.size() != 24) {
1177         //stdcout << "result size == " << result.size() << "\n";
1178         //stdcout << "reference size == " << 24 << "\n";
1179         return false;
1180       }
1181       stdcout << "done testing Scan45Star1\n";
1182       return true;
1183     }
1184
1185     template <typename stream_type>
1186     static inline bool testScan45Star2(stream_type& stdcout) {
1187       stdcout << "testing Scan45Star2\n";
1188       Scan45<Count2, boolean_op_45_output_functor<0> > scan45;
1189       std::vector<Vertex45 > result;
1190       typedef std::pair<Point, Scan45Count> Scan45Vertex;
1191       std::vector<Scan45Vertex> vertices;
1192       //is a Rectnagle(0, 0, 10, 10);
1193       Count2 count(1, 0);
1194       Count2 ncount(-1, 0);
1195       vertices.push_back(Scan45Vertex(Point(0,4), Scan45Count(Count2(0, 0), count, ncount, Count2(0, 0))));
1196       vertices.push_back(Scan45Vertex(Point(16,4), Scan45Count(count, ncount, Count2(0, 0), Count2(0, 0))));
1197       vertices.push_back(Scan45Vertex(Point(8,12), Scan45Count(ncount, Count2(0, 0), count, Count2(0, 0))));
1198       count = Count2(0, 1);
1199       ncount = count.invert();
1200       vertices.push_back(Scan45Vertex(Point(0,8), Scan45Count(count, ncount, Count2(0, 0), Count2(0, 0))));
1201       vertices.push_back(Scan45Vertex(Point(16,8), Scan45Count(Count2(0, 0), count, ncount, Count2(0, 0))));
1202       vertices.push_back(Scan45Vertex(Point(8,0), Scan45Count(ncount, Count2(0, 0), count, Count2(0, 0))));
1203       sortScan45Vector(vertices);
1204       stdcout << "scanning\n";
1205       scan45.scan(result, vertices.begin(), vertices.end());
1206       stdcout << "done scanning\n";
1207       // result size == 24
1208       // result == 0 4 0 1
1209       // result == 0 4 1 -1
1210       // result == 0 8 -1 1
1211       // result == 0 8 0 -1
1212       // result == 2 6 1 1
1213       // result == 2 6 -1 -1
1214       // result == 4 4 0 -1
1215       // result == 4 8 0 1
1216       // result == 4 4 -1 1
1217       // result == 4 8 1 -1
1218       // result == 8 0 -1 -1
1219       // result == 8 0 1 1
1220       // result == 8 12 1 1
1221       // result == 8 12 -1 -1
1222       // result == 12 4 1 -1
1223       // result == 12 8 -1 1
1224       // result == 12 4 0 1
1225       // result == 12 8 0 -1
1226       // result == 14 6 -1 -1
1227       // result == 14 6 1 1
1228       // result == 16 4 0 -1
1229       // result == 16 4 -1 1
1230       // result == 16 8 1 -1
1231       // result == 16 8 0 1
1232       if(result.size() != 24) {
1233         //std::cout << "result size == " << result.size() << "\n";
1234         //std::cout << "reference size == " << 24 << "\n";
1235         return false;
1236       }
1237       stdcout << "done testing Scan45Star2\n";
1238       return true;
1239     }
1240
1241     template <typename stream_type>
1242     static inline bool testScan45Star3(stream_type& stdcout) {
1243       stdcout << "testing Scan45Star3\n";
1244       Scan45<Count2, boolean_op_45_output_functor<0> > scan45;
1245       std::vector<Vertex45 > result;
1246       typedef std::pair<Point, Scan45Count> Scan45Vertex;
1247       std::vector<Scan45Vertex> vertices;
1248       //is a Rectnagle(0, 0, 10, 10);
1249       Count2 count(1, 0);
1250       Count2 ncount(-1, 0);
1251       vertices.push_back(Scan45Vertex(Point(0,8), Scan45Count(count, Count2(0, 0), ncount, Count2(0, 0))));
1252       vertices.push_back(Scan45Vertex(Point(8,0), Scan45Count(ncount, Count2(0, 0), Count2(0, 0), ncount)));
1253       vertices.push_back(Scan45Vertex(Point(8,16), Scan45Count(Count2(0, 0), Count2(0, 0), count, count)));
1254
1255       vertices.push_back(Scan45Vertex(Point(6,0), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
1256       vertices.push_back(Scan45Vertex(Point(6,14), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
1257       vertices.push_back(Scan45Vertex(Point(12,0), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
1258       vertices.push_back(Scan45Vertex(Point(12,14), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
1259       count = Count2(0, 1);
1260       ncount = count.invert();
1261       vertices.push_back(Scan45Vertex(Point(12,8), Scan45Count(count, Count2(0, 0), ncount, Count2(0, 0))));
1262       vertices.push_back(Scan45Vertex(Point(4,0), Scan45Count(Count2(0, 0), Count2(0, 0), count, count)));
1263       vertices.push_back(Scan45Vertex(Point(4,16), Scan45Count(ncount, Count2(0, 0), Count2(0, 0), ncount)));
1264       sortScan45Vector(vertices);
1265       stdcout << "scanning\n";
1266       scan45.scan(result, vertices.begin(), vertices.end());
1267       stdcout << "done scanning\n";
1268       // result size == 28
1269       // result == 0 8 -1 1
1270       // result == 0 8 1 -1
1271       // result == 4 0 1 1
1272       // result == 4 0 2 1
1273       // result == 4 4 2 -1
1274       // result == 4 4 -1 -1
1275       // result == 4 12 1 1
1276       // result == 4 12 2 1
1277       // result == 4 16 2 -1
1278       // result == 4 16 -1 -1
1279       // result == 6 2 1 -1
1280       // result == 6 14 -1 1
1281       // result == 6 0 0 1
1282       // result == 6 0 2 1
1283       // result == 6 2 2 -1
1284       // result == 6 14 1 -1
1285       // result == 8 0 0 -1
1286       // result == 8 0 0 1
1287       // result == 8 14 0 -1
1288       // result == 8 14 2 -1
1289       // result == 8 16 2 1
1290       // result == 8 16 1 1
1291       // result == 12 0 0 -1
1292       // result == 12 0 2 -1
1293       // result == 12 8 2 1
1294       // result == 12 8 2 -1
1295       // result == 12 14 2 1
1296       // result == 12 14 0 1
1297       if(result.size() != 28) {
1298         //std::cout << "result size == " << result.size() << "\n";
1299         //std::cout << "reference size == " << 28 << "\n";
1300         return false;
1301       }
1302
1303       stdcout << "done testing Scan45Star3\n";
1304       return true;
1305     }
1306
1307
1308     template <typename stream_type>
1309     static inline bool testScan45Star4(stream_type& stdcout) {
1310       stdcout << "testing Scan45Star4\n";
1311       Scan45<Count2, boolean_op_45_output_functor<0> > scan45;
1312       std::vector<Vertex45 > result;
1313       typedef std::pair<Point, Scan45Count> Scan45Vertex;
1314       std::vector<Scan45Vertex> vertices;
1315       //is a Rectnagle(0, 0, 10, 10);
1316       Count2 count(1, 0);
1317       Count2 ncount(-1, 0);
1318       vertices.push_back(Scan45Vertex(Point(0,4), Scan45Count(Count2(0, 0), count, ncount, Count2(0, 0))));
1319       vertices.push_back(Scan45Vertex(Point(16,4), Scan45Count(count, ncount, Count2(0, 0), Count2(0, 0))));
1320       vertices.push_back(Scan45Vertex(Point(8,12), Scan45Count(ncount, Count2(0, 0), count, Count2(0, 0))));
1321
1322       vertices.push_back(Scan45Vertex(Point(0,6), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
1323       vertices.push_back(Scan45Vertex(Point(0,12), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
1324       vertices.push_back(Scan45Vertex(Point(16,6), Scan45Count(Count2(0, 0), ncount, Count2(0, 0), ncount)));
1325       vertices.push_back(Scan45Vertex(Point(16,12), Scan45Count(Count2(0, 0), count, Count2(0, 0), count)));
1326       count = Count2(0, 1);
1327       ncount = count.invert();
1328       vertices.push_back(Scan45Vertex(Point(0,8), Scan45Count(count, ncount, Count2(0, 0), Count2(0, 0))));
1329       vertices.push_back(Scan45Vertex(Point(16,8), Scan45Count(Count2(0, 0), count, ncount, Count2(0, 0))));
1330       vertices.push_back(Scan45Vertex(Point(8,0), Scan45Count(ncount, Count2(0, 0), count, Count2(0, 0))));
1331       sortScan45Vector(vertices);
1332       stdcout << "scanning\n";
1333       scan45.scan(result, vertices.begin(), vertices.end());
1334       stdcout << "done scanning\n";
1335       // result size == 28
1336       // result == 0 4 0 1
1337       // result == 0 4 1 -1
1338       // result == 0 6 0 1
1339       // result == 0 6 2 1
1340       // result == 0 8 2 -1
1341       // result == 0 8 2 1
1342       // result == 0 12 2 -1
1343       // result == 0 12 0 -1
1344       // result == 2 6 1 1
1345       // result == 2 6 0 -1
1346       // result == 4 4 0 -1
1347       // result == 4 4 -1 1
1348       // result == 8 12 0 1
1349       // result == 8 0 -1 -1
1350       // result == 8 0 1 1
1351       // result == 8 12 0 -1
1352       // result == 12 4 1 -1
1353       // result == 12 4 0 1
1354       // result == 14 6 -1 -1
1355       // result == 14 6 0 1
1356       // result == 16 4 0 -1
1357       // result == 16 4 -1 1
1358       // result == 16 6 0 -1
1359       // result == 16 6 2 -1
1360       // result == 16 8 2 1
1361       // result == 16 8 2 -1
1362       // result == 16 12 2 1
1363       // result == 16 12 0 1
1364       if(result.size() != 28) {
1365         //stdcout << "result size == " << result.size() << "\n";
1366         //stdcout << "reference size == " << 28 << "\n";
1367         return false;
1368       }
1369
1370       stdcout << "done testing Scan45Star4\n";
1371       return true;
1372     }
1373
1374     template <typename stream_type>
1375     static inline bool testScan45(stream_type& stdcout) {
1376       if(!testScan45Rect(stdcout)) return false;
1377       if(!testScan45P1(stdcout)) return false;
1378       if(!testScan45P2(stdcout)) return false;
1379       if(!testScan45And(stdcout)) return false;
1380       if(!testScan45Star1(stdcout)) return false;
1381       if(!testScan45Star2(stdcout)) return false;
1382       if(!testScan45Star3(stdcout)) return false;
1383       if(!testScan45Star4(stdcout)) return false;
1384       return true;
1385     }
1386
1387   };
1388
1389 }
1390
1391 }
1392 #endif