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