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_POLYGON_45_FORMATION_HPP 9 #define BOOST_POLYGON_POLYGON_45_FORMATION_HPP 10 namespace boost { namespace polygon{ 11 12 template <typename T, typename T2> 13 struct PolyLineByConcept {}; 14 15 template <typename T> 16 class PolyLine45PolygonData; 17 template <typename T> 18 class PolyLine45HoleData; 19 20 //polygon45formation algorithm 21 template <typename Unit> 22 struct polygon_45_formation : public boolean_op_45<Unit> { 23 typedef point_data<Unit> Point; 24 typedef polygon_45_data<Unit> Polygon45; 25 typedef polygon_45_with_holes_data<Unit> Polygon45WithHoles; 26 typedef typename boolean_op_45<Unit>::Vertex45 Vertex45; 27 typedef typename boolean_op_45<Unit>::lessVertex45 lessVertex45; 28 typedef typename boolean_op_45<Unit>::Count2 Count2; 29 typedef typename boolean_op_45<Unit>::Scan45Count Scan45Count; 30 typedef std::pair<Point, Scan45Count> Scan45Vertex; 31 typedef typename boolean_op_45<Unit>::template 32 Scan45<Count2, typename boolean_op_45<Unit>::template boolean_op_45_output_functor<0> > Scan45; 33 34 class PolyLine45 { 35 public: 36 typedef typename std::list<Point>::const_iterator iterator; 37 38 // default constructor of point does not initialize x and y PolyLine45()39 inline PolyLine45() : points() {} //do nothing default constructor 40 41 // initialize a polygon from x,y values, it is assumed that the first is an x 42 // and that the input is a well behaved polygon 43 template<class iT> set(iT inputBegin,iT inputEnd)44 inline PolyLine45& set(iT inputBegin, iT inputEnd) { 45 points.clear(); //just in case there was some old data there 46 while(inputBegin != inputEnd) { 47 points.insert(points.end(), *inputBegin); 48 ++inputBegin; 49 } 50 return *this; 51 } 52 53 // copy constructor (since we have dynamic memory) PolyLine45(const PolyLine45 & that)54 inline PolyLine45(const PolyLine45& that) : points(that.points) {} 55 56 // assignment operator (since we have dynamic memory do a deep copy) operator =(const PolyLine45 & that)57 inline PolyLine45& operator=(const PolyLine45& that) { 58 points = that.points; 59 return *this; 60 } 61 62 // get begin iterator, returns a pointer to a const Unit begin() const63 inline iterator begin() const { return points.begin(); } 64 65 // get end iterator, returns a pointer to a const Unit end() const66 inline iterator end() const { return points.end(); } 67 size() const68 inline std::size_t size() const { return points.size(); } 69 70 //public data member 71 std::list<Point> points; 72 }; 73 74 class ActiveTail45 { 75 private: 76 //data 77 PolyLine45* tailp_; 78 ActiveTail45 *otherTailp_; 79 std::list<ActiveTail45*> holesList_; 80 bool head_; 81 public: 82 83 /** 84 * @brief iterator over coordinates of the figure 85 */ 86 typedef typename PolyLine45::iterator iterator; 87 88 /** 89 * @brief iterator over holes contained within the figure 90 */ 91 typedef typename std::list<ActiveTail45*>::const_iterator iteratorHoles; 92 93 //default constructor ActiveTail45()94 inline ActiveTail45() : tailp_(0), otherTailp_(0), holesList_(), head_(0) {} 95 96 //constructor ActiveTail45(const Vertex45 & vertex,ActiveTail45 * otherTailp=0)97 inline ActiveTail45(const Vertex45& vertex, ActiveTail45* otherTailp = 0) : 98 tailp_(0), otherTailp_(0), holesList_(), head_(0) { 99 tailp_ = new PolyLine45; 100 tailp_->points.push_back(vertex.pt); 101 bool headArray[4] = {false, true, true, true}; 102 bool inverted = vertex.count == -1; 103 head_ = headArray[vertex.rise+1] ^ inverted; 104 otherTailp_ = otherTailp; 105 } 106 ActiveTail45(Point point,ActiveTail45 * otherTailp,bool head=true)107 inline ActiveTail45(Point point, ActiveTail45* otherTailp, bool head = true) : 108 tailp_(0), otherTailp_(0), holesList_(), head_(0) { 109 tailp_ = new PolyLine45; 110 tailp_->points.push_back(point); 111 head_ = head; 112 otherTailp_ = otherTailp; 113 114 } ActiveTail45(ActiveTail45 * otherTailp)115 inline ActiveTail45(ActiveTail45* otherTailp) : 116 tailp_(0), otherTailp_(0), holesList_(), head_(0) { 117 tailp_ = otherTailp->tailp_; 118 otherTailp_ = otherTailp; 119 } 120 121 //copy constructor ActiveTail45(const ActiveTail45 & that)122 inline ActiveTail45(const ActiveTail45& that) : 123 tailp_(0), otherTailp_(0), holesList_(), head_(0) { (*this) = that; } 124 125 //destructor ~ActiveTail45()126 inline ~ActiveTail45() { 127 destroyContents(); 128 } 129 130 //assignment operator operator =(const ActiveTail45 & that)131 inline ActiveTail45& operator=(const ActiveTail45& that) { 132 tailp_ = new PolyLine45(*(that.tailp_)); 133 head_ = that.head_; 134 otherTailp_ = that.otherTailp_; 135 holesList_ = that.holesList_; 136 return *this; 137 } 138 139 //equivalence operator operator ==(const ActiveTail45 & b) const140 inline bool operator==(const ActiveTail45& b) const { 141 return tailp_ == b.tailp_ && head_ == b.head_; 142 } 143 144 /** 145 * @brief get the pointer to the polyline that this is an active tail of 146 */ getTail() const147 inline PolyLine45* getTail() const { return tailp_; } 148 149 /** 150 * @brief get the pointer to the polyline at the other end of the chain 151 */ getOtherTail() const152 inline PolyLine45* getOtherTail() const { return otherTailp_->tailp_; } 153 154 /** 155 * @brief get the pointer to the activetail at the other end of the chain 156 */ getOtherActiveTail() const157 inline ActiveTail45* getOtherActiveTail() const { return otherTailp_; } 158 159 /** 160 * @brief test if another active tail is the other end of the chain 161 */ isOtherTail(const ActiveTail45 & b) const162 inline bool isOtherTail(const ActiveTail45& b) const { return &b == otherTailp_; } 163 164 /** 165 * @brief update this end of chain pointer to new polyline 166 */ updateTail(PolyLine45 * newTail)167 inline ActiveTail45& updateTail(PolyLine45* newTail) { tailp_ = newTail; return *this; } 168 join(ActiveTail45 * tail)169 inline bool join(ActiveTail45* tail) { 170 if(tail == otherTailp_) { 171 //std::cout << "joining to other tail!\n"; 172 return false; 173 } 174 if(tail->head_ == head_) { 175 //std::cout << "joining head to head!\n"; 176 return false; 177 } 178 if(!tailp_) { 179 //std::cout << "joining empty tail!\n"; 180 return false; 181 } 182 if(!(otherTailp_->head_)) { 183 otherTailp_->copyHoles(*tail); 184 otherTailp_->copyHoles(*this); 185 } else { 186 tail->otherTailp_->copyHoles(*this); 187 tail->otherTailp_->copyHoles(*tail); 188 } 189 PolyLine45* tail1 = tailp_; 190 PolyLine45* tail2 = tail->tailp_; 191 if(head_) std::swap(tail1, tail2); 192 tail1->points.splice(tail1->points.end(), tail2->points); 193 delete tail2; 194 otherTailp_->tailp_ = tail1; 195 tail->otherTailp_->tailp_ = tail1; 196 otherTailp_->otherTailp_ = tail->otherTailp_; 197 tail->otherTailp_->otherTailp_ = otherTailp_; 198 tailp_ = 0; 199 tail->tailp_ = 0; 200 tail->otherTailp_ = 0; 201 otherTailp_ = 0; 202 return true; 203 } 204 205 /** 206 * @brief associate a hole to this active tail by the specified policy 207 */ addHole(ActiveTail45 * hole)208 inline ActiveTail45* addHole(ActiveTail45* hole) { 209 holesList_.push_back(hole); 210 copyHoles(*hole); 211 copyHoles(*(hole->otherTailp_)); 212 return this; 213 } 214 215 /** 216 * @brief get the list of holes 217 */ getHoles() const218 inline const std::list<ActiveTail45*>& getHoles() const { return holesList_; } 219 220 /** 221 * @brief copy holes from that to this 222 */ copyHoles(ActiveTail45 & that)223 inline void copyHoles(ActiveTail45& that) { holesList_.splice(holesList_.end(), that.holesList_); } 224 225 /** 226 * @brief find out if solid to right 227 */ solidToRight() const228 inline bool solidToRight() const { return !head_; } solidToLeft() const229 inline bool solidToLeft() const { return head_; } 230 231 /** 232 * @brief get vertex 233 */ getPoint() const234 inline Point getPoint() const { 235 if(head_) return tailp_->points.front(); 236 return tailp_->points.back(); 237 } 238 239 /** 240 * @brief add a coordinate to the polygon at this active tail end, properly handle degenerate edges by removing redundant coordinate 241 */ pushPoint(Point point)242 inline void pushPoint(Point point) { 243 if(head_) { 244 //if(tailp_->points.size() < 2) { 245 // tailp_->points.push_front(point); 246 // return; 247 //} 248 typename std::list<Point>::iterator iter = tailp_->points.begin(); 249 if(iter == tailp_->points.end()) { 250 tailp_->points.push_front(point); 251 return; 252 } 253 Unit firstY = (*iter).y(); 254 Unit firstX = (*iter).x(); 255 ++iter; 256 if(iter == tailp_->points.end()) { 257 tailp_->points.push_front(point); 258 return; 259 } 260 if((iter->y() == point.y() && firstY == point.y()) || 261 (iter->x() == point.x() && firstX == point.x())){ 262 --iter; 263 *iter = point; 264 } else { 265 tailp_->points.push_front(point); 266 } 267 return; 268 } 269 //if(tailp_->points.size() < 2) { 270 // tailp_->points.push_back(point); 271 // return; 272 //} 273 typename std::list<Point>::reverse_iterator iter = tailp_->points.rbegin(); 274 if(iter == tailp_->points.rend()) { 275 tailp_->points.push_back(point); 276 return; 277 } 278 Unit firstY = (*iter).y(); 279 Unit firstX = (*iter).x(); 280 ++iter; 281 if(iter == tailp_->points.rend()) { 282 tailp_->points.push_back(point); 283 return; 284 } 285 if((iter->y() == point.y() && firstY == point.y()) || 286 (iter->x() == point.x() && firstX == point.x())){ 287 --iter; 288 *iter = point; 289 } else { 290 tailp_->points.push_back(point); 291 } 292 } 293 294 /** 295 * @brief joins the two chains that the two active tail tails are ends of 296 * checks for closure of figure and writes out polygons appropriately 297 * returns a handle to a hole if one is closed 298 */ 299 300 template <class cT> joinChains(Point point,ActiveTail45 * at1,ActiveTail45 * at2,bool solid,cT & output)301 static inline ActiveTail45* joinChains(Point point, ActiveTail45* at1, ActiveTail45* at2, bool solid, 302 cT& output) { 303 if(at1->otherTailp_ == at2) { 304 //if(at2->otherTailp_ != at1) std::cout << "half closed error\n"; 305 //we are closing a figure 306 at1->pushPoint(point); 307 at2->pushPoint(point); 308 if(solid) { 309 //we are closing a solid figure, write to output 310 //std::cout << "test1\n"; 311 at1->copyHoles(*(at1->otherTailp_)); 312 //std::cout << "test2\n"; 313 //Polygon45WithHolesImpl<PolyLine45PolygonData> poly(polyData); 314 //std::cout << poly << "\n"; 315 //std::cout << "test3\n"; 316 typedef typename cT::value_type pType; 317 output.push_back(pType()); 318 typedef typename geometry_concept<pType>::type cType; 319 typename PolyLineByConcept<Unit, cType>::type polyData(at1); 320 assign(output.back(), polyData); 321 //std::cout << "test4\n"; 322 //std::cout << "delete " << at1->otherTailp_ << "\n"; 323 //at1->print(); 324 //at1->otherTailp_->print(); 325 delete at1->otherTailp_; 326 //at1->print(); 327 //at1->otherTailp_->print(); 328 //std::cout << "test5\n"; 329 //std::cout << "delete " << at1 << "\n"; 330 delete at1; 331 //std::cout << "test6\n"; 332 return 0; 333 } else { 334 //we are closing a hole, return the tail end active tail of the figure 335 return at1; 336 } 337 } 338 //we are not closing a figure 339 at1->pushPoint(point); 340 at1->join(at2); 341 delete at1; 342 delete at2; 343 return 0; 344 } 345 destroyContents()346 inline void destroyContents() { 347 if(otherTailp_) { 348 //std::cout << "delete p " << tailp_ << "\n"; 349 if(tailp_) delete tailp_; 350 tailp_ = 0; 351 otherTailp_->otherTailp_ = 0; 352 otherTailp_->tailp_ = 0; 353 otherTailp_ = 0; 354 } 355 for(typename std::list<ActiveTail45*>::iterator itr = holesList_.begin(); itr != holesList_.end(); ++itr) { 356 //std::cout << "delete p " << (*itr) << "\n"; 357 if(*itr) { 358 if((*itr)->otherTailp_) { 359 delete (*itr)->otherTailp_; 360 (*itr)->otherTailp_ = 0; 361 } 362 delete (*itr); 363 } 364 (*itr) = 0; 365 } 366 holesList_.clear(); 367 } 368 369 // inline void print() { 370 // std::cout << this << " " << tailp_ << " " << otherTailp_ << " " << holesList_.size() << " " << head_ << "\n"; 371 // } 372 createActiveTail45sAsPair(Point point,bool solid,ActiveTail45 * phole,bool fractureHoles)373 static inline std::pair<ActiveTail45*, ActiveTail45*> createActiveTail45sAsPair(Point point, bool solid, 374 ActiveTail45* phole, bool fractureHoles) { 375 ActiveTail45* at1 = 0; 376 ActiveTail45* at2 = 0; 377 if(phole && fractureHoles) { 378 //std::cout << "adding hole\n"; 379 at1 = phole; 380 //assert solid == false, we should be creating a corner with solid below and to the left if there was a hole 381 at2 = at1->getOtherActiveTail(); 382 at2->pushPoint(point); 383 at1->pushPoint(point); 384 } else { 385 at1 = new ActiveTail45(point, at2, solid); 386 at2 = new ActiveTail45(at1); 387 at1->otherTailp_ = at2; 388 at2->head_ = !solid; 389 if(phole) 390 at2->addHole(phole); //assert fractureHoles == false 391 } 392 return std::pair<ActiveTail45*, ActiveTail45*>(at1, at2); 393 } 394 395 }; 396 397 template <typename ct> 398 class Vertex45CountT { 399 public: 400 typedef ct count_type; Vertex45CountT()401 inline Vertex45CountT() 402 #ifndef BOOST_POLYGON_MSVC 403 : counts() 404 #endif 405 { counts[0] = counts[1] = counts[2] = counts[3] = 0; } 406 //inline Vertex45CountT(ct count) { counts[0] = counts[1] = counts[2] = counts[3] = count; } Vertex45CountT(const ct & count1,const ct & count2,const ct & count3,const ct & count4)407 inline Vertex45CountT(const ct& count1, const ct& count2, const ct& count3, 408 const ct& count4) 409 #ifndef BOOST_POLYGON_MSVC 410 : counts() 411 #endif 412 { 413 counts[0] = count1; 414 counts[1] = count2; 415 counts[2] = count3; 416 counts[3] = count4; 417 } Vertex45CountT(const Vertex45 & vertex)418 inline Vertex45CountT(const Vertex45& vertex) 419 #ifndef BOOST_POLYGON_MSVC 420 : counts() 421 #endif 422 { 423 counts[0] = counts[1] = counts[2] = counts[3] = 0; 424 (*this) += vertex; 425 } Vertex45CountT(const Vertex45CountT & count)426 inline Vertex45CountT(const Vertex45CountT& count) 427 #ifndef BOOST_POLYGON_MSVC 428 : counts() 429 #endif 430 { 431 (*this) = count; 432 } operator ==(const Vertex45CountT & count) const433 inline bool operator==(const Vertex45CountT& count) const { 434 for(unsigned int i = 0; i < 4; ++i) { 435 if(counts[i] != count.counts[i]) return false; 436 } 437 return true; 438 } operator !=(const Vertex45CountT & count) const439 inline bool operator!=(const Vertex45CountT& count) const { return !((*this) == count); } operator =(ct count)440 inline Vertex45CountT& operator=(ct count) { 441 counts[0] = counts[1] = counts[2] = counts[3] = count; return *this; } operator =(const Vertex45CountT & count)442 inline Vertex45CountT& operator=(const Vertex45CountT& count) { 443 for(unsigned int i = 0; i < 4; ++i) { 444 counts[i] = count.counts[i]; 445 } 446 return *this; 447 } operator [](int index)448 inline ct& operator[](int index) { return counts[index]; } operator [](int index) const449 inline ct operator[](int index) const {return counts[index]; } operator +=(const Vertex45CountT & count)450 inline Vertex45CountT& operator+=(const Vertex45CountT& count){ 451 for(unsigned int i = 0; i < 4; ++i) { 452 counts[i] += count.counts[i]; 453 } 454 return *this; 455 } operator -=(const Vertex45CountT & count)456 inline Vertex45CountT& operator-=(const Vertex45CountT& count){ 457 for(unsigned int i = 0; i < 4; ++i) { 458 counts[i] -= count.counts[i]; 459 } 460 return *this; 461 } operator +(const Vertex45CountT & count) const462 inline Vertex45CountT operator+(const Vertex45CountT& count) const { 463 return Vertex45CountT(*this)+=count; 464 } operator -(const Vertex45CountT & count) const465 inline Vertex45CountT operator-(const Vertex45CountT& count) const { 466 return Vertex45CountT(*this)-=count; 467 } invert() const468 inline Vertex45CountT invert() const { 469 return Vertex45CountT()-=(*this); 470 } operator +=(const Vertex45 & element)471 inline Vertex45CountT& operator+=(const Vertex45& element){ 472 counts[element.rise+1] += element.count; return *this; 473 } is_45() const474 inline bool is_45() const { 475 return counts[0] != 0 || counts[2] != 0; 476 } 477 private: 478 ct counts[4]; 479 }; 480 481 typedef Vertex45CountT<int> Vertex45Count; 482 483 // inline std::ostream& operator<< (std::ostream& o, const Vertex45Count& c) { 484 // o << c[0] << ", " << c[1] << ", "; 485 // o << c[2] << ", " << c[3]; 486 // return o; 487 // } 488 489 template <typename ct> 490 class Vertex45CompactT { 491 public: 492 Point pt; 493 ct count; 494 typedef typename boolean_op_45<Unit>::template Vertex45T<typename ct::count_type> Vertex45T; Vertex45CompactT()495 inline Vertex45CompactT() : pt(), count() {} Vertex45CompactT(const Point & point,int riseIn,int countIn)496 inline Vertex45CompactT(const Point& point, int riseIn, int countIn) : pt(point), count() { 497 count[riseIn+1] = countIn; 498 } 499 template <typename ct2> Vertex45CompactT(const typename boolean_op_45<Unit>::template Vertex45T<ct2> & vertex)500 inline Vertex45CompactT(const typename boolean_op_45<Unit>::template Vertex45T<ct2>& vertex) : pt(vertex.pt), count() { 501 count[vertex.rise+1] = vertex.count; 502 } Vertex45CompactT(const Vertex45CompactT & vertex)503 inline Vertex45CompactT(const Vertex45CompactT& vertex) : pt(vertex.pt), count(vertex.count) {} operator =(const Vertex45CompactT & vertex)504 inline Vertex45CompactT& operator=(const Vertex45CompactT& vertex){ 505 pt = vertex.pt; count = vertex.count; return *this; } operator ==(const Vertex45CompactT & vertex) const506 inline bool operator==(const Vertex45CompactT& vertex) const { 507 return pt == vertex.pt && count == vertex.count; } operator !=(const Vertex45CompactT & vertex) const508 inline bool operator!=(const Vertex45CompactT& vertex) const { return !((*this) == vertex); } operator <(const Vertex45CompactT & vertex) const509 inline bool operator<(const Vertex45CompactT& vertex) const { 510 if(pt.x() < vertex.pt.x()) return true; 511 if(pt.x() == vertex.pt.x()) { 512 return pt.y() < vertex.pt.y(); 513 } 514 return false; 515 } operator >(const Vertex45CompactT & vertex) const516 inline bool operator>(const Vertex45CompactT& vertex) const { return vertex < (*this); } operator <=(const Vertex45CompactT & vertex) const517 inline bool operator<=(const Vertex45CompactT& vertex) const { return !((*this) > vertex); } operator >=(const Vertex45CompactT & vertex) const518 inline bool operator>=(const Vertex45CompactT& vertex) const { return !((*this) < vertex); } haveVertex45(int index) const519 inline bool haveVertex45(int index) const { return count[index]; } operator [](int index) const520 inline Vertex45T operator[](int index) const { 521 return Vertex45T(pt, index-1, count[index]); } 522 }; 523 524 typedef Vertex45CompactT<Vertex45Count> Vertex45Compact; 525 526 // inline std::ostream& operator<< (std::ostream& o, const Vertex45Compact& c) { 527 // o << c.pt << ", " << c.count; 528 // return o; 529 // } 530 531 class Polygon45Formation { 532 private: 533 //definitions 534 typedef std::map<Vertex45, ActiveTail45*, lessVertex45> Polygon45FormationData; 535 typedef typename Polygon45FormationData::iterator iterator; 536 typedef typename Polygon45FormationData::const_iterator const_iterator; 537 538 //data 539 Polygon45FormationData scanData_; 540 Unit x_; 541 int justBefore_; 542 int fractureHoles_; 543 public: Polygon45Formation()544 inline Polygon45Formation() : scanData_(), x_((std::numeric_limits<Unit>::min)()), justBefore_(false), fractureHoles_(0) { 545 lessVertex45 lessElm(&x_, &justBefore_); 546 scanData_ = Polygon45FormationData(lessElm); 547 } Polygon45Formation(bool fractureHoles)548 inline Polygon45Formation(bool fractureHoles) : scanData_(), x_((std::numeric_limits<Unit>::min)()), justBefore_(false), fractureHoles_(fractureHoles) { 549 lessVertex45 lessElm(&x_, &justBefore_); 550 scanData_ = Polygon45FormationData(lessElm); 551 } Polygon45Formation(const Polygon45Formation & that)552 inline Polygon45Formation(const Polygon45Formation& that) : 553 scanData_(), x_((std::numeric_limits<Unit>::min)()), justBefore_(false), fractureHoles_(0) { (*this) = that; } operator =(const Polygon45Formation & that)554 inline Polygon45Formation& operator=(const Polygon45Formation& that) { 555 x_ = that.x_; 556 justBefore_ = that.justBefore_; 557 fractureHoles_ = that.fractureHoles_; 558 lessVertex45 lessElm(&x_, &justBefore_); 559 scanData_ = Polygon45FormationData(lessElm); 560 for(const_iterator itr = that.scanData_.begin(); itr != that.scanData_.end(); ++itr){ 561 scanData_.insert(scanData_.end(), *itr); 562 } 563 return *this; 564 } 565 566 //cT is an output container of Polygon45 or Polygon45WithHoles 567 //iT is an iterator over Vertex45 elements 568 //inputBegin - inputEnd is a range of sorted iT that represents 569 //one or more scanline stops worth of data 570 template <class cT, class iT> scan(cT & output,iT inputBegin,iT inputEnd)571 void scan(cT& output, iT inputBegin, iT inputEnd) { 572 //std::cout << "1\n"; 573 while(inputBegin != inputEnd) { 574 //std::cout << "2\n"; 575 x_ = (*inputBegin).pt.x(); 576 //std::cout << "SCAN FORMATION " << x_ << "\n"; 577 //std::cout << "x_ = " << x_ << "\n"; 578 //std::cout << "scan line size: " << scanData_.size() << "\n"; 579 inputBegin = processEvent_(output, inputBegin, inputEnd); 580 } 581 } 582 583 private: 584 //functions 585 template <class cT, class cT2> processPoint_(cT & output,cT2 & elements,Point point,Vertex45Count & counts,ActiveTail45 ** tails,Vertex45Count & incoming)586 inline std::pair<int, ActiveTail45*> processPoint_(cT& output, cT2& elements, Point point, 587 Vertex45Count& counts, ActiveTail45** tails, Vertex45Count& incoming) { 588 //std::cout << point << "\n"; 589 //std::cout << counts[0] << " "; 590 //std::cout << counts[1] << " "; 591 //std::cout << counts[2] << " "; 592 //std::cout << counts[3] << "\n"; 593 //std::cout << incoming[0] << " "; 594 //std::cout << incoming[1] << " "; 595 //std::cout << incoming[2] << " "; 596 //std::cout << incoming[3] << "\n"; 597 //join any closing solid corners 598 ActiveTail45* returnValue = 0; 599 int returnCount = 0; 600 for(int i = 0; i < 3; ++i) { 601 //std::cout << i << "\n"; 602 if(counts[i] == -1) { 603 //std::cout << "fixed i\n"; 604 for(int j = i + 1; j < 4; ++j) { 605 //std::cout << j << "\n"; 606 if(counts[j]) { 607 if(counts[j] == 1) { 608 //std::cout << "case1: " << i << " " << j << "\n"; 609 //if a figure is closed it will be written out by this function to output 610 ActiveTail45::joinChains(point, tails[i], tails[j], true, output); 611 counts[i] = 0; 612 counts[j] = 0; 613 tails[i] = 0; 614 tails[j] = 0; 615 } 616 break; 617 } 618 } 619 } 620 } 621 //find any pairs of incoming edges that need to create pair for leading solid 622 //std::cout << "checking case2\n"; 623 for(int i = 0; i < 3; ++i) { 624 //std::cout << i << "\n"; 625 if(incoming[i] == 1) { 626 //std::cout << "fixed i\n"; 627 for(int j = i + 1; j < 4; ++j) { 628 //std::cout << j << "\n"; 629 if(incoming[j]) { 630 if(incoming[j] == -1) { 631 //std::cout << "case2: " << i << " " << j << "\n"; 632 //std::cout << "creating active tail pair\n"; 633 std::pair<ActiveTail45*, ActiveTail45*> tailPair = 634 ActiveTail45::createActiveTail45sAsPair(point, true, 0, fractureHoles_ != 0); 635 //tailPair.first->print(); 636 //tailPair.second->print(); 637 if(j == 3) { 638 //vertical active tail becomes return value 639 returnValue = tailPair.first; 640 returnCount = 1; 641 } else { 642 Vertex45 vertex(point, i -1, incoming[i]); 643 //std::cout << "new element " << j-1 << " " << -1 << "\n"; 644 elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, j -1, -1), tailPair.first)); 645 } 646 //std::cout << "new element " << i-1 << " " << 1 << "\n"; 647 elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, i -1, 1), tailPair.second)); 648 incoming[i] = 0; 649 incoming[j] = 0; 650 } 651 break; 652 } 653 } 654 } 655 } 656 657 //find any active tail that needs to pass through to an incoming edge 658 //we expect to find no more than two pass through 659 660 //find pass through with solid on top 661 //std::cout << "checking case 3\n"; 662 for(int i = 0; i < 4; ++i) { 663 //std::cout << i << "\n"; 664 if(counts[i] != 0) { 665 if(counts[i] == 1) { 666 //std::cout << "fixed i\n"; 667 for(int j = 3; j >= 0; --j) { 668 if(incoming[j] != 0) { 669 if(incoming[j] == 1) { 670 //std::cout << "case3: " << i << " " << j << "\n"; 671 //tails[i]->print(); 672 //pass through solid on top 673 tails[i]->pushPoint(point); 674 //std::cout << "after push\n"; 675 if(j == 3) { 676 returnValue = tails[i]; 677 returnCount = -1; 678 } else { 679 elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, j -1, incoming[j]), tails[i])); 680 } 681 tails[i] = 0; 682 counts[i] = 0; 683 incoming[j] = 0; 684 } 685 break; 686 } 687 } 688 } 689 break; 690 } 691 } 692 //std::cout << "checking case 4\n"; 693 //find pass through with solid on bottom 694 for(int i = 3; i >= 0; --i) { 695 if(counts[i] != 0) { 696 if(counts[i] == -1) { 697 for(int j = 0; j < 4; ++j) { 698 if(incoming[j] != 0) { 699 if(incoming[j] == -1) { 700 //std::cout << "case4: " << i << " " << j << "\n"; 701 //pass through solid on bottom 702 tails[i]->pushPoint(point); 703 if(j == 3) { 704 returnValue = tails[i]; 705 returnCount = 1; 706 } else { 707 //std::cout << "new element " << j-1 << " " << incoming[j] << "\n"; 708 elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, j -1, incoming[j]), tails[i])); 709 } 710 tails[i] = 0; 711 counts[i] = 0; 712 incoming[j] = 0; 713 } 714 break; 715 } 716 } 717 } 718 break; 719 } 720 } 721 722 //find the end of a hole or the beginning of a hole 723 724 //find end of a hole 725 for(int i = 0; i < 3; ++i) { 726 if(counts[i] != 0) { 727 for(int j = i+1; j < 4; ++j) { 728 if(counts[j] != 0) { 729 //std::cout << "case5: " << i << " " << j << "\n"; 730 //we are ending a hole and may potentially close a figure and have to handle the hole 731 returnValue = ActiveTail45::joinChains(point, tails[i], tails[j], false, output); 732 tails[i] = 0; 733 tails[j] = 0; 734 counts[i] = 0; 735 counts[j] = 0; 736 break; 737 } 738 } 739 break; 740 } 741 } 742 //find beginning of a hole 743 for(int i = 0; i < 3; ++i) { 744 if(incoming[i] != 0) { 745 for(int j = i+1; j < 4; ++j) { 746 if(incoming[j] != 0) { 747 //std::cout << "case6: " << i << " " << j << "\n"; 748 //we are beginning a empty space 749 ActiveTail45* holep = 0; 750 if(counts[3] == 0) holep = tails[3]; 751 std::pair<ActiveTail45*, ActiveTail45*> tailPair = 752 ActiveTail45::createActiveTail45sAsPair(point, false, holep, fractureHoles_ != 0); 753 if(j == 3) { 754 returnValue = tailPair.first; 755 returnCount = -1; 756 } else { 757 //std::cout << "new element " << j-1 << " " << incoming[j] << "\n"; 758 elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, j -1, incoming[j]), tailPair.first)); 759 } 760 //std::cout << "new element " << i-1 << " " << incoming[i] << "\n"; 761 elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, i -1, incoming[i]), tailPair.second)); 762 incoming[i] = 0; 763 incoming[j] = 0; 764 break; 765 } 766 } 767 break; 768 } 769 } 770 //assert that tails, counts and incoming are all null 771 return std::pair<int, ActiveTail45*>(returnCount, returnValue); 772 } 773 774 template <class cT, class iT> processEvent_(cT & output,iT inputBegin,iT inputEnd)775 inline iT processEvent_(cT& output, iT inputBegin, iT inputEnd) { 776 //std::cout << "processEvent_\n"; 777 justBefore_ = true; 778 //collect up all elements from the tree that are at the y 779 //values of events in the input queue 780 //create vector of new elements to add into tree 781 ActiveTail45* verticalTail = 0; 782 int verticalCount = 0; 783 iT currentIter = inputBegin; 784 std::vector<iterator> elementIters; 785 std::vector<std::pair<Vertex45, ActiveTail45*> > elements; 786 while(currentIter != inputEnd && currentIter->pt.x() == x_) { 787 //std::cout << "loop\n"; 788 Unit currentY = (*currentIter).pt.y(); 789 iterator iter = lookUp_(currentY); 790 //int counts[4] = {0, 0, 0, 0}; 791 Vertex45Count counts; 792 ActiveTail45* tails[4] = {0, 0, 0, verticalTail}; 793 //std::cout << "finding elements in tree\n"; 794 while(iter != scanData_.end() && 795 iter->first.evalAtX(x_) == currentY) { 796 //std::cout << "loop2\n"; 797 elementIters.push_back(iter); 798 int index = iter->first.rise + 1; 799 //std::cout << index << " " << iter->first.count << "\n"; 800 counts[index] = iter->first.count; 801 tails[index] = iter->second; 802 ++iter; 803 } 804 //int incoming[4] = {0, 0, 0, 0}; 805 Vertex45Count incoming; 806 //std::cout << "aggregating\n"; 807 do { 808 //std::cout << "loop3\n"; 809 Vertex45Compact currentVertex(*currentIter); 810 incoming += currentVertex.count; 811 ++currentIter; 812 } while(currentIter != inputEnd && currentIter->pt.y() == currentY && 813 currentIter->pt.x() == x_); 814 //now counts and tails have the data from the left and 815 //incoming has the data from the right at this point 816 //cancel out any end points 817 //std::cout << counts[0] << " "; 818 //std::cout << counts[1] << " "; 819 //std::cout << counts[2] << " "; 820 //std::cout << counts[3] << "\n"; 821 //std::cout << incoming[0] << " "; 822 //std::cout << incoming[1] << " "; 823 //std::cout << incoming[2] << " "; 824 //std::cout << incoming[3] << "\n"; 825 if(verticalTail) { 826 counts[3] = -verticalCount; 827 } 828 incoming[3] *= -1; 829 for(unsigned int i = 0; i < 4; ++i) incoming[i] += counts[i]; 830 //std::cout << "calling processPoint_\n"; 831 std::pair<int, ActiveTail45*> result = processPoint_(output, elements, Point(x_, currentY), counts, tails, incoming); 832 verticalCount = result.first; 833 verticalTail = result.second; 834 //if(verticalTail) std::cout << "have vertical tail\n"; 835 //std::cout << "verticalCount: " << verticalCount << "\n"; 836 if(verticalTail && !verticalCount) { 837 //we got a hole out of the point we just processed 838 //iter is still at the next y element above the current y value in the tree 839 //std::cout << "checking whether ot handle hole\n"; 840 if(currentIter == inputEnd || 841 currentIter->pt.x() != x_ || 842 currentIter->pt.y() >= iter->first.evalAtX(x_)) { 843 //std::cout << "handle hole here\n"; 844 if(fractureHoles_) { 845 //std::cout << "fracture hole here\n"; 846 //we need to handle the hole now and not at the next input vertex 847 ActiveTail45* at = iter->second; 848 Point point(x_, iter->first.evalAtX(x_)); 849 verticalTail->getOtherActiveTail()->pushPoint(point); 850 iter->second = verticalTail->getOtherActiveTail(); 851 at->pushPoint(point); 852 verticalTail->join(at); 853 delete at; 854 delete verticalTail; 855 verticalTail = 0; 856 } else { 857 //std::cout << "push hole onto list\n"; 858 iter->second->addHole(verticalTail); 859 verticalTail = 0; 860 } 861 } 862 } 863 } 864 //std::cout << "erasing\n"; 865 //erase all elements from the tree 866 for(typename std::vector<iterator>::iterator iter = elementIters.begin(); 867 iter != elementIters.end(); ++iter) { 868 //std::cout << "erasing loop\n"; 869 scanData_.erase(*iter); 870 } 871 //switch comparison tie breaking policy 872 justBefore_ = false; 873 //add new elements into tree 874 //std::cout << "inserting\n"; 875 for(typename std::vector<std::pair<Vertex45, ActiveTail45*> >::iterator iter = elements.begin(); 876 iter != elements.end(); ++iter) { 877 //std::cout << "inserting loop\n"; 878 scanData_.insert(scanData_.end(), *iter); 879 } 880 //std::cout << "end processEvent\n"; 881 return currentIter; 882 } 883 lookUp_(Unit y)884 inline iterator lookUp_(Unit y){ 885 //if just before then we need to look from 1 not -1 886 return scanData_.lower_bound(Vertex45(Point(x_, y), -1+2*justBefore_, 0)); 887 } 888 889 }; 890 891 template <typename stream_type> testPolygon45FormationRectboost::polygon::polygon_45_formation892 static inline bool testPolygon45FormationRect(stream_type& stdcout) { 893 stdcout << "testing polygon formation\n"; 894 Polygon45Formation pf(true); 895 std::vector<Polygon45> polys; 896 std::vector<Vertex45> data; 897 data.push_back(Vertex45(Point(0, 0), 0, 1)); 898 data.push_back(Vertex45(Point(0, 0), 2, 1)); 899 data.push_back(Vertex45(Point(0, 10), 2, -1)); 900 data.push_back(Vertex45(Point(0, 10), 0, -1)); 901 data.push_back(Vertex45(Point(10, 0), 0, -1)); 902 data.push_back(Vertex45(Point(10, 0), 2, -1)); 903 data.push_back(Vertex45(Point(10, 10), 2, 1)); 904 data.push_back(Vertex45(Point(10, 10), 0, 1)); 905 polygon_sort(data.begin(), data.end()); 906 pf.scan(polys, data.begin(), data.end()); 907 stdcout << "result size: " << polys.size() << "\n"; 908 for(std::size_t i = 0; i < polys.size(); ++i) { 909 stdcout << polys[i] << "\n"; 910 } 911 stdcout << "done testing polygon formation\n"; 912 return true; 913 } 914 915 template <typename stream_type> testPolygon45FormationP1boost::polygon::polygon_45_formation916 static inline bool testPolygon45FormationP1(stream_type& stdcout) { 917 stdcout << "testing polygon formation\n"; 918 Polygon45Formation pf(true); 919 std::vector<Polygon45> polys; 920 std::vector<Vertex45> data; 921 data.push_back(Vertex45(Point(0, 0), 1, 1)); 922 data.push_back(Vertex45(Point(0, 0), 2, 1)); 923 data.push_back(Vertex45(Point(0, 10), 2, -1)); 924 data.push_back(Vertex45(Point(0, 10), 1, -1)); 925 data.push_back(Vertex45(Point(10, 10), 1, -1)); 926 data.push_back(Vertex45(Point(10, 10), 2, -1)); 927 data.push_back(Vertex45(Point(10, 20), 2, 1)); 928 data.push_back(Vertex45(Point(10, 20), 1, 1)); 929 polygon_sort(data.begin(), data.end()); 930 pf.scan(polys, data.begin(), data.end()); 931 stdcout << "result size: " << polys.size() << "\n"; 932 for(std::size_t i = 0; i < polys.size(); ++i) { 933 stdcout << polys[i] << "\n"; 934 } 935 stdcout << "done testing polygon formation\n"; 936 return true; 937 } 938 //polygon45set class 939 940 template <typename stream_type> testPolygon45FormationP2boost::polygon::polygon_45_formation941 static inline bool testPolygon45FormationP2(stream_type& stdcout) { 942 stdcout << "testing polygon formation\n"; 943 Polygon45Formation pf(true); 944 std::vector<Polygon45> polys; 945 std::vector<Vertex45> data; 946 data.push_back(Vertex45(Point(0, 0), 0, 1)); 947 data.push_back(Vertex45(Point(0, 0), 1, -1)); 948 data.push_back(Vertex45(Point(10, 0), 0, -1)); 949 data.push_back(Vertex45(Point(10, 0), 1, 1)); 950 data.push_back(Vertex45(Point(10, 10), 1, 1)); 951 data.push_back(Vertex45(Point(10, 10), 0, -1)); 952 data.push_back(Vertex45(Point(20, 10), 1, -1)); 953 data.push_back(Vertex45(Point(20, 10), 0, 1)); 954 polygon_sort(data.begin(), data.end()); 955 pf.scan(polys, data.begin(), data.end()); 956 stdcout << "result size: " << polys.size() << "\n"; 957 for(std::size_t i = 0; i < polys.size(); ++i) { 958 stdcout << polys[i] << "\n"; 959 } 960 stdcout << "done testing polygon formation\n"; 961 return true; 962 } 963 //polygon45set class 964 965 template <typename stream_type> testPolygon45FormationStar1boost::polygon::polygon_45_formation966 static inline bool testPolygon45FormationStar1(stream_type& stdcout) { 967 stdcout << "testing polygon formation\n"; 968 Polygon45Formation pf(true); 969 std::vector<Polygon45> polys; 970 std::vector<Vertex45> data; 971 // result == 0 8 -1 1 972 data.push_back(Vertex45(Point(0, 8), -1, 1)); 973 // result == 0 8 1 -1 974 data.push_back(Vertex45(Point(0, 8), 1, -1)); 975 // result == 4 0 1 1 976 data.push_back(Vertex45(Point(4, 0), 1, 1)); 977 // result == 4 0 2 1 978 data.push_back(Vertex45(Point(4, 0), 2, 1)); 979 // result == 4 4 2 -1 980 data.push_back(Vertex45(Point(4, 4), 2, -1)); 981 // result == 4 4 -1 -1 982 data.push_back(Vertex45(Point(4, 4), -1, -1)); 983 // result == 4 12 1 1 984 data.push_back(Vertex45(Point(4, 12), 1, 1)); 985 // result == 4 12 2 1 986 data.push_back(Vertex45(Point(4, 12), 2, 1)); 987 // result == 4 16 2 -1 988 data.push_back(Vertex45(Point(4, 16), 2, 1)); 989 // result == 4 16 -1 -1 990 data.push_back(Vertex45(Point(4, 16), -1, -1)); 991 // result == 6 2 1 -1 992 data.push_back(Vertex45(Point(6, 2), 1, -1)); 993 // result == 6 14 -1 1 994 data.push_back(Vertex45(Point(6, 14), -1, 1)); 995 // result == 6 2 -1 1 996 data.push_back(Vertex45(Point(6, 2), -1, 1)); 997 // result == 6 14 1 -1 998 data.push_back(Vertex45(Point(6, 14), 1, -1)); 999 // result == 8 0 -1 -1 1000 data.push_back(Vertex45(Point(8, 0), -1, -1)); 1001 // result == 8 0 2 -1 1002 data.push_back(Vertex45(Point(8, 0), 2, -1)); 1003 // result == 8 4 2 1 1004 data.push_back(Vertex45(Point(8, 4), 2, 1)); 1005 // result == 8 4 1 1 1006 data.push_back(Vertex45(Point(8, 4), 1, 1)); 1007 // result == 8 12 -1 -1 1008 data.push_back(Vertex45(Point(8, 12), -1, -1)); 1009 // result == 8 12 2 -1 1010 data.push_back(Vertex45(Point(8, 12), 2, -1)); 1011 // result == 8 16 2 1 1012 data.push_back(Vertex45(Point(8, 16), 2, 1)); 1013 // result == 8 16 1 1 1014 data.push_back(Vertex45(Point(8, 16), 1, 1)); 1015 // result == 12 8 1 -1 1016 data.push_back(Vertex45(Point(12, 8), 1, -1)); 1017 // result == 12 8 -1 1 1018 data.push_back(Vertex45(Point(12, 8), -1, 1)); 1019 polygon_sort(data.begin(), data.end()); 1020 pf.scan(polys, data.begin(), data.end()); 1021 stdcout << "result size: " << polys.size() << "\n"; 1022 for(std::size_t i = 0; i < polys.size(); ++i) { 1023 stdcout << polys[i] << "\n"; 1024 } 1025 stdcout << "done testing polygon formation\n"; 1026 return true; 1027 } 1028 1029 template <typename stream_type> testPolygon45FormationStar2boost::polygon::polygon_45_formation1030 static inline bool testPolygon45FormationStar2(stream_type& stdcout) { 1031 stdcout << "testing polygon formation\n"; 1032 Polygon45Formation pf(true); 1033 std::vector<Polygon45> polys; 1034 Scan45 scan45; 1035 std::vector<Vertex45 > result; 1036 std::vector<Scan45Vertex> vertices; 1037 //is a Rectnagle(0, 0, 10, 10); 1038 Count2 count(1, 0); 1039 Count2 ncount(-1, 0); 1040 vertices.push_back(Scan45Vertex(Point(0,4), Scan45Count(Count2(0, 0), count, ncount, Count2(0, 0)))); 1041 vertices.push_back(Scan45Vertex(Point(16,4), Scan45Count(count, ncount, Count2(0, 0), Count2(0, 0)))); 1042 vertices.push_back(Scan45Vertex(Point(8,12), Scan45Count(ncount, Count2(0, 0), count, Count2(0, 0)))); 1043 count = Count2(0, 1); 1044 ncount = count.invert(); 1045 vertices.push_back(Scan45Vertex(Point(0,8), Scan45Count(count, ncount, Count2(0, 0), Count2(0, 0)))); 1046 vertices.push_back(Scan45Vertex(Point(16,8), Scan45Count(Count2(0, 0), count, ncount, Count2(0, 0)))); 1047 vertices.push_back(Scan45Vertex(Point(8,0), Scan45Count(ncount, Count2(0, 0), count, Count2(0, 0)))); 1048 sortScan45Vector(vertices); 1049 stdcout << "scanning\n"; 1050 scan45.scan(result, vertices.begin(), vertices.end()); 1051 1052 polygon_sort(result.begin(), result.end()); 1053 pf.scan(polys, result.begin(), result.end()); 1054 stdcout << "result size: " << polys.size() << "\n"; 1055 for(std::size_t i = 0; i < polys.size(); ++i) { 1056 stdcout << polys[i] << "\n"; 1057 } 1058 stdcout << "done testing polygon formation\n"; 1059 return true; 1060 } 1061 1062 template <typename stream_type> testPolygon45FormationStarHole1boost::polygon::polygon_45_formation1063 static inline bool testPolygon45FormationStarHole1(stream_type& stdcout) { 1064 stdcout << "testing polygon formation\n"; 1065 Polygon45Formation pf(true); 1066 std::vector<Polygon45> polys; 1067 std::vector<Vertex45> data; 1068 // result == 0 8 -1 1 1069 data.push_back(Vertex45(Point(0, 8), -1, 1)); 1070 // result == 0 8 1 -1 1071 data.push_back(Vertex45(Point(0, 8), 1, -1)); 1072 // result == 4 0 1 1 1073 data.push_back(Vertex45(Point(4, 0), 1, 1)); 1074 // result == 4 0 2 1 1075 data.push_back(Vertex45(Point(4, 0), 2, 1)); 1076 // result == 4 4 2 -1 1077 data.push_back(Vertex45(Point(4, 4), 2, -1)); 1078 // result == 4 4 -1 -1 1079 data.push_back(Vertex45(Point(4, 4), -1, -1)); 1080 // result == 4 12 1 1 1081 data.push_back(Vertex45(Point(4, 12), 1, 1)); 1082 // result == 4 12 2 1 1083 data.push_back(Vertex45(Point(4, 12), 2, 1)); 1084 // result == 4 16 2 -1 1085 data.push_back(Vertex45(Point(4, 16), 2, 1)); 1086 // result == 4 16 -1 -1 1087 data.push_back(Vertex45(Point(4, 16), -1, -1)); 1088 // result == 6 2 1 -1 1089 data.push_back(Vertex45(Point(6, 2), 1, -1)); 1090 // result == 6 14 -1 1 1091 data.push_back(Vertex45(Point(6, 14), -1, 1)); 1092 // result == 6 2 -1 1 1093 data.push_back(Vertex45(Point(6, 2), -1, 1)); 1094 // result == 6 14 1 -1 1095 data.push_back(Vertex45(Point(6, 14), 1, -1)); 1096 // result == 8 0 -1 -1 1097 data.push_back(Vertex45(Point(8, 0), -1, -1)); 1098 // result == 8 0 2 -1 1099 data.push_back(Vertex45(Point(8, 0), 2, -1)); 1100 // result == 8 4 2 1 1101 data.push_back(Vertex45(Point(8, 4), 2, 1)); 1102 // result == 8 4 1 1 1103 data.push_back(Vertex45(Point(8, 4), 1, 1)); 1104 // result == 8 12 -1 -1 1105 data.push_back(Vertex45(Point(8, 12), -1, -1)); 1106 // result == 8 12 2 -1 1107 data.push_back(Vertex45(Point(8, 12), 2, -1)); 1108 // result == 8 16 2 1 1109 data.push_back(Vertex45(Point(8, 16), 2, 1)); 1110 // result == 8 16 1 1 1111 data.push_back(Vertex45(Point(8, 16), 1, 1)); 1112 // result == 12 8 1 -1 1113 data.push_back(Vertex45(Point(12, 8), 1, -1)); 1114 // result == 12 8 -1 1 1115 data.push_back(Vertex45(Point(12, 8), -1, 1)); 1116 1117 data.push_back(Vertex45(Point(6, 4), 1, -1)); 1118 data.push_back(Vertex45(Point(6, 4), 2, -1)); 1119 data.push_back(Vertex45(Point(6, 8), -1, 1)); 1120 data.push_back(Vertex45(Point(6, 8), 2, 1)); 1121 data.push_back(Vertex45(Point(8, 6), -1, -1)); 1122 data.push_back(Vertex45(Point(8, 6), 1, 1)); 1123 1124 polygon_sort(data.begin(), data.end()); 1125 pf.scan(polys, data.begin(), data.end()); 1126 stdcout << "result size: " << polys.size() << "\n"; 1127 for(std::size_t i = 0; i < polys.size(); ++i) { 1128 stdcout << polys[i] << "\n"; 1129 } 1130 stdcout << "done testing polygon formation\n"; 1131 return true; 1132 } 1133 1134 template <typename stream_type> testPolygon45FormationStarHole2boost::polygon::polygon_45_formation1135 static inline bool testPolygon45FormationStarHole2(stream_type& stdcout) { 1136 stdcout << "testing polygon formation\n"; 1137 Polygon45Formation pf(false); 1138 std::vector<Polygon45WithHoles> polys; 1139 std::vector<Vertex45> data; 1140 // result == 0 8 -1 1 1141 data.push_back(Vertex45(Point(0, 8), -1, 1)); 1142 // result == 0 8 1 -1 1143 data.push_back(Vertex45(Point(0, 8), 1, -1)); 1144 // result == 4 0 1 1 1145 data.push_back(Vertex45(Point(4, 0), 1, 1)); 1146 // result == 4 0 2 1 1147 data.push_back(Vertex45(Point(4, 0), 2, 1)); 1148 // result == 4 4 2 -1 1149 data.push_back(Vertex45(Point(4, 4), 2, -1)); 1150 // result == 4 4 -1 -1 1151 data.push_back(Vertex45(Point(4, 4), -1, -1)); 1152 // result == 4 12 1 1 1153 data.push_back(Vertex45(Point(4, 12), 1, 1)); 1154 // result == 4 12 2 1 1155 data.push_back(Vertex45(Point(4, 12), 2, 1)); 1156 // result == 4 16 2 -1 1157 data.push_back(Vertex45(Point(4, 16), 2, 1)); 1158 // result == 4 16 -1 -1 1159 data.push_back(Vertex45(Point(4, 16), -1, -1)); 1160 // result == 6 2 1 -1 1161 data.push_back(Vertex45(Point(6, 2), 1, -1)); 1162 // result == 6 14 -1 1 1163 data.push_back(Vertex45(Point(6, 14), -1, 1)); 1164 // result == 6 2 -1 1 1165 data.push_back(Vertex45(Point(6, 2), -1, 1)); 1166 // result == 6 14 1 -1 1167 data.push_back(Vertex45(Point(6, 14), 1, -1)); 1168 // result == 8 0 -1 -1 1169 data.push_back(Vertex45(Point(8, 0), -1, -1)); 1170 // result == 8 0 2 -1 1171 data.push_back(Vertex45(Point(8, 0), 2, -1)); 1172 // result == 8 4 2 1 1173 data.push_back(Vertex45(Point(8, 4), 2, 1)); 1174 // result == 8 4 1 1 1175 data.push_back(Vertex45(Point(8, 4), 1, 1)); 1176 // result == 8 12 -1 -1 1177 data.push_back(Vertex45(Point(8, 12), -1, -1)); 1178 // result == 8 12 2 -1 1179 data.push_back(Vertex45(Point(8, 12), 2, -1)); 1180 // result == 8 16 2 1 1181 data.push_back(Vertex45(Point(8, 16), 2, 1)); 1182 // result == 8 16 1 1 1183 data.push_back(Vertex45(Point(8, 16), 1, 1)); 1184 // result == 12 8 1 -1 1185 data.push_back(Vertex45(Point(12, 8), 1, -1)); 1186 // result == 12 8 -1 1 1187 data.push_back(Vertex45(Point(12, 8), -1, 1)); 1188 1189 data.push_back(Vertex45(Point(6, 4), 1, -1)); 1190 data.push_back(Vertex45(Point(6, 4), 2, -1)); 1191 data.push_back(Vertex45(Point(6, 12), -1, 1)); 1192 data.push_back(Vertex45(Point(6, 12), 2, 1)); 1193 data.push_back(Vertex45(Point(10, 8), -1, -1)); 1194 data.push_back(Vertex45(Point(10, 8), 1, 1)); 1195 1196 polygon_sort(data.begin(), data.end()); 1197 pf.scan(polys, data.begin(), data.end()); 1198 stdcout << "result size: " << polys.size() << "\n"; 1199 for(std::size_t i = 0; i < polys.size(); ++i) { 1200 stdcout << polys[i] << "\n"; 1201 } 1202 stdcout << "done testing polygon formation\n"; 1203 return true; 1204 } 1205 1206 template <typename stream_type> testPolygon45Formationboost::polygon::polygon_45_formation1207 static inline bool testPolygon45Formation(stream_type& stdcout) { 1208 stdcout << "testing polygon formation\n"; 1209 Polygon45Formation pf(false); 1210 std::vector<Polygon45WithHoles> polys; 1211 std::vector<Vertex45> data; 1212 1213 data.push_back(Vertex45(Point(0, 0), 0, 1)); 1214 data.push_back(Vertex45(Point(0, 0), 2, 1)); 1215 data.push_back(Vertex45(Point(0, 100), 2, -1)); 1216 data.push_back(Vertex45(Point(0, 100), 0, -1)); 1217 data.push_back(Vertex45(Point(100, 0), 0, -1)); 1218 data.push_back(Vertex45(Point(100, 0), 2, -1)); 1219 data.push_back(Vertex45(Point(100, 100), 2, 1)); 1220 data.push_back(Vertex45(Point(100, 100), 0, 1)); 1221 1222 data.push_back(Vertex45(Point(2, 2), 0, -1)); 1223 data.push_back(Vertex45(Point(2, 2), 2, -1)); 1224 data.push_back(Vertex45(Point(2, 10), 2, 1)); 1225 data.push_back(Vertex45(Point(2, 10), 0, 1)); 1226 data.push_back(Vertex45(Point(10, 2), 0, 1)); 1227 data.push_back(Vertex45(Point(10, 2), 2, 1)); 1228 data.push_back(Vertex45(Point(10, 10), 2, -1)); 1229 data.push_back(Vertex45(Point(10, 10), 0, -1)); 1230 1231 data.push_back(Vertex45(Point(2, 12), 0, -1)); 1232 data.push_back(Vertex45(Point(2, 12), 2, -1)); 1233 data.push_back(Vertex45(Point(2, 22), 2, 1)); 1234 data.push_back(Vertex45(Point(2, 22), 0, 1)); 1235 data.push_back(Vertex45(Point(10, 12), 0, 1)); 1236 data.push_back(Vertex45(Point(10, 12), 2, 1)); 1237 data.push_back(Vertex45(Point(10, 22), 2, -1)); 1238 data.push_back(Vertex45(Point(10, 22), 0, -1)); 1239 1240 polygon_sort(data.begin(), data.end()); 1241 pf.scan(polys, data.begin(), data.end()); 1242 stdcout << "result size: " << polys.size() << "\n"; 1243 for(std::size_t i = 0; i < polys.size(); ++i) { 1244 stdcout << polys[i] << "\n"; 1245 } 1246 stdcout << "done testing polygon formation\n"; 1247 return true; 1248 } 1249 1250 1251 class Polygon45Tiling { 1252 private: 1253 //definitions 1254 typedef std::map<Vertex45, ActiveTail45*, lessVertex45> Polygon45FormationData; 1255 typedef typename Polygon45FormationData::iterator iterator; 1256 typedef typename Polygon45FormationData::const_iterator const_iterator; 1257 1258 //data 1259 Polygon45FormationData scanData_; 1260 Unit x_; 1261 int justBefore_; 1262 public: Polygon45Tiling()1263 inline Polygon45Tiling() : scanData_(), x_((std::numeric_limits<Unit>::min)()), justBefore_(false) { 1264 lessVertex45 lessElm(&x_, &justBefore_); 1265 scanData_ = Polygon45FormationData(lessElm); 1266 } Polygon45Tiling(const Polygon45Tiling & that)1267 inline Polygon45Tiling(const Polygon45Tiling& that) : 1268 scanData_(), x_((std::numeric_limits<Unit>::min)()), justBefore_(false) { (*this) = that; } operator =(const Polygon45Tiling & that)1269 inline Polygon45Tiling& operator=(const Polygon45Tiling& that) { 1270 x_ = that.x_; 1271 justBefore_ = that.justBefore_; 1272 lessVertex45 lessElm(&x_, &justBefore_); 1273 scanData_ = Polygon45FormationData(lessElm); 1274 for(const_iterator itr = that.scanData_.begin(); itr != that.scanData_.end(); ++itr){ 1275 scanData_.insert(scanData_.end(), *itr); 1276 } 1277 return *this; 1278 } 1279 1280 //cT is an output container of Polygon45 or Polygon45WithHoles 1281 //iT is an iterator over Vertex45 elements 1282 //inputBegin - inputEnd is a range of sorted iT that represents 1283 //one or more scanline stops worth of data 1284 template <class cT, class iT> scan(cT & output,iT inputBegin,iT inputEnd)1285 void scan(cT& output, iT inputBegin, iT inputEnd) { 1286 //std::cout << "1\n"; 1287 while(inputBegin != inputEnd) { 1288 //std::cout << "2\n"; 1289 x_ = (*inputBegin).pt.x(); 1290 //std::cout << "SCAN FORMATION " << x_ << "\n"; 1291 //std::cout << "x_ = " << x_ << "\n"; 1292 //std::cout << "scan line size: " << scanData_.size() << "\n"; 1293 inputBegin = processEvent_(output, inputBegin, inputEnd); 1294 } 1295 } 1296 1297 private: 1298 //functions 1299 getVerticalPair_(std::pair<ActiveTail45 *,ActiveTail45 * > & verticalPair,iterator previter)1300 inline void getVerticalPair_(std::pair<ActiveTail45*, ActiveTail45*>& verticalPair, 1301 iterator previter) { 1302 ActiveTail45* iterTail = (*previter).second; 1303 Point prevPoint(x_, previter->first.evalAtX(x_)); 1304 iterTail->pushPoint(prevPoint); 1305 std::pair<ActiveTail45*, ActiveTail45*> tailPair = 1306 ActiveTail45::createActiveTail45sAsPair(prevPoint, true, 0, false); 1307 verticalPair.first = iterTail; 1308 verticalPair.second = tailPair.first; 1309 (*previter).second = tailPair.second; 1310 } 1311 1312 template <class cT, class cT2> processPoint_(cT & output,cT2 & elements,std::pair<ActiveTail45 *,ActiveTail45 * > & verticalPair,iterator previter,Point point,Vertex45Count & counts,ActiveTail45 ** tails,Vertex45Count & incoming)1313 inline std::pair<int, ActiveTail45*> processPoint_(cT& output, cT2& elements, 1314 std::pair<ActiveTail45*, ActiveTail45*>& verticalPair, 1315 iterator previter, Point point, 1316 Vertex45Count& counts, ActiveTail45** tails, Vertex45Count& incoming) { 1317 //std::cout << point << "\n"; 1318 //std::cout << counts[0] << " "; 1319 //std::cout << counts[1] << " "; 1320 //std::cout << counts[2] << " "; 1321 //std::cout << counts[3] << "\n"; 1322 //std::cout << incoming[0] << " "; 1323 //std::cout << incoming[1] << " "; 1324 //std::cout << incoming[2] << " "; 1325 //std::cout << incoming[3] << "\n"; 1326 //join any closing solid corners 1327 ActiveTail45* returnValue = 0; 1328 std::pair<ActiveTail45*, ActiveTail45*> verticalPairOut; 1329 verticalPairOut.first = 0; 1330 verticalPairOut.second = 0; 1331 int returnCount = 0; 1332 for(int i = 0; i < 3; ++i) { 1333 //std::cout << i << "\n"; 1334 if(counts[i] == -1) { 1335 //std::cout << "fixed i\n"; 1336 for(int j = i + 1; j < 4; ++j) { 1337 //std::cout << j << "\n"; 1338 if(counts[j]) { 1339 if(counts[j] == 1) { 1340 //std::cout << "case1: " << i << " " << j << "\n"; 1341 //if a figure is closed it will be written out by this function to output 1342 ActiveTail45::joinChains(point, tails[i], tails[j], true, output); 1343 counts[i] = 0; 1344 counts[j] = 0; 1345 tails[i] = 0; 1346 tails[j] = 0; 1347 } 1348 break; 1349 } 1350 } 1351 } 1352 } 1353 //find any pairs of incoming edges that need to create pair for leading solid 1354 //std::cout << "checking case2\n"; 1355 for(int i = 0; i < 3; ++i) { 1356 //std::cout << i << "\n"; 1357 if(incoming[i] == 1) { 1358 //std::cout << "fixed i\n"; 1359 for(int j = i + 1; j < 4; ++j) { 1360 //std::cout << j << "\n"; 1361 if(incoming[j]) { 1362 if(incoming[j] == -1) { 1363 //std::cout << "case2: " << i << " " << j << "\n"; 1364 //std::cout << "creating active tail pair\n"; 1365 std::pair<ActiveTail45*, ActiveTail45*> tailPair = 1366 ActiveTail45::createActiveTail45sAsPair(point, true, 0, false); 1367 //tailPair.first->print(); 1368 //tailPair.second->print(); 1369 if(j == 3) { 1370 //vertical active tail becomes return value 1371 returnValue = tailPair.first; 1372 returnCount = 1; 1373 } else { 1374 Vertex45 vertex(point, i -1, incoming[i]); 1375 //std::cout << "new element " << j-1 << " " << -1 << "\n"; 1376 elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, j -1, -1), tailPair.first)); 1377 } 1378 //std::cout << "new element " << i-1 << " " << 1 << "\n"; 1379 elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, i -1, 1), tailPair.second)); 1380 incoming[i] = 0; 1381 incoming[j] = 0; 1382 } 1383 break; 1384 } 1385 } 1386 } 1387 } 1388 1389 //find any active tail that needs to pass through to an incoming edge 1390 //we expect to find no more than two pass through 1391 1392 //find pass through with solid on top 1393 //std::cout << "checking case 3\n"; 1394 for(int i = 0; i < 4; ++i) { 1395 //std::cout << i << "\n"; 1396 if(counts[i] != 0) { 1397 if(counts[i] == 1) { 1398 //std::cout << "fixed i\n"; 1399 for(int j = 3; j >= 0; --j) { 1400 if(incoming[j] != 0) { 1401 if(incoming[j] == 1) { 1402 //std::cout << "case3: " << i << " " << j << "\n"; 1403 //tails[i]->print(); 1404 //pass through solid on top 1405 if(i != 3) 1406 tails[i]->pushPoint(point); 1407 //std::cout << "after push\n"; 1408 if(j == 3) { 1409 returnValue = tails[i]; 1410 returnCount = -1; 1411 } else { 1412 verticalPairOut.first = tails[i]; 1413 std::pair<ActiveTail45*, ActiveTail45*> tailPair = 1414 ActiveTail45::createActiveTail45sAsPair(point, true, 0, false); 1415 verticalPairOut.second = tailPair.first; 1416 elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, j -1, incoming[j]), 1417 tailPair.second)); 1418 } 1419 tails[i] = 0; 1420 counts[i] = 0; 1421 incoming[j] = 0; 1422 } 1423 break; 1424 } 1425 } 1426 } 1427 break; 1428 } 1429 } 1430 //std::cout << "checking case 4\n"; 1431 //find pass through with solid on bottom 1432 for(int i = 3; i >= 0; --i) { 1433 if(counts[i] != 0) { 1434 if(counts[i] == -1) { 1435 for(int j = 0; j < 4; ++j) { 1436 if(incoming[j] != 0) { 1437 if(incoming[j] == -1) { 1438 //std::cout << "case4: " << i << " " << j << "\n"; 1439 //pass through solid on bottom 1440 if(i == 3) { 1441 //std::cout << "new element " << j-1 << " " << incoming[j] << "\n"; 1442 if(j == 3) { 1443 returnValue = tails[i]; 1444 returnCount = 1; 1445 } else { 1446 tails[i]->pushPoint(point); 1447 elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, j -1, incoming[j]), tails[i])); 1448 } 1449 } else if(j == 3) { 1450 if(verticalPair.first == 0) { 1451 getVerticalPair_(verticalPair, previter); 1452 } 1453 ActiveTail45::joinChains(point, tails[i], verticalPair.first, true, output); 1454 returnValue = verticalPair.second; 1455 returnCount = 1; 1456 } else { 1457 if(verticalPair.first == 0) { 1458 getVerticalPair_(verticalPair, previter); 1459 } 1460 ActiveTail45::joinChains(point, tails[i], verticalPair.first, true, output); 1461 verticalPair.second->pushPoint(point); 1462 elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, j -1, incoming[j]), 1463 verticalPair.second)); 1464 } 1465 tails[i] = 0; 1466 counts[i] = 0; 1467 incoming[j] = 0; 1468 } 1469 break; 1470 } 1471 } 1472 } 1473 break; 1474 } 1475 } 1476 1477 //find the end of a hole or the beginning of a hole 1478 1479 //find end of a hole 1480 for(int i = 0; i < 3; ++i) { 1481 if(counts[i] != 0) { 1482 for(int j = i+1; j < 4; ++j) { 1483 if(counts[j] != 0) { 1484 //std::cout << "case5: " << i << " " << j << "\n"; 1485 //we are ending a hole and may potentially close a figure and have to handle the hole 1486 tails[i]->pushPoint(point); 1487 verticalPairOut.first = tails[i]; 1488 if(j == 3) { 1489 verticalPairOut.second = tails[j]; 1490 } else { 1491 if(verticalPair.first == 0) { 1492 getVerticalPair_(verticalPair, previter); 1493 } 1494 ActiveTail45::joinChains(point, tails[j], verticalPair.first, true, output); 1495 verticalPairOut.second = verticalPair.second; 1496 } 1497 tails[i] = 0; 1498 tails[j] = 0; 1499 counts[i] = 0; 1500 counts[j] = 0; 1501 break; 1502 } 1503 } 1504 break; 1505 } 1506 } 1507 //find beginning of a hole 1508 for(int i = 0; i < 3; ++i) { 1509 if(incoming[i] != 0) { 1510 for(int j = i+1; j < 4; ++j) { 1511 if(incoming[j] != 0) { 1512 //std::cout << "case6: " << i << " " << j << "\n"; 1513 //we are beginning a empty space 1514 if(verticalPair.first == 0) { 1515 getVerticalPair_(verticalPair, previter); 1516 } 1517 verticalPair.second->pushPoint(point); 1518 if(j == 3) { 1519 returnValue = verticalPair.first; 1520 returnCount = -1; 1521 } else { 1522 std::pair<ActiveTail45*, ActiveTail45*> tailPair = 1523 ActiveTail45::createActiveTail45sAsPair(point, true, 0, false); 1524 //std::cout << "new element " << j-1 << " " << incoming[j] << "\n"; 1525 elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, j -1, incoming[j]), tailPair.second)); 1526 verticalPairOut.second = tailPair.first; 1527 verticalPairOut.first = verticalPair.first; 1528 } 1529 //std::cout << "new element " << i-1 << " " << incoming[i] << "\n"; 1530 elements.push_back(std::pair<Vertex45, ActiveTail45*>(Vertex45(point, i -1, incoming[i]), verticalPair.second)); 1531 incoming[i] = 0; 1532 incoming[j] = 0; 1533 break; 1534 } 1535 } 1536 break; 1537 } 1538 } 1539 verticalPair = verticalPairOut; 1540 //assert that verticalPair is either both null, or neither null 1541 //assert that returnValue is null if verticalPair is not null 1542 //assert that tails, counts and incoming are all null 1543 return std::pair<int, ActiveTail45*>(returnCount, returnValue); 1544 } 1545 1546 template <class cT, class iT> processEvent_(cT & output,iT inputBegin,iT inputEnd)1547 inline iT processEvent_(cT& output, iT inputBegin, iT inputEnd) { 1548 //std::cout << "processEvent_\n"; 1549 justBefore_ = true; 1550 //collect up all elements from the tree that are at the y 1551 //values of events in the input queue 1552 //create vector of new elements to add into tree 1553 ActiveTail45* verticalTail = 0; 1554 std::pair<ActiveTail45*, ActiveTail45*> verticalPair; 1555 verticalPair.first = 0; 1556 verticalPair.second = 0; 1557 int verticalCount = 0; 1558 iT currentIter = inputBegin; 1559 std::vector<iterator> elementIters; 1560 std::vector<std::pair<Vertex45, ActiveTail45*> > elements; 1561 while(currentIter != inputEnd && currentIter->pt.x() == x_) { 1562 //std::cout << "loop\n"; 1563 Unit currentY = (*currentIter).pt.y(); 1564 iterator iter = lookUp_(currentY); 1565 //int counts[4] = {0, 0, 0, 0}; 1566 Vertex45Count counts; 1567 ActiveTail45* tails[4] = {0, 0, 0, verticalTail}; 1568 //std::cout << "finding elements in tree\n"; 1569 iterator previter = iter; 1570 if(previter != scanData_.end() && 1571 previter->first.evalAtX(x_) >= currentY && 1572 previter != scanData_.begin()) 1573 --previter; 1574 while(iter != scanData_.end() && 1575 iter->first.evalAtX(x_) == currentY) { 1576 //std::cout << "loop2\n"; 1577 elementIters.push_back(iter); 1578 int index = iter->first.rise + 1; 1579 //std::cout << index << " " << iter->first.count << "\n"; 1580 counts[index] = iter->first.count; 1581 tails[index] = iter->second; 1582 ++iter; 1583 } 1584 //int incoming[4] = {0, 0, 0, 0}; 1585 Vertex45Count incoming; 1586 //std::cout << "aggregating\n"; 1587 do { 1588 //std::cout << "loop3\n"; 1589 Vertex45Compact currentVertex(*currentIter); 1590 incoming += currentVertex.count; 1591 ++currentIter; 1592 } while(currentIter != inputEnd && currentIter->pt.y() == currentY && 1593 currentIter->pt.x() == x_); 1594 //now counts and tails have the data from the left and 1595 //incoming has the data from the right at this point 1596 //cancel out any end points 1597 //std::cout << counts[0] << " "; 1598 //std::cout << counts[1] << " "; 1599 //std::cout << counts[2] << " "; 1600 //std::cout << counts[3] << "\n"; 1601 //std::cout << incoming[0] << " "; 1602 //std::cout << incoming[1] << " "; 1603 //std::cout << incoming[2] << " "; 1604 //std::cout << incoming[3] << "\n"; 1605 if(verticalTail) { 1606 counts[3] = -verticalCount; 1607 } 1608 incoming[3] *= -1; 1609 for(unsigned int i = 0; i < 4; ++i) incoming[i] += counts[i]; 1610 //std::cout << "calling processPoint_\n"; 1611 std::pair<int, ActiveTail45*> result = processPoint_(output, elements, verticalPair, previter, 1612 Point(x_, currentY), counts, tails, incoming); 1613 verticalCount = result.first; 1614 verticalTail = result.second; 1615 if(verticalPair.first != 0 && iter != scanData_.end() && 1616 (currentIter == inputEnd || currentIter->pt.x() != x_ || 1617 currentIter->pt.y() > (*iter).first.evalAtX(x_))) { 1618 //splice vertical pair into edge above 1619 ActiveTail45* tailabove = (*iter).second; 1620 Point point(x_, (*iter).first.evalAtX(x_)); 1621 verticalPair.second->pushPoint(point); 1622 ActiveTail45::joinChains(point, tailabove, verticalPair.first, true, output); 1623 (*iter).second = verticalPair.second; 1624 verticalPair.first = 0; 1625 verticalPair.second = 0; 1626 } 1627 } 1628 //std::cout << "erasing\n"; 1629 //erase all elements from the tree 1630 for(typename std::vector<iterator>::iterator iter = elementIters.begin(); 1631 iter != elementIters.end(); ++iter) { 1632 //std::cout << "erasing loop\n"; 1633 scanData_.erase(*iter); 1634 } 1635 //switch comparison tie breaking policy 1636 justBefore_ = false; 1637 //add new elements into tree 1638 //std::cout << "inserting\n"; 1639 for(typename std::vector<std::pair<Vertex45, ActiveTail45*> >::iterator iter = elements.begin(); 1640 iter != elements.end(); ++iter) { 1641 //std::cout << "inserting loop\n"; 1642 scanData_.insert(scanData_.end(), *iter); 1643 } 1644 //std::cout << "end processEvent\n"; 1645 return currentIter; 1646 } 1647 lookUp_(Unit y)1648 inline iterator lookUp_(Unit y){ 1649 //if just before then we need to look from 1 not -1 1650 return scanData_.lower_bound(Vertex45(Point(x_, y), -1+2*justBefore_, 0)); 1651 } 1652 1653 }; 1654 1655 template <typename stream_type> testPolygon45TilingRectboost::polygon::polygon_45_formation1656 static inline bool testPolygon45TilingRect(stream_type& stdcout) { 1657 stdcout << "testing polygon tiling\n"; 1658 Polygon45Tiling pf; 1659 std::vector<Polygon45> polys; 1660 std::vector<Vertex45> data; 1661 data.push_back(Vertex45(Point(0, 0), 0, 1)); 1662 data.push_back(Vertex45(Point(0, 0), 2, 1)); 1663 data.push_back(Vertex45(Point(0, 10), 2, -1)); 1664 data.push_back(Vertex45(Point(0, 10), 0, -1)); 1665 data.push_back(Vertex45(Point(10, 0), 0, -1)); 1666 data.push_back(Vertex45(Point(10, 0), 2, -1)); 1667 data.push_back(Vertex45(Point(10, 10), 2, 1)); 1668 data.push_back(Vertex45(Point(10, 10), 0, 1)); 1669 polygon_sort(data.begin(), data.end()); 1670 pf.scan(polys, data.begin(), data.end()); 1671 stdcout << "result size: " << polys.size() << "\n"; 1672 for(std::size_t i = 0; i < polys.size(); ++i) { 1673 stdcout << polys[i] << "\n"; 1674 } 1675 stdcout << "done testing polygon tiling\n"; 1676 return true; 1677 } 1678 1679 template <typename stream_type> testPolygon45TilingP1boost::polygon::polygon_45_formation1680 static inline bool testPolygon45TilingP1(stream_type& stdcout) { 1681 stdcout << "testing polygon tiling\n"; 1682 Polygon45Tiling pf; 1683 std::vector<Polygon45> polys; 1684 std::vector<Vertex45> data; 1685 data.push_back(Vertex45(Point(0, 0), 1, 1)); 1686 data.push_back(Vertex45(Point(0, 0), 2, 1)); 1687 data.push_back(Vertex45(Point(0, 10), 2, -1)); 1688 data.push_back(Vertex45(Point(0, 10), 1, -1)); 1689 data.push_back(Vertex45(Point(10, 10), 1, -1)); 1690 data.push_back(Vertex45(Point(10, 10), 2, -1)); 1691 data.push_back(Vertex45(Point(10, 20), 2, 1)); 1692 data.push_back(Vertex45(Point(10, 20), 1, 1)); 1693 polygon_sort(data.begin(), data.end()); 1694 pf.scan(polys, data.begin(), data.end()); 1695 stdcout << "result size: " << polys.size() << "\n"; 1696 for(std::size_t i = 0; i < polys.size(); ++i) { 1697 stdcout << polys[i] << "\n"; 1698 } 1699 stdcout << "done testing polygon tiling\n"; 1700 return true; 1701 } 1702 1703 template <typename stream_type> testPolygon45TilingP2boost::polygon::polygon_45_formation1704 static inline bool testPolygon45TilingP2(stream_type& stdcout) { 1705 stdcout << "testing polygon tiling\n"; 1706 Polygon45Tiling pf; 1707 std::vector<Polygon45> polys; 1708 std::vector<Vertex45> data; 1709 data.push_back(Vertex45(Point(0, 0), 0, 1)); 1710 data.push_back(Vertex45(Point(0, 0), 1, -1)); 1711 data.push_back(Vertex45(Point(10, 0), 0, -1)); 1712 data.push_back(Vertex45(Point(10, 0), 1, 1)); 1713 data.push_back(Vertex45(Point(10, 10), 1, 1)); 1714 data.push_back(Vertex45(Point(10, 10), 0, -1)); 1715 data.push_back(Vertex45(Point(20, 10), 1, -1)); 1716 data.push_back(Vertex45(Point(20, 10), 0, 1)); 1717 polygon_sort(data.begin(), data.end()); 1718 pf.scan(polys, data.begin(), data.end()); 1719 stdcout << "result size: " << polys.size() << "\n"; 1720 for(std::size_t i = 0; i < polys.size(); ++i) { 1721 stdcout << polys[i] << "\n"; 1722 } 1723 stdcout << "done testing polygon tiling\n"; 1724 return true; 1725 } 1726 1727 template <typename stream_type> testPolygon45TilingP3boost::polygon::polygon_45_formation1728 static inline bool testPolygon45TilingP3(stream_type& stdcout) { 1729 stdcout << "testing polygon tiling\n"; 1730 Polygon45Tiling pf; 1731 std::vector<Polygon45> polys; 1732 std::vector<Vertex45> data; 1733 data.push_back(Vertex45(Point(0, 0), 0, 1)); 1734 data.push_back(Vertex45(Point(0, 0), 2, 1)); 1735 data.push_back(Vertex45(Point(0, 10), 2, -1)); 1736 data.push_back(Vertex45(Point(0, 10), 0, -1)); 1737 data.push_back(Vertex45(Point(20, 0), 0, -1)); 1738 data.push_back(Vertex45(Point(20, 0), 2, -1)); 1739 data.push_back(Vertex45(Point(10, 10), 1, -1)); 1740 data.push_back(Vertex45(Point(10, 10), 0, 1)); 1741 data.push_back(Vertex45(Point(20, 20), 1, 1)); 1742 data.push_back(Vertex45(Point(20, 20), 2, 1)); 1743 polygon_sort(data.begin(), data.end()); 1744 pf.scan(polys, data.begin(), data.end()); 1745 stdcout << "result size: " << polys.size() << "\n"; 1746 for(std::size_t i = 0; i < polys.size(); ++i) { 1747 stdcout << polys[i] << "\n"; 1748 } 1749 stdcout << "done testing polygon tiling\n"; 1750 return true; 1751 } 1752 1753 template <typename stream_type> testPolygon45TilingP4boost::polygon::polygon_45_formation1754 static inline bool testPolygon45TilingP4(stream_type& stdcout) { 1755 stdcout << "testing polygon tiling p4\n"; 1756 Polygon45Tiling pf; 1757 std::vector<Polygon45> polys; 1758 std::vector<Vertex45> data; 1759 data.push_back(Vertex45(Point(0, 0), 0, 1)); 1760 data.push_back(Vertex45(Point(0, 0), 2, 1)); 1761 data.push_back(Vertex45(Point(0, 10), 2, -1)); 1762 data.push_back(Vertex45(Point(0, 10), 0, -1)); 1763 data.push_back(Vertex45(Point(10, 0), -1, 1)); 1764 data.push_back(Vertex45(Point(10, 0), 0, -1)); 1765 data.push_back(Vertex45(Point(20, 10), 2, 1)); 1766 data.push_back(Vertex45(Point(20, 10), 0, 1)); 1767 data.push_back(Vertex45(Point(20, -10), -1, -1)); 1768 data.push_back(Vertex45(Point(20, -10), 2, -1)); 1769 polygon_sort(data.begin(), data.end()); 1770 pf.scan(polys, data.begin(), data.end()); 1771 stdcout << "result size: " << polys.size() << "\n"; 1772 for(std::size_t i = 0; i < polys.size(); ++i) { 1773 stdcout << polys[i] << "\n"; 1774 } 1775 stdcout << "done testing polygon tiling\n"; 1776 return true; 1777 } 1778 1779 template <typename stream_type> testPolygon45TilingP5boost::polygon::polygon_45_formation1780 static inline bool testPolygon45TilingP5(stream_type& stdcout) { 1781 stdcout << "testing polygon tiling P5\n"; 1782 Polygon45Tiling pf; 1783 std::vector<Polygon45> polys; 1784 std::vector<Vertex45> data; 1785 data.push_back(Vertex45(Point(0, 0), 0, 1)); 1786 data.push_back(Vertex45(Point(0, 0), 2, 1)); 1787 data.push_back(Vertex45(Point(0, 10), 2, -1)); 1788 data.push_back(Vertex45(Point(0, 10), 0, -1)); 1789 data.push_back(Vertex45(Point(10, 0), 0, -1)); 1790 data.push_back(Vertex45(Point(10, 0), 2, -1)); 1791 data.push_back(Vertex45(Point(10, 10), 2, 1)); 1792 data.push_back(Vertex45(Point(10, 10), 0, 1)); 1793 1794 data.push_back(Vertex45(Point(1, 1), 0, -1)); 1795 data.push_back(Vertex45(Point(1, 1), 1, 1)); 1796 data.push_back(Vertex45(Point(2, 1), 0, 1)); 1797 data.push_back(Vertex45(Point(2, 1), 1, -1)); 1798 data.push_back(Vertex45(Point(2, 2), 1, -1)); 1799 data.push_back(Vertex45(Point(2, 2), 0, 1)); 1800 data.push_back(Vertex45(Point(3, 2), 1, 1)); 1801 data.push_back(Vertex45(Point(3, 2), 0, -1)); 1802 polygon_sort(data.begin(), data.end()); 1803 pf.scan(polys, data.begin(), data.end()); 1804 stdcout << "result size: " << polys.size() << "\n"; 1805 for(std::size_t i = 0; i < polys.size(); ++i) { 1806 stdcout << polys[i] << "\n"; 1807 } 1808 stdcout << "done testing polygon tiling\n"; 1809 return true; 1810 } 1811 1812 template <typename stream_type> testPolygon45TilingP6boost::polygon::polygon_45_formation1813 static inline bool testPolygon45TilingP6(stream_type& stdcout) { 1814 stdcout << "testing polygon tiling P6\n"; 1815 Polygon45Tiling pf; 1816 std::vector<Polygon45> polys; 1817 std::vector<Vertex45> data; 1818 data.push_back(Vertex45(Point(0, 0), 0, 1)); 1819 data.push_back(Vertex45(Point(0, 0), 2, 1)); 1820 data.push_back(Vertex45(Point(0, 10), 2, -1)); 1821 data.push_back(Vertex45(Point(0, 10), 0, -1)); 1822 data.push_back(Vertex45(Point(10, 0), 0, -1)); 1823 data.push_back(Vertex45(Point(10, 0), 2, -1)); 1824 data.push_back(Vertex45(Point(10, 10), 2, 1)); 1825 data.push_back(Vertex45(Point(10, 10), 0, 1)); 1826 1827 data.push_back(Vertex45(Point(1, 1), 0, -1)); 1828 data.push_back(Vertex45(Point(1, 1), 2, -1)); 1829 data.push_back(Vertex45(Point(1, 2), 2, 1)); 1830 data.push_back(Vertex45(Point(1, 2), 0, 1)); 1831 data.push_back(Vertex45(Point(2, 1), 0, 1)); 1832 data.push_back(Vertex45(Point(2, 1), 2, 1)); 1833 data.push_back(Vertex45(Point(2, 2), 2, -1)); 1834 data.push_back(Vertex45(Point(2, 2), 0, -1)); 1835 1836 polygon_sort(data.begin(), data.end()); 1837 pf.scan(polys, data.begin(), data.end()); 1838 stdcout << "result size: " << polys.size() << "\n"; 1839 for(std::size_t i = 0; i < polys.size(); ++i) { 1840 stdcout << polys[i] << "\n"; 1841 } 1842 stdcout << "done testing polygon tiling\n"; 1843 return true; 1844 } 1845 1846 template <typename stream_type> testPolygon45TilingStar1boost::polygon::polygon_45_formation1847 static inline bool testPolygon45TilingStar1(stream_type& stdcout) { 1848 stdcout << "testing polygon tiling star1\n"; 1849 Polygon45Tiling pf; 1850 std::vector<Polygon45> polys; 1851 std::vector<Vertex45> data; 1852 // result == 0 8 -1 1 1853 data.push_back(Vertex45(Point(0, 8), -1, 1)); 1854 // result == 0 8 1 -1 1855 data.push_back(Vertex45(Point(0, 8), 1, -1)); 1856 // result == 4 0 1 1 1857 data.push_back(Vertex45(Point(4, 0), 1, 1)); 1858 // result == 4 0 2 1 1859 data.push_back(Vertex45(Point(4, 0), 2, 1)); 1860 // result == 4 4 2 -1 1861 data.push_back(Vertex45(Point(4, 4), 2, -1)); 1862 // result == 4 4 -1 -1 1863 data.push_back(Vertex45(Point(4, 4), -1, -1)); 1864 // result == 4 12 1 1 1865 data.push_back(Vertex45(Point(4, 12), 1, 1)); 1866 // result == 4 12 2 1 1867 data.push_back(Vertex45(Point(4, 12), 2, 1)); 1868 // result == 4 16 2 -1 1869 data.push_back(Vertex45(Point(4, 16), 2, 1)); 1870 // result == 4 16 -1 -1 1871 data.push_back(Vertex45(Point(4, 16), -1, -1)); 1872 // result == 6 2 1 -1 1873 data.push_back(Vertex45(Point(6, 2), 1, -1)); 1874 // result == 6 14 -1 1 1875 data.push_back(Vertex45(Point(6, 14), -1, 1)); 1876 // result == 6 2 -1 1 1877 data.push_back(Vertex45(Point(6, 2), -1, 1)); 1878 // result == 6 14 1 -1 1879 data.push_back(Vertex45(Point(6, 14), 1, -1)); 1880 // result == 8 0 -1 -1 1881 data.push_back(Vertex45(Point(8, 0), -1, -1)); 1882 // result == 8 0 2 -1 1883 data.push_back(Vertex45(Point(8, 0), 2, -1)); 1884 // result == 8 4 2 1 1885 data.push_back(Vertex45(Point(8, 4), 2, 1)); 1886 // result == 8 4 1 1 1887 data.push_back(Vertex45(Point(8, 4), 1, 1)); 1888 // result == 8 12 -1 -1 1889 data.push_back(Vertex45(Point(8, 12), -1, -1)); 1890 // result == 8 12 2 -1 1891 data.push_back(Vertex45(Point(8, 12), 2, -1)); 1892 // result == 8 16 2 1 1893 data.push_back(Vertex45(Point(8, 16), 2, 1)); 1894 // result == 8 16 1 1 1895 data.push_back(Vertex45(Point(8, 16), 1, 1)); 1896 // result == 12 8 1 -1 1897 data.push_back(Vertex45(Point(12, 8), 1, -1)); 1898 // result == 12 8 -1 1 1899 data.push_back(Vertex45(Point(12, 8), -1, 1)); 1900 polygon_sort(data.begin(), data.end()); 1901 pf.scan(polys, data.begin(), data.end()); 1902 stdcout << "result size: " << polys.size() << "\n"; 1903 for(std::size_t i = 0; i < polys.size(); ++i) { 1904 stdcout << polys[i] << "\n"; 1905 } 1906 stdcout << "done testing polygon tiling\n"; 1907 return true; 1908 } 1909 1910 template <typename stream_type> testPolygon45TilingStar2boost::polygon::polygon_45_formation1911 static inline bool testPolygon45TilingStar2(stream_type& stdcout) { 1912 stdcout << "testing polygon tiling\n"; 1913 Polygon45Tiling pf; 1914 std::vector<Polygon45> polys; 1915 1916 Scan45 scan45; 1917 std::vector<Vertex45 > result; 1918 std::vector<Scan45Vertex> vertices; 1919 //is a Rectnagle(0, 0, 10, 10); 1920 Count2 count(1, 0); 1921 Count2 ncount(-1, 0); 1922 vertices.push_back(Scan45Vertex(Point(0,4), Scan45Count(Count2(0, 0), count, ncount, Count2(0, 0)))); 1923 vertices.push_back(Scan45Vertex(Point(16,4), Scan45Count(count, ncount, Count2(0, 0), Count2(0, 0)))); 1924 vertices.push_back(Scan45Vertex(Point(8,12), Scan45Count(ncount, Count2(0, 0), count, Count2(0, 0)))); 1925 count = Count2(0, 1); 1926 ncount = count.invert(); 1927 vertices.push_back(Scan45Vertex(Point(0,8), Scan45Count(count, ncount, Count2(0, 0), Count2(0, 0)))); 1928 vertices.push_back(Scan45Vertex(Point(16,8), Scan45Count(Count2(0, 0), count, ncount, Count2(0, 0)))); 1929 vertices.push_back(Scan45Vertex(Point(8,0), Scan45Count(ncount, Count2(0, 0), count, Count2(0, 0)))); 1930 sortScan45Vector(vertices); 1931 stdcout << "scanning\n"; 1932 scan45.scan(result, vertices.begin(), vertices.end()); 1933 1934 polygon_sort(result.begin(), result.end()); 1935 pf.scan(polys, result.begin(), result.end()); 1936 stdcout << "result size: " << polys.size() << "\n"; 1937 for(std::size_t i = 0; i < polys.size(); ++i) { 1938 stdcout << polys[i] << "\n"; 1939 } 1940 stdcout << "done testing polygon tiling\n"; 1941 return true; 1942 } 1943 1944 template <typename stream_type> testPolygon45TilingStarHole1boost::polygon::polygon_45_formation1945 static inline bool testPolygon45TilingStarHole1(stream_type& stdcout) { 1946 stdcout << "testing polygon tiling star hole 1\n"; 1947 Polygon45Tiling pf; 1948 std::vector<Polygon45> polys; 1949 std::vector<Vertex45> data; 1950 // result == 0 8 -1 1 1951 data.push_back(Vertex45(Point(0, 8), -1, 1)); 1952 // result == 0 8 1 -1 1953 data.push_back(Vertex45(Point(0, 8), 1, -1)); 1954 // result == 4 0 1 1 1955 data.push_back(Vertex45(Point(4, 0), 1, 1)); 1956 // result == 4 0 2 1 1957 data.push_back(Vertex45(Point(4, 0), 2, 1)); 1958 // result == 4 4 2 -1 1959 data.push_back(Vertex45(Point(4, 4), 2, -1)); 1960 // result == 4 4 -1 -1 1961 data.push_back(Vertex45(Point(4, 4), -1, -1)); 1962 // result == 4 12 1 1 1963 data.push_back(Vertex45(Point(4, 12), 1, 1)); 1964 // result == 4 12 2 1 1965 data.push_back(Vertex45(Point(4, 12), 2, 1)); 1966 // result == 4 16 2 -1 1967 data.push_back(Vertex45(Point(4, 16), 2, 1)); 1968 // result == 4 16 -1 -1 1969 data.push_back(Vertex45(Point(4, 16), -1, -1)); 1970 // result == 6 2 1 -1 1971 data.push_back(Vertex45(Point(6, 2), 1, -1)); 1972 // result == 6 14 -1 1 1973 data.push_back(Vertex45(Point(6, 14), -1, 1)); 1974 // result == 6 2 -1 1 1975 data.push_back(Vertex45(Point(6, 2), -1, 1)); 1976 // result == 6 14 1 -1 1977 data.push_back(Vertex45(Point(6, 14), 1, -1)); 1978 // result == 8 0 -1 -1 1979 data.push_back(Vertex45(Point(8, 0), -1, -1)); 1980 // result == 8 0 2 -1 1981 data.push_back(Vertex45(Point(8, 0), 2, -1)); 1982 // result == 8 4 2 1 1983 data.push_back(Vertex45(Point(8, 4), 2, 1)); 1984 // result == 8 4 1 1 1985 data.push_back(Vertex45(Point(8, 4), 1, 1)); 1986 // result == 8 12 -1 -1 1987 data.push_back(Vertex45(Point(8, 12), -1, -1)); 1988 // result == 8 12 2 -1 1989 data.push_back(Vertex45(Point(8, 12), 2, -1)); 1990 // result == 8 16 2 1 1991 data.push_back(Vertex45(Point(8, 16), 2, 1)); 1992 // result == 8 16 1 1 1993 data.push_back(Vertex45(Point(8, 16), 1, 1)); 1994 // result == 12 8 1 -1 1995 data.push_back(Vertex45(Point(12, 8), 1, -1)); 1996 // result == 12 8 -1 1 1997 data.push_back(Vertex45(Point(12, 8), -1, 1)); 1998 1999 data.push_back(Vertex45(Point(6, 4), 1, -1)); 2000 data.push_back(Vertex45(Point(6, 4), 2, -1)); 2001 data.push_back(Vertex45(Point(6, 8), -1, 1)); 2002 data.push_back(Vertex45(Point(6, 8), 2, 1)); 2003 data.push_back(Vertex45(Point(8, 6), -1, -1)); 2004 data.push_back(Vertex45(Point(8, 6), 1, 1)); 2005 2006 polygon_sort(data.begin(), data.end()); 2007 pf.scan(polys, data.begin(), data.end()); 2008 stdcout << "result size: " << polys.size() << "\n"; 2009 for(std::size_t i = 0; i < polys.size(); ++i) { 2010 stdcout << polys[i] << "\n"; 2011 } 2012 stdcout << "done testing polygon tiling\n"; 2013 return true; 2014 } 2015 2016 template <typename stream_type> testPolygon45TilingStarHole2boost::polygon::polygon_45_formation2017 static inline bool testPolygon45TilingStarHole2(stream_type& stdcout) { 2018 stdcout << "testing polygon tiling star hole 2\n"; 2019 Polygon45Tiling pf; 2020 std::vector<Polygon45WithHoles> polys; 2021 std::vector<Vertex45> data; 2022 // result == 0 8 -1 1 2023 data.push_back(Vertex45(Point(0, 8), -1, 1)); 2024 // result == 0 8 1 -1 2025 data.push_back(Vertex45(Point(0, 8), 1, -1)); 2026 // result == 4 0 1 1 2027 data.push_back(Vertex45(Point(4, 0), 1, 1)); 2028 // result == 4 0 2 1 2029 data.push_back(Vertex45(Point(4, 0), 2, 1)); 2030 // result == 4 4 2 -1 2031 data.push_back(Vertex45(Point(4, 4), 2, -1)); 2032 // result == 4 4 -1 -1 2033 data.push_back(Vertex45(Point(4, 4), -1, -1)); 2034 // result == 4 12 1 1 2035 data.push_back(Vertex45(Point(4, 12), 1, 1)); 2036 // result == 4 12 2 1 2037 data.push_back(Vertex45(Point(4, 12), 2, 1)); 2038 // result == 4 16 2 -1 2039 data.push_back(Vertex45(Point(4, 16), 2, 1)); 2040 // result == 4 16 -1 -1 2041 data.push_back(Vertex45(Point(4, 16), -1, -1)); 2042 // result == 6 2 1 -1 2043 data.push_back(Vertex45(Point(6, 2), 1, -1)); 2044 // result == 6 14 -1 1 2045 data.push_back(Vertex45(Point(6, 14), -1, 1)); 2046 // result == 6 2 -1 1 2047 data.push_back(Vertex45(Point(6, 2), -1, 1)); 2048 // result == 6 14 1 -1 2049 data.push_back(Vertex45(Point(6, 14), 1, -1)); 2050 // result == 8 0 -1 -1 2051 data.push_back(Vertex45(Point(8, 0), -1, -1)); 2052 // result == 8 0 2 -1 2053 data.push_back(Vertex45(Point(8, 0), 2, -1)); 2054 // result == 8 4 2 1 2055 data.push_back(Vertex45(Point(8, 4), 2, 1)); 2056 // result == 8 4 1 1 2057 data.push_back(Vertex45(Point(8, 4), 1, 1)); 2058 // result == 8 12 -1 -1 2059 data.push_back(Vertex45(Point(8, 12), -1, -1)); 2060 // result == 8 12 2 -1 2061 data.push_back(Vertex45(Point(8, 12), 2, -1)); 2062 // result == 8 16 2 1 2063 data.push_back(Vertex45(Point(8, 16), 2, 1)); 2064 // result == 8 16 1 1 2065 data.push_back(Vertex45(Point(8, 16), 1, 1)); 2066 // result == 12 8 1 -1 2067 data.push_back(Vertex45(Point(12, 8), 1, -1)); 2068 // result == 12 8 -1 1 2069 data.push_back(Vertex45(Point(12, 8), -1, 1)); 2070 2071 data.push_back(Vertex45(Point(6, 4), 1, -1)); 2072 data.push_back(Vertex45(Point(6, 4), 2, -1)); 2073 data.push_back(Vertex45(Point(6, 12), -1, 1)); 2074 data.push_back(Vertex45(Point(6, 12), 2, 1)); 2075 data.push_back(Vertex45(Point(10, 8), -1, -1)); 2076 data.push_back(Vertex45(Point(10, 8), 1, 1)); 2077 2078 polygon_sort(data.begin(), data.end()); 2079 pf.scan(polys, data.begin(), data.end()); 2080 stdcout << "result size: " << polys.size() << "\n"; 2081 for(std::size_t i = 0; i < polys.size(); ++i) { 2082 stdcout << polys[i] << "\n"; 2083 } 2084 stdcout << "done testing polygon tiling\n"; 2085 return true; 2086 } 2087 2088 template <typename stream_type> testPolygon45Tilingboost::polygon::polygon_45_formation2089 static inline bool testPolygon45Tiling(stream_type& stdcout) { 2090 stdcout << "testing polygon tiling\n"; 2091 Polygon45Tiling pf; 2092 std::vector<Polygon45WithHoles> polys; 2093 std::vector<Vertex45> data; 2094 2095 data.push_back(Vertex45(Point(0, 0), 0, 1)); 2096 data.push_back(Vertex45(Point(0, 0), 2, 1)); 2097 data.push_back(Vertex45(Point(0, 100), 2, -1)); 2098 data.push_back(Vertex45(Point(0, 100), 0, -1)); 2099 data.push_back(Vertex45(Point(100, 0), 0, -1)); 2100 data.push_back(Vertex45(Point(100, 0), 2, -1)); 2101 data.push_back(Vertex45(Point(100, 100), 2, 1)); 2102 data.push_back(Vertex45(Point(100, 100), 0, 1)); 2103 2104 data.push_back(Vertex45(Point(2, 2), 0, -1)); 2105 data.push_back(Vertex45(Point(2, 2), 2, -1)); 2106 data.push_back(Vertex45(Point(2, 10), 2, 1)); 2107 data.push_back(Vertex45(Point(2, 10), 0, 1)); 2108 data.push_back(Vertex45(Point(10, 2), 0, 1)); 2109 data.push_back(Vertex45(Point(10, 2), 2, 1)); 2110 data.push_back(Vertex45(Point(10, 10), 2, -1)); 2111 data.push_back(Vertex45(Point(10, 10), 0, -1)); 2112 2113 data.push_back(Vertex45(Point(2, 12), 0, -1)); 2114 data.push_back(Vertex45(Point(2, 12), 2, -1)); 2115 data.push_back(Vertex45(Point(2, 22), 2, 1)); 2116 data.push_back(Vertex45(Point(2, 22), 0, 1)); 2117 data.push_back(Vertex45(Point(10, 12), 0, 1)); 2118 data.push_back(Vertex45(Point(10, 12), 2, 1)); 2119 data.push_back(Vertex45(Point(10, 22), 2, -1)); 2120 data.push_back(Vertex45(Point(10, 22), 0, -1)); 2121 2122 polygon_sort(data.begin(), data.end()); 2123 pf.scan(polys, data.begin(), data.end()); 2124 stdcout << "result size: " << polys.size() << "\n"; 2125 for(std::size_t i = 0; i < polys.size(); ++i) { 2126 stdcout << polys[i] << "\n"; 2127 } 2128 stdcout << "done testing polygon tiling\n"; 2129 return true; 2130 } 2131 }; 2132 2133 template <typename Unit> 2134 class PolyLine45HoleData { 2135 public: 2136 typedef typename polygon_45_formation<Unit>::ActiveTail45 ActiveTail45; 2137 typedef typename ActiveTail45::iterator iterator; 2138 2139 typedef polygon_45_concept geometry_type; 2140 typedef Unit coordinate_type; 2141 typedef point_data<Unit> Point; 2142 typedef Point point_type; 2143 // typedef iterator_points_to_compact<iterator, Point> compact_iterator_type; 2144 typedef iterator iterator_type; 2145 typedef typename coordinate_traits<Unit>::area_type area_type; 2146 PolyLine45HoleData()2147 inline PolyLine45HoleData() : p_(0) {} PolyLine45HoleData(ActiveTail45 * p)2148 inline PolyLine45HoleData(ActiveTail45* p) : p_(p) {} 2149 //use default copy and assign begin() const2150 inline iterator begin() const { return p_->getTail()->begin(); } end() const2151 inline iterator end() const { return p_->getTail()->end(); } size() const2152 inline std::size_t size() const { return 0; } 2153 private: 2154 ActiveTail45* p_; 2155 }; 2156 2157 template <typename Unit> 2158 class PolyLine45PolygonData { 2159 public: 2160 typedef typename polygon_45_formation<Unit>::ActiveTail45 ActiveTail45; 2161 typedef typename ActiveTail45::iterator iterator; 2162 typedef PolyLine45HoleData<Unit> holeType; 2163 2164 typedef polygon_45_with_holes_concept geometry_type; 2165 typedef Unit coordinate_type; 2166 typedef point_data<Unit> Point; 2167 typedef Point point_type; 2168 // typedef iterator_points_to_compact<iterator, Point> compact_iterator_type; 2169 typedef iterator iterator_type; 2170 typedef holeType hole_type; 2171 typedef typename coordinate_traits<Unit>::area_type area_type; 2172 class iteratorHoles { 2173 private: 2174 typename ActiveTail45::iteratorHoles itr_; 2175 public: 2176 typedef PolyLine45HoleData<Unit> holeType; 2177 typedef holeType value_type; 2178 typedef std::forward_iterator_tag iterator_category; 2179 typedef std::ptrdiff_t difference_type; 2180 typedef const value_type* pointer; //immutable 2181 typedef const value_type& reference; //immutable iteratorHoles()2182 inline iteratorHoles() : itr_() {} iteratorHoles(typename ActiveTail45::iteratorHoles itr)2183 inline iteratorHoles(typename ActiveTail45::iteratorHoles itr) : itr_(itr) {} iteratorHoles(const iteratorHoles & that)2184 inline iteratorHoles(const iteratorHoles& that) : itr_(that.itr_) {} operator =(const iteratorHoles & that)2185 inline iteratorHoles& operator=(const iteratorHoles& that) { 2186 itr_ = that.itr_; 2187 return *this; 2188 } operator ==(const iteratorHoles & that)2189 inline bool operator==(const iteratorHoles& that) { return itr_ == that.itr_; } operator !=(const iteratorHoles & that)2190 inline bool operator!=(const iteratorHoles& that) { return itr_ != that.itr_; } operator ++()2191 inline iteratorHoles& operator++() { 2192 ++itr_; 2193 return *this; 2194 } operator ++(int)2195 inline const iteratorHoles operator++(int) { 2196 iteratorHoles tmp = *this; 2197 ++(*this); 2198 return tmp; 2199 } operator *()2200 inline holeType operator*() { 2201 return *itr_; 2202 } 2203 }; 2204 typedef iteratorHoles iterator_holes_type; 2205 2206 PolyLine45PolygonData()2207 inline PolyLine45PolygonData() : p_(0) {} PolyLine45PolygonData(ActiveTail45 * p)2208 inline PolyLine45PolygonData(ActiveTail45* p) : p_(p) {} 2209 //use default copy and assign begin() const2210 inline iterator begin() const { return p_->getTail()->begin(); } end() const2211 inline iterator end() const { return p_->getTail()->end(); } begin_holes() const2212 inline iteratorHoles begin_holes() const { return iteratorHoles(p_->getHoles().begin()); } end_holes() const2213 inline iteratorHoles end_holes() const { return iteratorHoles(p_->getHoles().end()); } yield()2214 inline ActiveTail45* yield() { return p_; } 2215 //stub out these four required functions that will not be used but are needed for the interface size_holes() const2216 inline std::size_t size_holes() const { return 0; } size() const2217 inline std::size_t size() const { return 0; } 2218 private: 2219 ActiveTail45* p_; 2220 }; 2221 2222 template <typename T> 2223 struct PolyLineByConcept<T, polygon_45_with_holes_concept> { typedef PolyLine45PolygonData<T> type; }; 2224 template <typename T> 2225 struct PolyLineByConcept<T, polygon_with_holes_concept> { typedef PolyLine45PolygonData<T> type; }; 2226 template <typename T> 2227 struct PolyLineByConcept<T, polygon_45_concept> { typedef PolyLine45HoleData<T> type; }; 2228 template <typename T> 2229 struct PolyLineByConcept<T, polygon_concept> { typedef PolyLine45HoleData<T> type; }; 2230 2231 template <typename T> 2232 struct geometry_concept<PolyLine45PolygonData<T> > { typedef polygon_45_with_holes_concept type; }; 2233 template <typename T> 2234 struct geometry_concept<PolyLine45HoleData<T> > { typedef polygon_45_concept type; }; 2235 2236 } 2237 } 2238 #endif 2239