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 #include<iostream> 9 #include<cassert> 10 #ifndef BOOST_POLYGON_POLYGON_FORMATION_HPP 11 #define BOOST_POLYGON_POLYGON_FORMATION_HPP 12 namespace boost { namespace polygon{ 13 14 namespace polygon_formation { 15 16 /* 17 * End has two states, HEAD and TAIL as is represented by a bool 18 */ 19 typedef bool End; 20 21 /* 22 * HEAD End is represented as false because it is the lesser state 23 */ 24 const End HEAD = false; 25 26 /* 27 * TAIL End is represented by true because TAIL comes after head and 1 after 0 28 */ 29 const End TAIL = true; 30 31 /* 32 * 2D turning direction, left and right sides (is a boolean value since it has two states.) 33 */ 34 typedef bool Side; 35 36 /* 37 * LEFT Side is 0 because we inuitively think left to right; left < right 38 */ 39 const Side LEFT = false; 40 41 /* 42 * RIGHT Side is 1 so that right > left 43 */ 44 const Side RIGHT = true; 45 46 /* 47 * The PolyLine class is data storage and services for building and representing partial polygons. 48 * As the polyline is added to it extends its storage to accomodate the data. 49 * PolyLines can be joined head-to-head/head-to-tail when it is determined that two polylines are 50 * part of the same polygon. 51 * PolyLines keep state information about what orientation their incomplete head and tail geometry have, 52 * which side of the polyline is solid and whether the polyline is joined head-to-head and tail-to-head. 53 * PolyLines have nothing whatsoever to do with holes. 54 * It may be valuable to collect a histogram of PolyLine lengths used by an algorithm on its typical data 55 * sets and tune the allocation of the initial vector of coordinate data to be greater than or equal to 56 * the mean, median, mode, or mean plus some number of standard deviation, or just generally large enough 57 * to prevent too much unnecesary reallocations, but not too big that it wastes a lot of memory and degrades cache 58 * performance. 59 */ 60 template <typename Unit> 61 class PolyLine { 62 private: 63 //data 64 65 /* 66 * ptdata_ a vector of coordiantes 67 * if VERTICAL_HEAD, first coordiante is an X 68 * else first coordinate is a Y 69 */ 70 std::vector<Unit> ptdata_; 71 72 /* 73 * head and tail points to other polylines before and after this in a chain 74 */ 75 PolyLine* headp_; 76 PolyLine* tailp_; 77 78 /* 79 * state bitmask 80 * bit zero is orientation, 0 H, 1 V 81 * bit 1 is head connectivity, 0 for head, 1 for tail 82 * bit 2 is tail connectivity, 0 for head, 1 for tail 83 * bit 3 is solid to left of PolyLine when 1, right when 0 84 */ 85 int state_; 86 87 public: 88 /* 89 * default constructor (for preallocation) 90 */ 91 PolyLine(); 92 93 /* 94 * constructor that takes the orientation, coordiante and side to which there is solid 95 */ 96 PolyLine(orientation_2d orient, Unit coord, Side side); 97 98 //copy constructor 99 PolyLine(const PolyLine& pline); 100 101 //destructor 102 ~PolyLine(); 103 104 //assignment operator 105 PolyLine& operator=(const PolyLine& that); 106 107 //equivalence operator 108 bool operator==(const PolyLine& b) const; 109 110 /* 111 * valid PolyLine (only default constructed polylines are invalid.) 112 */ 113 bool isValid() const; 114 115 /* 116 * Orientation of Head 117 */ 118 orientation_2d headOrient() const; 119 120 /* 121 * returns true if first coordinate is an X value (first segment is vertical) 122 */ 123 bool verticalHead() const; 124 125 /* 126 * returns the orientation_2d fo the tail 127 */ 128 orientation_2d tailOrient() const; 129 130 /* 131 * returns true if last coordinate is an X value (last segment is vertical) 132 */ 133 bool verticalTail() const; 134 135 /* 136 * retrun true if PolyLine has odd number of coordiantes 137 */ 138 bool oddLength() const; 139 140 /* 141 * retrun the End of the other polyline that the specified end of this polyline is connected to 142 */ 143 End endConnectivity(End end) const; 144 145 /* 146 * retrun true if the head of this polyline is connect to the tail of a polyline 147 */ 148 bool headToTail() const; 149 /* 150 * retrun true if the head of this polyline is connect to the head of a polyline 151 */ 152 bool headToHead() const; 153 154 /* 155 * retrun true if the tail of this polyline is connect to the tail of a polyline 156 */ 157 bool tailToTail() const; 158 /* 159 * retrun true if the tail of this polyline is connect to the head of a polyline 160 */ 161 bool tailToHead() const; 162 163 /* 164 * retrun the side on which there is solid for this polyline 165 */ 166 Side solidSide() const; 167 168 /* 169 * retrun true if there is solid to the right of this polyline 170 */ 171 bool solidToRight() const; 172 173 /* 174 * returns true if the polyline tail is not connected 175 */ 176 bool active() const; 177 178 /* 179 * adds a coordinate value to the end of the polyline changing the tail orientation 180 */ 181 PolyLine& pushCoordinate(Unit coord); 182 183 /* 184 * removes a coordinate value at the end of the polyline changing the tail orientation 185 */ 186 PolyLine& popCoordinate(); 187 188 /* 189 * extends the tail of the polyline to include the point, changing orientation if needed 190 */ 191 PolyLine& pushPoint(const point_data<Unit>& point); 192 193 /* 194 * changes the last coordinate of the tail of the polyline by the amount of the delta 195 */ 196 PolyLine& extendTail(Unit delta); 197 198 /* 199 * join thisEnd of this polyline to that polyline's end 200 */ 201 PolyLine& joinTo(End thisEnd, PolyLine& that, End end); 202 203 /* 204 * join an end of this polyline to the tail of that polyline 205 */ 206 PolyLine& joinToTail(PolyLine& that, End end); 207 208 /* 209 * join an end of this polyline to the head of that polyline 210 */ 211 PolyLine& joinToHead(PolyLine& that, End end); 212 213 /* 214 * join the head of this polyline to the head of that polyline 215 */ 216 //join this to that in the given way 217 PolyLine& joinHeadToHead(PolyLine& that); 218 219 /* 220 * join the head of this polyline to the tail of that polyline 221 */ 222 PolyLine& joinHeadToTail(PolyLine& that); 223 224 /* 225 * join the tail of this polyline to the head of that polyline 226 */ 227 PolyLine& joinTailToHead(PolyLine& that); 228 229 /* 230 * join the tail of this polyline to the tail of that polyline 231 */ 232 PolyLine& joinTailToTail(PolyLine& that); 233 234 /* 235 * dissconnect the tail at the end of the polygon 236 */ 237 PolyLine& disconnectTails(); 238 239 /* 240 * get the coordinate at one end of this polyline, by default the tail end 241 */ 242 Unit getEndCoord(End end = TAIL) const; 243 244 /* 245 * get the point on the polyline at the given index (polylines have the same number of coordinates as points 246 */ 247 point_data<Unit> getPoint(unsigned int index) const; 248 249 /* 250 * get the point on one end of the polyline, by default the tail 251 */ 252 point_data<Unit> getEndPoint(End end = TAIL) const; 253 254 /* 255 * get the orientation of a segment by index 256 */ 257 orientation_2d segmentOrient(unsigned int index = 0) const; 258 259 /* 260 * get a coordinate by index using the square bracket operator 261 */ 262 Unit operator[] (unsigned int index) const; 263 264 /* 265 * get the number of segments/points/coordinates in the polyline 266 */ 267 unsigned int numSegments() const; 268 269 /* 270 * get the pointer to the next polyline at one end of this 271 */ 272 PolyLine* next(End end) const; 273 274 /* 275 * write out coordinates of this and all attached polylines to a single vector 276 */ 277 PolyLine* writeOut(std::vector<Unit>& outVec, End startEnd = TAIL) const; 278 279 private: 280 //methods 281 PolyLine& joinTo_(End thisEnd, PolyLine& that, End end); 282 }; 283 284 //forward declaration 285 template<bool orientT, typename Unit> 286 class PolyLinePolygonData; 287 288 //forward declaration 289 template<bool orientT, typename Unit> 290 class PolyLinePolygonWithHolesData; 291 292 /* 293 * ActiveTail represents an edge of an incomplete polygon. 294 * 295 * An ActiveTail object is the active tail end of a polyline object, which may (should) be the attached to 296 * a chain of polyline objects through a pointer. The ActiveTail class provides an abstraction between 297 * and algorithm that builds polygons and the PolyLine data representation of incomplete polygons that are 298 * being built. It does this by providing an iterface to access the information about the last edge at the 299 * tail of the PolyLine it is associated with. To a polygon constructing algorithm, an ActiveTail is a floating 300 * edge of an incomplete polygon and has an orientation and coordinate value, as well as knowing which side of 301 * that edge is supposed to be solid or space. Any incomplete polygon will have two active tails. Active tails 302 * may be joined together to merge two incomplete polygons into a larger incomplete polygon. If two active tails 303 * that are to be merged are the oppositve ends of the same incomplete polygon that indicates that the polygon 304 * has been closed and is complete. The active tail keeps a pointer to the other active tail of its incomplete 305 * polygon so that it is easy to check this condition. These pointers are updated when active tails are joined. 306 * The active tail also keeps a list of pointers to active tail objects that serve as handles to closed holes. In 307 * this way a hole can be associated to another incomplete polygon, which will eventually be its enclosing shell, 308 * or reassociate the hole to another incomplete polygon in the case that it become a hole itself. Alternately, 309 * the active tail may add a filiment to stitch a hole into a shell and "fracture" the hole out of the interior 310 * of a polygon. The active tail maintains a static output buffer to temporarily write polygon data to when 311 * it outputs a figure so that outputting a polygon does not require the allocation of a temporary buffer. This 312 * static buffer should be destroyed whenever the program determines that it won't need it anymore and would prefer to 313 * release the memory it has allocated back to the system. 314 */ 315 template <typename Unit> 316 class ActiveTail { 317 private: 318 //data 319 PolyLine<Unit>* tailp_; 320 ActiveTail *otherTailp_; 321 std::list<ActiveTail*> holesList_; 322 //Sum of all the polylines which constitute the active tail (including holes)// 323 size_t polyLineSize_; 324 public: 325 getPolyLineSize()326 inline size_t getPolyLineSize(){ 327 return polyLineSize_; 328 } 329 setPolyLineSize(int delta)330 inline void setPolyLineSize(int delta){ 331 polyLineSize_ = delta; 332 } 333 addPolyLineSize(int delta)334 inline void addPolyLineSize(int delta){ 335 polyLineSize_ += delta; 336 } 337 338 /* 339 * iterator over coordinates of the figure 340 */ 341 class iterator { 342 private: 343 const PolyLine<Unit>* pLine_; 344 const PolyLine<Unit>* pLineEnd_; 345 unsigned int index_; 346 unsigned int indexEnd_; 347 End startEnd_; 348 public: iterator()349 inline iterator() : pLine_(), pLineEnd_(), index_(), indexEnd_(), startEnd_() {} iterator(const ActiveTail * at,bool isHole,orientation_2d orient)350 inline iterator(const ActiveTail* at, bool isHole, orientation_2d orient) : 351 pLine_(), pLineEnd_(), index_(), indexEnd_(), startEnd_() { 352 //if it is a hole and orientation is vertical or it is not a hole and orientation is horizontal 353 //we want to use this active tail, otherwise we want to use the other active tail 354 startEnd_ = TAIL; 355 if(!isHole ^ (orient == HORIZONTAL)) { 356 //switch winding direction 357 at = at->getOtherActiveTail(); 358 } 359 //now we have the right winding direction 360 //if it is horizontal we need to skip the first element 361 pLine_ = at->getTail(); 362 363 if(at->getTail()->numSegments() > 0) 364 index_ = at->getTail()->numSegments() - 1; 365 366 if((at->getOrient() == HORIZONTAL) ^ (orient == HORIZONTAL)) { 367 pLineEnd_ = at->getTail(); 368 indexEnd_ = pLineEnd_->numSegments() - 1; 369 if(index_ == 0) { 370 pLine_ = at->getTail()->next(HEAD); 371 if(at->getTail()->endConnectivity(HEAD) == TAIL) { 372 index_ = pLine_->numSegments() -1; 373 } else { 374 startEnd_ = HEAD; 375 index_ = 0; 376 } 377 } else { --index_; } 378 } else { 379 pLineEnd_ = at->getOtherActiveTail()->getTail(); 380 if(pLineEnd_->numSegments() > 0) 381 indexEnd_ = pLineEnd_->numSegments() - 1; 382 } 383 at->getTail()->joinTailToTail(*(at->getOtherActiveTail()->getTail())); 384 } 385 size(void)386 inline size_t size(void){ 387 size_t count = 0; 388 End dir = startEnd_; 389 PolyLine<Unit> const * currLine = pLine_; 390 size_t ops = 0; 391 while(currLine != pLineEnd_){ 392 ops++; 393 count += currLine->numSegments(); 394 currLine = currLine->next(dir == HEAD ? TAIL : HEAD); 395 dir = currLine->endConnectivity(dir == HEAD ? TAIL : HEAD); 396 } 397 count += pLineEnd_->numSegments(); 398 return count; //no. of vertices 399 } 400 401 //use bitwise copy and assign provided by the compiler operator ++()402 inline iterator& operator++() { 403 if(pLine_ == pLineEnd_ && index_ == indexEnd_) { 404 pLine_ = 0; 405 index_ = 0; 406 return *this; 407 } 408 if(startEnd_ == HEAD) { 409 ++index_; 410 if(index_ == pLine_->numSegments()) { 411 End end = pLine_->endConnectivity(TAIL); 412 pLine_ = pLine_->next(TAIL); 413 if(end == TAIL) { 414 startEnd_ = TAIL; 415 index_ = pLine_->numSegments() -1; 416 } else { 417 index_ = 0; 418 } 419 } 420 } else { 421 if(index_ == 0) { 422 End end = pLine_->endConnectivity(HEAD); 423 pLine_ = pLine_->next(HEAD); 424 if(end == TAIL) { 425 index_ = pLine_->numSegments() -1; 426 } else { 427 startEnd_ = HEAD; 428 index_ = 0; 429 } 430 } else { 431 --index_; 432 } 433 } 434 return *this; 435 } operator ++(int)436 inline const iterator operator++(int) { 437 iterator tmp(*this); 438 ++(*this); 439 return tmp; 440 } operator ==(const iterator & that) const441 inline bool operator==(const iterator& that) const { 442 return pLine_ == that.pLine_ && index_ == that.index_; 443 } operator !=(const iterator & that) const444 inline bool operator!=(const iterator& that) const { 445 return pLine_ != that.pLine_ || index_ != that.index_; 446 } operator *()447 inline Unit operator*() { return (*pLine_)[index_]; } 448 }; 449 450 /* 451 * iterator over holes contained within the figure 452 */ 453 typedef typename std::list<ActiveTail*>::const_iterator iteratorHoles; 454 455 //default constructor 456 ActiveTail(); 457 458 //constructor 459 ActiveTail(orientation_2d orient, Unit coord, Side solidToRight, ActiveTail* otherTailp); 460 461 //constructor 462 ActiveTail(PolyLine<Unit>* active, ActiveTail* otherTailp); 463 464 //copy constructor 465 ActiveTail(const ActiveTail& that); 466 467 //destructor 468 ~ActiveTail(); 469 470 //assignment operator 471 ActiveTail& operator=(const ActiveTail& that); 472 473 //equivalence operator 474 bool operator==(const ActiveTail& b) const; 475 476 /* 477 * comparison operators, ActiveTail objects are sortable by geometry 478 */ 479 bool operator<(const ActiveTail& b) const; 480 bool operator<=(const ActiveTail& b) const; 481 bool operator>(const ActiveTail& b) const; 482 bool operator>=(const ActiveTail& b) const; 483 484 /* 485 * get the pointer to the polyline that this is an active tail of 486 */ 487 PolyLine<Unit>* getTail() const; 488 489 /* 490 * get the pointer to the polyline at the other end of the chain 491 */ 492 PolyLine<Unit>* getOtherTail() const; 493 494 /* 495 * get the pointer to the activetail at the other end of the chain 496 */ 497 ActiveTail* getOtherActiveTail() const; 498 499 /* 500 * test if another active tail is the other end of the chain 501 */ 502 bool isOtherTail(const ActiveTail& b); 503 504 /* 505 * update this end of chain pointer to new polyline 506 */ 507 ActiveTail& updateTail(PolyLine<Unit>* newTail); 508 509 /* 510 * associate a hole to this active tail by the specified policy 511 */ 512 ActiveTail* addHole(ActiveTail* hole, bool fractureHoles); 513 514 /* 515 * get the list of holes 516 */ 517 const std::list<ActiveTail*>& getHoles() const; 518 519 /* 520 * copy holes from that to this 521 */ 522 void copyHoles(ActiveTail& that); 523 524 /* 525 * find out if solid to right 526 */ 527 bool solidToRight() const; 528 529 /* 530 * get coordinate (getCoord and getCoordinate are aliases for eachother) 531 */ 532 Unit getCoord() const; 533 Unit getCoordinate() const; 534 535 /* 536 * get the tail orientation 537 */ 538 orientation_2d getOrient() const; 539 540 /* 541 * add a coordinate to the polygon at this active tail end, properly handle degenerate edges by removing redundant coordinate 542 */ 543 void pushCoordinate(Unit coord); 544 545 /* 546 * write the figure that this active tail points to out to the temp buffer 547 */ 548 void writeOutFigure(std::vector<Unit>& outVec, bool isHole = false) const; 549 550 /* 551 * write the figure that this active tail points to out through iterators 552 */ 553 void writeOutFigureItrs(iterator& beginOut, iterator& endOut, bool isHole = false, orientation_2d orient = VERTICAL) const; 554 iterator begin(bool isHole, orientation_2d orient) const; 555 iterator end() const; 556 557 /* 558 * write the holes that this active tail points to out through iterators 559 */ 560 void writeOutFigureHoleItrs(iteratorHoles& beginOut, iteratorHoles& endOut) const; 561 iteratorHoles beginHoles() const; 562 iteratorHoles endHoles() const; 563 564 /* 565 * joins the two chains that the two active tail tails are ends of 566 * checks for closure of figure and writes out polygons appropriately 567 * returns a handle to a hole if one is closed 568 */ 569 static ActiveTail* joinChains(ActiveTail* at1, ActiveTail* at2, bool solid, std::vector<Unit>& outBufferTmp); 570 template <typename PolygonT> 571 static ActiveTail* joinChains(ActiveTail* at1, ActiveTail* at2, bool solid, typename std::vector<PolygonT>& outBufferTmp); 572 573 /* 574 * deallocate temp buffer 575 */ 576 static void destroyOutBuffer(); 577 578 /* 579 * deallocate all polygon data this active tail points to (deep delete, call only from one of a pair of active tails) 580 */ 581 void destroyContents(); 582 }; 583 584 /* allocate a polyline object */ 585 template <typename Unit> 586 PolyLine<Unit>* createPolyLine(orientation_2d orient, Unit coord, Side side); 587 588 /* deallocate a polyline object */ 589 template <typename Unit> 590 void destroyPolyLine(PolyLine<Unit>* pLine); 591 592 /* allocate an activetail object */ 593 template <typename Unit> 594 ActiveTail<Unit>* createActiveTail(); 595 596 /* deallocate an activetail object */ 597 template <typename Unit> 598 void destroyActiveTail(ActiveTail<Unit>* aTail); 599 600 template<bool orientT, typename Unit> 601 class PolyLineHoleData { 602 private: 603 ActiveTail<Unit>* p_; 604 public: 605 typedef Unit coordinate_type; 606 typedef typename ActiveTail<Unit>::iterator compact_iterator_type; 607 typedef iterator_compact_to_points<compact_iterator_type, point_data<coordinate_type> > iterator_type; PolyLineHoleData()608 inline PolyLineHoleData() : p_(0) {} PolyLineHoleData(ActiveTail<Unit> * p)609 inline PolyLineHoleData(ActiveTail<Unit>* p) : p_(p) {} 610 //use default copy and assign begin_compact() const611 inline compact_iterator_type begin_compact() const { return p_->begin(true, (orientT ? VERTICAL : HORIZONTAL)); } end_compact() const612 inline compact_iterator_type end_compact() const { return p_->end(); } begin() const613 inline iterator_type begin() const { return iterator_type(begin_compact(), end_compact()); } end() const614 inline iterator_type end() const { return iterator_type(end_compact(), end_compact()); } size() const615 inline std::size_t size() const { 616 return p_->getPolyLineSize(); 617 } yield()618 inline ActiveTail<Unit>* yield() { return p_; } 619 }; 620 621 template<bool orientT, typename Unit> 622 class PolyLinePolygonWithHolesData { 623 private: 624 ActiveTail<Unit>* p_; 625 public: 626 typedef Unit coordinate_type; 627 typedef typename ActiveTail<Unit>::iterator compact_iterator_type; 628 typedef iterator_compact_to_points<compact_iterator_type, point_data<coordinate_type> > iterator_type; 629 typedef PolyLineHoleData<orientT, Unit> hole_type; 630 typedef typename coordinate_traits<Unit>::area_type area_type; 631 class iteratorHoles { 632 private: 633 typename ActiveTail<Unit>::iteratorHoles itr_; 634 public: iteratorHoles()635 inline iteratorHoles() : itr_() {} iteratorHoles(typename ActiveTail<Unit>::iteratorHoles itr)636 inline iteratorHoles(typename ActiveTail<Unit>::iteratorHoles itr) : itr_(itr) {} 637 //use bitwise copy and assign provided by the compiler operator ++()638 inline iteratorHoles& operator++() { 639 ++itr_; 640 return *this; 641 } operator ++(int)642 inline const iteratorHoles operator++(int) { 643 iteratorHoles tmp(*this); 644 ++(*this); 645 return tmp; 646 } operator ==(const iteratorHoles & that) const647 inline bool operator==(const iteratorHoles& that) const { 648 return itr_ == that.itr_; 649 } operator !=(const iteratorHoles & that) const650 inline bool operator!=(const iteratorHoles& that) const { 651 return itr_ != that.itr_; 652 } operator *()653 inline PolyLineHoleData<orientT, Unit> operator*() { return PolyLineHoleData<orientT, Unit>(*itr_);} 654 }; 655 typedef iteratorHoles iterator_holes_type; 656 PolyLinePolygonWithHolesData()657 inline PolyLinePolygonWithHolesData() : p_(0) {} PolyLinePolygonWithHolesData(ActiveTail<Unit> * p)658 inline PolyLinePolygonWithHolesData(ActiveTail<Unit>* p) : p_(p) {} 659 //use default copy and assign begin_compact() const660 inline compact_iterator_type begin_compact() const { return p_->begin(false, (orientT ? VERTICAL : HORIZONTAL)); } end_compact() const661 inline compact_iterator_type end_compact() const { return p_->end(); } begin() const662 inline iterator_type begin() const { return iterator_type(begin_compact(), end_compact()); } end() const663 inline iterator_type end() const { return iterator_type(end_compact(), end_compact()); } begin_holes() const664 inline iteratorHoles begin_holes() const { return iteratorHoles(p_->beginHoles()); } end_holes() const665 inline iteratorHoles end_holes() const { return iteratorHoles(p_->endHoles()); } yield()666 inline ActiveTail<Unit>* yield() { return p_; } 667 //stub out these four required functions that will not be used but are needed for the interface size_holes() const668 inline std::size_t size_holes() const { return 0; } size() const669 inline std::size_t size() const { return 0; } 670 }; 671 672 673 template <bool orientT, typename Unit, typename polygon_concept_type> 674 struct PolyLineType { }; 675 template <bool orientT, typename Unit> 676 struct PolyLineType<orientT, Unit, polygon_90_with_holes_concept> { typedef PolyLinePolygonWithHolesData<orientT, Unit> type; }; 677 template <bool orientT, typename Unit> 678 struct PolyLineType<orientT, Unit, polygon_45_with_holes_concept> { typedef PolyLinePolygonWithHolesData<orientT, Unit> type; }; 679 template <bool orientT, typename Unit> 680 struct PolyLineType<orientT, Unit, polygon_with_holes_concept> { typedef PolyLinePolygonWithHolesData<orientT, Unit> type; }; 681 template <bool orientT, typename Unit> 682 struct PolyLineType<orientT, Unit, polygon_90_concept> { typedef PolyLineHoleData<orientT, Unit> type; }; 683 template <bool orientT, typename Unit> 684 struct PolyLineType<orientT, Unit, polygon_45_concept> { typedef PolyLineHoleData<orientT, Unit> type; }; 685 template <bool orientT, typename Unit> 686 struct PolyLineType<orientT, Unit, polygon_concept> { typedef PolyLineHoleData<orientT, Unit> type; }; 687 688 template <bool orientT, typename Unit, typename polygon_concept_type> 689 class ScanLineToPolygonItrs { 690 private: 691 std::map<Unit, ActiveTail<Unit>*> tailMap_; 692 typedef typename PolyLineType<orientT, Unit, polygon_concept_type>::type PolyLinePolygonData; 693 std::vector<PolyLinePolygonData> outputPolygons_; 694 bool fractureHoles_; 695 public: 696 typedef typename std::vector<PolyLinePolygonData>::iterator iterator; ScanLineToPolygonItrs()697 inline ScanLineToPolygonItrs() : tailMap_(), outputPolygons_(), fractureHoles_(false) {} 698 /* construct a scanline with the proper offsets, protocol and options */ ScanLineToPolygonItrs(bool fractureHoles)699 inline ScanLineToPolygonItrs(bool fractureHoles) : tailMap_(), outputPolygons_(), fractureHoles_(fractureHoles) {} 700 ~ScanLineToPolygonItrs()701 ~ScanLineToPolygonItrs() { clearOutput_(); } 702 703 /* process all vertical edges, left and right, at a unique x coordinate, edges must be sorted low to high */ 704 void processEdges(iterator& beginOutput, iterator& endOutput, 705 Unit currentX, std::vector<interval_data<Unit> >& leftEdges, 706 std::vector<interval_data<Unit> >& rightEdges, 707 size_t vertexThreshold=(std::numeric_limits<size_t>::max)() ); 708 709 /********************************************************************** 710 *methods implementing new polygon formation code 711 * 712 **********************************************************************/ 713 void updatePartialSimplePolygonsWithRightEdges(Unit currentX, 714 const std::vector<interval_data<Unit> >& leftEdges, size_t threshold); 715 716 void updatePartialSimplePolygonsWithLeftEdges(Unit currentX, 717 const std::vector<interval_data<Unit> >& leftEdges, size_t threshold); 718 719 void closePartialSimplePolygon(Unit, ActiveTail<Unit>*, ActiveTail<Unit>*); 720 721 void maintainPartialSimplePolygonInvariant(iterator& ,iterator& ,Unit, 722 const std::vector<interval_data<Unit> >&, 723 const std::vector<interval_data<Unit> >&, 724 size_t vertexThreshold=(std::numeric_limits<size_t>::max)()); 725 726 void insertNewLeftEdgeIntoTailMap(Unit, Unit, Unit, 727 typename std::map<Unit, ActiveTail<Unit>*>::iterator &); 728 /**********************************************************************/ 729 getTailMapSize()730 inline size_t getTailMapSize(){ 731 typename std::map<Unit, ActiveTail<Unit>* >::const_iterator itr; 732 size_t tsize = 0; 733 for(itr=tailMap_.begin(); itr!=tailMap_.end(); ++itr){ 734 tsize += (itr->second)->getPolyLineSize(); 735 } 736 return tsize; 737 } 738 /*print the active tails in this map:*/ print()739 inline void print(){ 740 typename std::map<Unit, ActiveTail<Unit>* >::const_iterator itr; 741 printf("=========TailMap[%lu]=========\n", tailMap_.size()); 742 for(itr=tailMap_.begin(); itr!=tailMap_.end(); ++itr){ 743 std::cout<< "[" << itr->first << "] : " << std::endl; 744 //print active tail// 745 ActiveTail<Unit> const *t = (itr->second); 746 PolyLine<Unit> const *pBegin = t->getTail(); 747 PolyLine<Unit> const *pEnd = t->getOtherActiveTail()->getTail(); 748 std::string sorient = pBegin->solidToRight() ? "RIGHT" : "LEFT"; 749 std::cout<< " ActiveTail.tailp_ (solid= " << sorient ; 750 End dir = TAIL; 751 while(pBegin!=pEnd){ 752 std::cout << pBegin << "={ "; 753 for(size_t i=0; i<pBegin->numSegments(); i++){ 754 point_data<Unit> u = pBegin->getPoint(i); 755 std::cout << "(" << u.x() << "," << u.y() << ") "; 756 } 757 std::cout << "} "; 758 pBegin = pBegin->next(dir == HEAD ? TAIL : HEAD); 759 dir = pBegin->endConnectivity(dir == HEAD ? TAIL : HEAD); 760 } 761 if(pEnd){ 762 std::cout << pEnd << "={ "; 763 for(size_t i=0; i<pEnd->numSegments(); i++){ 764 point_data<Unit> u = pEnd->getPoint(i); 765 std::cout << "(" << u.x() << "," << u.y() << ") "; 766 } 767 std::cout << "} "; 768 } 769 std::cout << " end= " << pEnd << std::endl; 770 } 771 } 772 773 private: 774 void clearOutput_(); 775 }; 776 777 /* 778 * ScanLine does all the work of stitching together polygons from incoming vertical edges 779 */ 780 // template <typename Unit, typename polygon_concept_type> 781 // class ScanLineToPolygons { 782 // private: 783 // ScanLineToPolygonItrs<true, Unit> scanline_; 784 // public: 785 // inline ScanLineToPolygons() : scanline_() {} 786 // /* construct a scanline with the proper offsets, protocol and options */ 787 // inline ScanLineToPolygons(bool fractureHoles) : scanline_(fractureHoles) {} 788 789 // /* process all vertical edges, left and right, at a unique x coordinate, edges must be sorted low to high */ 790 // inline void processEdges(std::vector<Unit>& outBufferTmp, Unit currentX, std::vector<interval_data<Unit> >& leftEdges, 791 // std::vector<interval_data<Unit> >& rightEdges) { 792 // typename ScanLineToPolygonItrs<true, Unit>::iterator itr, endItr; 793 // scanline_.processEdges(itr, endItr, currentX, leftEdges, rightEdges); 794 // //copy data into outBufferTmp 795 // while(itr != endItr) { 796 // typename PolyLinePolygonData<true, Unit>::iterator pditr; 797 // outBufferTmp.push_back(0); 798 // unsigned int sizeIndex = outBufferTmp.size() - 1; 799 // int count = 0; 800 // for(pditr = (*itr).begin(); pditr != (*itr).end(); ++pditr) { 801 // outBufferTmp.push_back(*pditr); 802 // ++count; 803 // } 804 // outBufferTmp[sizeIndex] = count; 805 // typename PolyLinePolygonData<true, Unit>::iteratorHoles pdHoleItr; 806 // for(pdHoleItr = (*itr).beginHoles(); pdHoleItr != (*itr).endHoles(); ++pdHoleItr) { 807 // outBufferTmp.push_back(0); 808 // unsigned int sizeIndex2 = outBufferTmp.size() - 1; 809 // int count2 = 0; 810 // for(pditr = (*pdHoleItr).begin(); pditr != (*pdHoleItr).end(); ++pditr) { 811 // outBufferTmp.push_back(*pditr); 812 // ++count2; 813 // } 814 // outBufferTmp[sizeIndex2] = -count; 815 // } 816 // ++itr; 817 // } 818 // } 819 // }; 820 821 const int VERTICAL_HEAD = 1, HEAD_TO_TAIL = 2, TAIL_TO_TAIL = 4, SOLID_TO_RIGHT = 8; 822 823 //EVERY FUNCTION in this DEF file should be explicitly defined as inline 824 825 //microsoft compiler improperly warns whenever you cast an integer to bool 826 //call this function on an integer to convert it to bool without a warning 827 template <class T> to_bool(const T & val)828 inline bool to_bool(const T& val) { return val != 0; } 829 830 //default constructor (for preallocation) 831 template <typename Unit> PolyLine()832 inline PolyLine<Unit>::PolyLine() : ptdata_() ,headp_(0), tailp_(0), state_(-1) {} 833 834 //constructor 835 template <typename Unit> PolyLine(orientation_2d orient,Unit coord,Side side)836 inline PolyLine<Unit>::PolyLine(orientation_2d orient, Unit coord, Side side) : 837 ptdata_(1, coord), 838 headp_(0), 839 tailp_(0), 840 state_(orient.to_int() + 841 (side << 3)){} 842 843 //copy constructor 844 template <typename Unit> PolyLine(const PolyLine<Unit> & pline)845 inline PolyLine<Unit>::PolyLine(const PolyLine<Unit>& pline) : ptdata_(pline.ptdata_), 846 headp_(pline.headp_), 847 tailp_(pline.tailp_), 848 state_(pline.state_) {} 849 850 //destructor 851 template <typename Unit> ~PolyLine()852 inline PolyLine<Unit>::~PolyLine() { 853 //clear out data just in case it is read later 854 headp_ = tailp_ = 0; 855 state_ = 0; 856 } 857 858 template <typename Unit> operator =(const PolyLine<Unit> & that)859 inline PolyLine<Unit>& PolyLine<Unit>::operator=(const PolyLine<Unit>& that) { 860 if(!(this == &that)) { 861 headp_ = that.headp_; 862 tailp_ = that.tailp_; 863 ptdata_ = that.ptdata_; 864 state_ = that.state_; 865 } 866 return *this; 867 } 868 869 template <typename Unit> operator ==(const PolyLine<Unit> & b) const870 inline bool PolyLine<Unit>::operator==(const PolyLine<Unit>& b) const { 871 return this == &b || (state_ == b.state_ && 872 headp_ == b.headp_ && 873 tailp_ == b.tailp_); 874 } 875 876 //valid PolyLine 877 template <typename Unit> isValid() const878 inline bool PolyLine<Unit>::isValid() const { 879 return state_ > -1; } 880 881 //first coordinate is an X value 882 //first segment is vertical 883 template <typename Unit> verticalHead() const884 inline bool PolyLine<Unit>::verticalHead() const { 885 return state_ & VERTICAL_HEAD; 886 } 887 888 //retrun true is PolyLine has odd number of coordiantes 889 template <typename Unit> oddLength() const890 inline bool PolyLine<Unit>::oddLength() const { 891 return to_bool((ptdata_.size()-1) % 2); 892 } 893 894 //last coordiante is an X value 895 //last segment is vertical 896 template <typename Unit> verticalTail() const897 inline bool PolyLine<Unit>::verticalTail() const { 898 return to_bool(verticalHead() ^ oddLength()); 899 } 900 901 template <typename Unit> tailOrient() const902 inline orientation_2d PolyLine<Unit>::tailOrient() const { 903 return (verticalTail() ? VERTICAL : HORIZONTAL); 904 } 905 906 template <typename Unit> headOrient() const907 inline orientation_2d PolyLine<Unit>::headOrient() const { 908 return (verticalHead() ? VERTICAL : HORIZONTAL); 909 } 910 911 template <typename Unit> endConnectivity(End end) const912 inline End PolyLine<Unit>::endConnectivity(End end) const { 913 //Tail should be defined as true 914 if(end) { return tailToTail(); } 915 return headToTail(); 916 } 917 918 template <typename Unit> headToTail() const919 inline bool PolyLine<Unit>::headToTail() const { 920 return to_bool(state_ & HEAD_TO_TAIL); 921 } 922 923 template <typename Unit> headToHead() const924 inline bool PolyLine<Unit>::headToHead() const { 925 return to_bool(!headToTail()); 926 } 927 928 template <typename Unit> tailToHead() const929 inline bool PolyLine<Unit>::tailToHead() const { 930 return to_bool(!tailToTail()); 931 } 932 933 template <typename Unit> tailToTail() const934 inline bool PolyLine<Unit>::tailToTail() const { 935 return to_bool(state_ & TAIL_TO_TAIL); 936 } 937 938 template <typename Unit> solidSide() const939 inline Side PolyLine<Unit>::solidSide() const { 940 return solidToRight(); } 941 942 template <typename Unit> solidToRight() const943 inline bool PolyLine<Unit>::solidToRight() const { 944 return to_bool(state_ & SOLID_TO_RIGHT) != 0; 945 } 946 947 template <typename Unit> active() const948 inline bool PolyLine<Unit>::active() const { 949 return !to_bool(tailp_); 950 } 951 952 template <typename Unit> pushCoordinate(Unit coord)953 inline PolyLine<Unit>& PolyLine<Unit>::pushCoordinate(Unit coord) { 954 ptdata_.push_back(coord); 955 return *this; 956 } 957 958 template <typename Unit> popCoordinate()959 inline PolyLine<Unit>& PolyLine<Unit>::popCoordinate() { 960 ptdata_.pop_back(); 961 return *this; 962 } 963 964 template <typename Unit> pushPoint(const point_data<Unit> & point)965 inline PolyLine<Unit>& PolyLine<Unit>::pushPoint(const point_data<Unit>& point) { 966 if(numSegments()){ 967 point_data<Unit> endPt = getEndPoint(); 968 //vertical is true, horizontal is false 969 if((tailOrient().to_int() ? point.get(VERTICAL) == endPt.get(VERTICAL) : point.get(HORIZONTAL) == endPt.get(HORIZONTAL))) { 970 //we were pushing a colinear segment 971 return popCoordinate(); 972 } 973 } 974 return pushCoordinate(tailOrient().to_int() ? point.get(VERTICAL) : point.get(HORIZONTAL)); 975 } 976 977 template <typename Unit> extendTail(Unit delta)978 inline PolyLine<Unit>& PolyLine<Unit>::extendTail(Unit delta) { 979 ptdata_.back() += delta; 980 return *this; 981 } 982 983 //private member function that creates a link from this PolyLine to that 984 template <typename Unit> joinTo_(End thisEnd,PolyLine<Unit> & that,End end)985 inline PolyLine<Unit>& PolyLine<Unit>::joinTo_(End thisEnd, PolyLine<Unit>& that, End end) { 986 if(thisEnd){ 987 tailp_ = &that; 988 state_ &= ~TAIL_TO_TAIL; //clear any previous state_ of bit (for safety) 989 state_ |= (end << 2); //place bit into mask 990 } else { 991 headp_ = &that; 992 state_ &= ~HEAD_TO_TAIL; //clear any previous state_ of bit (for safety) 993 state_ |= (end << 1); //place bit into mask 994 } 995 return *this; 996 } 997 998 //join two PolyLines (both ways of the association) 999 template <typename Unit> joinTo(End thisEnd,PolyLine<Unit> & that,End end)1000 inline PolyLine<Unit>& PolyLine<Unit>::joinTo(End thisEnd, PolyLine<Unit>& that, End end) { 1001 joinTo_(thisEnd, that, end); 1002 that.joinTo_(end, *this, thisEnd); 1003 return *this; 1004 } 1005 1006 //convenience functions for joining PolyLines 1007 template <typename Unit> joinToTail(PolyLine<Unit> & that,End end)1008 inline PolyLine<Unit>& PolyLine<Unit>::joinToTail(PolyLine<Unit>& that, End end) { 1009 return joinTo(TAIL, that, end); 1010 } 1011 template <typename Unit> joinToHead(PolyLine<Unit> & that,End end)1012 inline PolyLine<Unit>& PolyLine<Unit>::joinToHead(PolyLine<Unit>& that, End end) { 1013 return joinTo(HEAD, that, end); 1014 } 1015 template <typename Unit> joinHeadToHead(PolyLine<Unit> & that)1016 inline PolyLine<Unit>& PolyLine<Unit>::joinHeadToHead(PolyLine<Unit>& that) { 1017 return joinToHead(that, HEAD); 1018 } 1019 template <typename Unit> joinHeadToTail(PolyLine<Unit> & that)1020 inline PolyLine<Unit>& PolyLine<Unit>::joinHeadToTail(PolyLine<Unit>& that) { 1021 return joinToHead(that, TAIL); 1022 } 1023 template <typename Unit> joinTailToHead(PolyLine<Unit> & that)1024 inline PolyLine<Unit>& PolyLine<Unit>::joinTailToHead(PolyLine<Unit>& that) { 1025 return joinToTail(that, HEAD); 1026 } 1027 template <typename Unit> joinTailToTail(PolyLine<Unit> & that)1028 inline PolyLine<Unit>& PolyLine<Unit>::joinTailToTail(PolyLine<Unit>& that) { 1029 return joinToTail(that, TAIL); 1030 } 1031 1032 template <typename Unit> disconnectTails()1033 inline PolyLine<Unit>& PolyLine<Unit>::disconnectTails() { 1034 next(TAIL)->state_ &= !TAIL_TO_TAIL; 1035 next(TAIL)->tailp_ = 0; 1036 state_ &= !TAIL_TO_TAIL; 1037 tailp_ = 0; 1038 return *this; 1039 } 1040 1041 template <typename Unit> getEndCoord(End end) const1042 inline Unit PolyLine<Unit>::getEndCoord(End end) const { 1043 if(end) 1044 return ptdata_.back(); 1045 return ptdata_.front(); 1046 } 1047 1048 template <typename Unit> segmentOrient(unsigned int index) const1049 inline orientation_2d PolyLine<Unit>::segmentOrient(unsigned int index) const { 1050 return (to_bool((unsigned int)verticalHead() ^ (index % 2)) ? VERTICAL : HORIZONTAL); 1051 } 1052 1053 template <typename Unit> getPoint(unsigned int index) const1054 inline point_data<Unit> PolyLine<Unit>::getPoint(unsigned int index) const { 1055 //assert(isValid() && headp_->isValid()) ("PolyLine: headp_ must be valid"); 1056 point_data<Unit> pt; 1057 pt.set(HORIZONTAL, ptdata_[index]); 1058 pt.set(VERTICAL, ptdata_[index]); 1059 Unit prevCoord; 1060 if(index == 0) { 1061 prevCoord = headp_->getEndCoord(headToTail()); 1062 } else { 1063 prevCoord = ptdata_[index-1]; 1064 } 1065 pt.set(segmentOrient(index), prevCoord); 1066 return pt; 1067 } 1068 1069 template <typename Unit> getEndPoint(End end) const1070 inline point_data<Unit> PolyLine<Unit>::getEndPoint(End end) const { 1071 return getPoint((end ? numSegments() - 1 : (unsigned int)0)); 1072 } 1073 1074 template <typename Unit> operator [](unsigned int index) const1075 inline Unit PolyLine<Unit>::operator[] (unsigned int index) const { 1076 //assert(ptdata_.size() > index) ("PolyLine: out of bounds index"); 1077 return ptdata_[index]; 1078 } 1079 1080 template <typename Unit> numSegments() const1081 inline unsigned int PolyLine<Unit>::numSegments() const { 1082 return ptdata_.size(); 1083 } 1084 1085 template <typename Unit> next(End end) const1086 inline PolyLine<Unit>* PolyLine<Unit>::next(End end) const { 1087 return (end ? tailp_ : headp_); 1088 } 1089 1090 template <typename Unit> ActiveTail()1091 inline ActiveTail<Unit>::ActiveTail() : tailp_(0), otherTailp_(0), holesList_(), 1092 polyLineSize_(0) {} 1093 1094 template <typename Unit> ActiveTail(orientation_2d orient,Unit coord,Side solidToRight,ActiveTail * otherTailp)1095 inline ActiveTail<Unit>::ActiveTail(orientation_2d orient, Unit coord, Side solidToRight, ActiveTail* otherTailp) : 1096 tailp_(0), otherTailp_(0), holesList_(), polyLineSize_(0) { 1097 tailp_ = createPolyLine(orient, coord, solidToRight); 1098 otherTailp_ = otherTailp; 1099 polyLineSize_ = tailp_->numSegments(); 1100 } 1101 1102 template <typename Unit> ActiveTail(PolyLine<Unit> * active,ActiveTail<Unit> * otherTailp)1103 inline ActiveTail<Unit>::ActiveTail(PolyLine<Unit>* active, ActiveTail<Unit>* otherTailp) : 1104 tailp_(active), otherTailp_(otherTailp), holesList_(), 1105 polyLineSize_(0) {} 1106 1107 //copy constructor 1108 template <typename Unit> ActiveTail(const ActiveTail<Unit> & that)1109 inline ActiveTail<Unit>::ActiveTail(const ActiveTail<Unit>& that) : tailp_(that.tailp_), otherTailp_(that.otherTailp_), holesList_(), polyLineSize_(that.polyLineSize_) {} 1110 1111 //destructor 1112 template <typename Unit> ~ActiveTail()1113 inline ActiveTail<Unit>::~ActiveTail() { 1114 //clear them in case the memory is read later 1115 tailp_ = 0; otherTailp_ = 0; 1116 } 1117 1118 template <typename Unit> operator =(const ActiveTail<Unit> & that)1119 inline ActiveTail<Unit>& ActiveTail<Unit>::operator=(const ActiveTail<Unit>& that) { 1120 //self assignment is safe in this case 1121 tailp_ = that.tailp_; 1122 otherTailp_ = that.otherTailp_; 1123 polyLineSize_ = that.polyLineSize_; 1124 return *this; 1125 } 1126 1127 template <typename Unit> operator ==(const ActiveTail<Unit> & b) const1128 inline bool ActiveTail<Unit>::operator==(const ActiveTail<Unit>& b) const { 1129 return tailp_ == b.tailp_ && otherTailp_ == b.otherTailp_; 1130 } 1131 1132 template <typename Unit> operator <(const ActiveTail<Unit> & b) const1133 inline bool ActiveTail<Unit>::operator<(const ActiveTail<Unit>& b) const { 1134 return tailp_->getEndPoint().get(VERTICAL) < b.tailp_->getEndPoint().get(VERTICAL); 1135 } 1136 1137 template <typename Unit> operator <=(const ActiveTail<Unit> & b) const1138 inline bool ActiveTail<Unit>::operator<=(const ActiveTail<Unit>& b) const { 1139 return !(*this > b); } 1140 1141 template <typename Unit> operator >(const ActiveTail<Unit> & b) const1142 inline bool ActiveTail<Unit>::operator>(const ActiveTail<Unit>& b) const { 1143 return b < (*this); } 1144 1145 template <typename Unit> operator >=(const ActiveTail<Unit> & b) const1146 inline bool ActiveTail<Unit>::operator>=(const ActiveTail<Unit>& b) const { 1147 return !(*this < b); } 1148 1149 template <typename Unit> getTail() const1150 inline PolyLine<Unit>* ActiveTail<Unit>::getTail() const { 1151 return tailp_; } 1152 1153 template <typename Unit> getOtherTail() const1154 inline PolyLine<Unit>* ActiveTail<Unit>::getOtherTail() const { 1155 return otherTailp_->tailp_; } 1156 1157 template <typename Unit> getOtherActiveTail() const1158 inline ActiveTail<Unit>* ActiveTail<Unit>::getOtherActiveTail() const { 1159 return otherTailp_; } 1160 1161 template <typename Unit> isOtherTail(const ActiveTail<Unit> & b)1162 inline bool ActiveTail<Unit>::isOtherTail(const ActiveTail<Unit>& b) { 1163 // assert( (tailp_ == b.getOtherTail() && getOtherTail() == b.tailp_) || 1164 // (tailp_ != b.getOtherTail() && getOtherTail() != b.tailp_)) 1165 // ("ActiveTail: Active tails out of sync"); 1166 return otherTailp_ == &b; 1167 } 1168 1169 template <typename Unit> updateTail(PolyLine<Unit> * newTail)1170 inline ActiveTail<Unit>& ActiveTail<Unit>::updateTail(PolyLine<Unit>* newTail) { 1171 //subtract the old size and add new size// 1172 int delta = newTail->numSegments() - tailp_->numSegments(); 1173 addPolyLineSize(delta); 1174 otherTailp_->addPolyLineSize(delta); 1175 tailp_ = newTail; 1176 return *this; 1177 } 1178 1179 template <typename Unit> addHole(ActiveTail<Unit> * hole,bool fractureHoles)1180 inline ActiveTail<Unit>* ActiveTail<Unit>::addHole(ActiveTail<Unit>* hole, bool fractureHoles) { 1181 1182 if(!fractureHoles){ 1183 holesList_.push_back(hole); 1184 copyHoles(*hole); 1185 copyHoles(*(hole->getOtherActiveTail())); 1186 return this; 1187 } 1188 ActiveTail<Unit>* h, *v; 1189 ActiveTail<Unit>* other = hole->getOtherActiveTail(); 1190 if(other->getOrient() == VERTICAL) { 1191 //assert that hole.getOrient() == HORIZONTAL 1192 //this case should never happen 1193 h = hole; 1194 v = other; 1195 } else { 1196 //assert that hole.getOrient() == VERTICAL 1197 h = other; 1198 v = hole; 1199 } 1200 h->pushCoordinate(v->getCoordinate()); 1201 //assert that h->getOrient() == VERTICAL 1202 //v->pushCoordinate(getCoordinate()); 1203 //assert that v->getOrient() == VERTICAL 1204 //I can't close a figure by adding a hole, so pass zero for xMin and yMin 1205 std::vector<Unit> tmpVec; 1206 ActiveTail<Unit>::joinChains(this, h, false, tmpVec); 1207 return v; 1208 } 1209 1210 template <typename Unit> getHoles() const1211 inline const std::list<ActiveTail<Unit>*>& ActiveTail<Unit>::getHoles() const { 1212 return holesList_; 1213 } 1214 1215 template <typename Unit> copyHoles(ActiveTail<Unit> & that)1216 inline void ActiveTail<Unit>::copyHoles(ActiveTail<Unit>& that) { 1217 holesList_.splice(holesList_.end(), that.holesList_); //splice the two lists together 1218 } 1219 1220 template <typename Unit> solidToRight() const1221 inline bool ActiveTail<Unit>::solidToRight() const { 1222 return getTail()->solidToRight(); } 1223 1224 template <typename Unit> getCoord() const1225 inline Unit ActiveTail<Unit>::getCoord() const { 1226 return getTail()->getEndCoord(); } 1227 1228 template <typename Unit> getCoordinate() const1229 inline Unit ActiveTail<Unit>::getCoordinate() const { 1230 return getCoord(); } 1231 1232 template <typename Unit> getOrient() const1233 inline orientation_2d ActiveTail<Unit>::getOrient() const { 1234 return getTail()->tailOrient(); } 1235 1236 template <typename Unit> pushCoordinate(Unit coord)1237 inline void ActiveTail<Unit>::pushCoordinate(Unit coord) { 1238 //appropriately handle any co-linear polyline segments by calling push point internally 1239 point_data<Unit> p; 1240 p.set(HORIZONTAL, coord); 1241 p.set(VERTICAL, coord); 1242 //if we are vertical assign the last coordinate (an X) to p.x, else to p.y 1243 p.set(getOrient().get_perpendicular(), getCoordinate()); 1244 int oldSegments = tailp_->numSegments(); 1245 tailp_->pushPoint(p); 1246 int delta = tailp_->numSegments() - oldSegments; 1247 addPolyLineSize(delta); 1248 otherTailp_->addPolyLineSize(delta); 1249 } 1250 1251 1252 //global utility functions 1253 template <typename Unit> createPolyLine(orientation_2d orient,Unit coord,Side side)1254 inline PolyLine<Unit>* createPolyLine(orientation_2d orient, Unit coord, Side side) { 1255 return new PolyLine<Unit>(orient, coord, side); 1256 } 1257 1258 template <typename Unit> destroyPolyLine(PolyLine<Unit> * pLine)1259 inline void destroyPolyLine(PolyLine<Unit>* pLine) { 1260 delete pLine; 1261 } 1262 1263 template <typename Unit> createActiveTail()1264 inline ActiveTail<Unit>* createActiveTail() { 1265 //consider replacing system allocator with ActiveTail memory pool 1266 return new ActiveTail<Unit>(); 1267 } 1268 1269 template <typename Unit> destroyActiveTail(ActiveTail<Unit> * aTail)1270 inline void destroyActiveTail(ActiveTail<Unit>* aTail) { 1271 delete aTail; 1272 } 1273 1274 1275 //no recursion, to prevent max recursion depth errors 1276 template <typename Unit> destroyContents()1277 inline void ActiveTail<Unit>::destroyContents() { 1278 tailp_->disconnectTails(); 1279 PolyLine<Unit>* nextPolyLinep = tailp_->next(HEAD); 1280 End end = tailp_->endConnectivity(HEAD); 1281 destroyPolyLine(tailp_); 1282 while(nextPolyLinep) { 1283 End nextEnd = nextPolyLinep->endConnectivity(!end); //get the direction of next polyLine 1284 PolyLine<Unit>* nextNextPolyLinep = nextPolyLinep->next(!end); //get the next polyline 1285 destroyPolyLine(nextPolyLinep); //destroy the current polyline 1286 end = nextEnd; 1287 nextPolyLinep = nextNextPolyLinep; 1288 } 1289 } 1290 1291 template <typename Unit> begin(bool isHole,orientation_2d orient) const1292 inline typename ActiveTail<Unit>::iterator ActiveTail<Unit>::begin(bool isHole, orientation_2d orient) const { 1293 return iterator(this, isHole, orient); 1294 } 1295 1296 template <typename Unit> end() const1297 inline typename ActiveTail<Unit>::iterator ActiveTail<Unit>::end() const { 1298 return iterator(); 1299 } 1300 1301 template <typename Unit> beginHoles() const1302 inline typename ActiveTail<Unit>::iteratorHoles ActiveTail<Unit>::beginHoles() const { 1303 return holesList_.begin(); 1304 } 1305 1306 template <typename Unit> endHoles() const1307 inline typename ActiveTail<Unit>::iteratorHoles ActiveTail<Unit>::endHoles() const { 1308 return holesList_.end(); 1309 } 1310 1311 template <typename Unit> writeOutFigureItrs(iterator & beginOut,iterator & endOut,bool isHole,orientation_2d orient) const1312 inline void ActiveTail<Unit>::writeOutFigureItrs(iterator& beginOut, iterator& endOut, bool isHole, orientation_2d orient) const { 1313 beginOut = begin(isHole, orient); 1314 endOut = end(); 1315 } 1316 1317 template <typename Unit> writeOutFigureHoleItrs(iteratorHoles & beginOut,iteratorHoles & endOut) const1318 inline void ActiveTail<Unit>::writeOutFigureHoleItrs(iteratorHoles& beginOut, iteratorHoles& endOut) const { 1319 beginOut = beginHoles(); 1320 endOut = endHoles(); 1321 } 1322 1323 template <typename Unit> writeOutFigure(std::vector<Unit> & outVec,bool isHole) const1324 inline void ActiveTail<Unit>::writeOutFigure(std::vector<Unit>& outVec, bool isHole) const { 1325 //we start writing out the polyLine that this active tail points to at its tail 1326 std::size_t size = outVec.size(); 1327 outVec.push_back(0); //place holder for size 1328 PolyLine<Unit>* nextPolyLinep = 0; 1329 if(!isHole){ 1330 nextPolyLinep = otherTailp_->tailp_->writeOut(outVec); 1331 } else { 1332 nextPolyLinep = tailp_->writeOut(outVec); 1333 } 1334 Unit firsty = outVec[size + 1]; 1335 if((getOrient() == HORIZONTAL) ^ !isHole) { 1336 //our first coordinate is a y value, so we need to rotate it to the end 1337 typename std::vector<Unit>::iterator tmpItr = outVec.begin(); 1338 tmpItr += size; 1339 outVec.erase(++tmpItr); //erase the 2nd element 1340 } 1341 End startEnd = tailp_->endConnectivity(HEAD); 1342 if(isHole) startEnd = otherTailp_->tailp_->endConnectivity(HEAD); 1343 while(nextPolyLinep) { 1344 bool nextStartEnd = nextPolyLinep->endConnectivity(!startEnd); 1345 nextPolyLinep = nextPolyLinep->writeOut(outVec, startEnd); 1346 startEnd = nextStartEnd; 1347 } 1348 if((getOrient() == HORIZONTAL) ^ !isHole) { 1349 //we want to push the y value onto the end since we ought to have ended with an x 1350 outVec.push_back(firsty); //should never be executed because we want first value to be an x 1351 } 1352 //the vector contains the coordinates of the linked list of PolyLines in the correct order 1353 //first element is supposed to be the size 1354 outVec[size] = outVec.size() - 1 - size; //number of coordinates in vector 1355 //assert outVec[size] % 2 == 0 //it should be even 1356 //make the size negative for holes 1357 outVec[size] *= (isHole ? -1 : 1); 1358 } 1359 1360 //no recursion to prevent max recursion depth errors 1361 template <typename Unit> writeOut(std::vector<Unit> & outVec,End startEnd) const1362 inline PolyLine<Unit>* PolyLine<Unit>::writeOut(std::vector<Unit>& outVec, End startEnd) const { 1363 if(startEnd == HEAD){ 1364 //forward order 1365 outVec.insert(outVec.end(), ptdata_.begin(), ptdata_.end()); 1366 return tailp_; 1367 }else{ 1368 //reverse order 1369 //do not reserve because we expect outVec to be large enough already 1370 for(int i = ptdata_.size() - 1; i >= 0; --i){ 1371 outVec.push_back(ptdata_[i]); 1372 } 1373 //NT didn't know about this version of the API.... 1374 //outVec.insert(outVec.end(), ptdata_.rbegin(), ptdata_.rend()); 1375 return headp_; 1376 } 1377 } 1378 1379 //solid indicates if it was joined by a solit or a space 1380 template <typename Unit> joinChains(ActiveTail<Unit> * at1,ActiveTail<Unit> * at2,bool solid,std::vector<Unit> & outBufferTmp)1381 inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid, std::vector<Unit>& outBufferTmp) 1382 { 1383 //checks to see if we closed a figure 1384 if(at1->isOtherTail(*at2)){ 1385 //value of solid tells us if we closed solid or hole 1386 //and output the solid or handle the hole appropriately 1387 //if the hole needs to fracture across horizontal partition boundary we need to notify 1388 //the calling context to do so 1389 if(solid) { 1390 //the chains are being joined because there is solid to the right 1391 //this means that if the figure is closed at this point it must be a hole 1392 //because otherwise it would have to have another vertex to the right of this one 1393 //and would not be closed at this point 1394 return at1; 1395 } else { 1396 //assert pG != 0 1397 //the figure that was closed is a shell 1398 at1->writeOutFigure(outBufferTmp); 1399 //process holes of the polygon 1400 at1->copyHoles(*at2); //there should not be holes on at2, but if there are, copy them over 1401 const std::list<ActiveTail<Unit>*>& holes = at1->getHoles(); 1402 for(typename std::list<ActiveTail<Unit>*>::const_iterator litr = holes.begin(); litr != holes.end(); ++litr) { 1403 (*litr)->writeOutFigure(outBufferTmp, true); 1404 //delete the hole 1405 (*litr)->destroyContents(); 1406 destroyActiveTail((*litr)->getOtherActiveTail()); 1407 destroyActiveTail((*litr)); 1408 } 1409 //delete the polygon 1410 at1->destroyContents(); 1411 //at2 contents are the same as at1, so it should not destroy them 1412 destroyActiveTail(at1); 1413 destroyActiveTail(at2); 1414 } 1415 return 0; 1416 } 1417 //join the two partial polygons into one large partial polygon 1418 at1->getTail()->joinTailToTail(*(at2->getTail())); 1419 *(at1->getOtherActiveTail()) = ActiveTail(at1->getOtherTail(), at2->getOtherActiveTail()); 1420 *(at2->getOtherActiveTail()) = ActiveTail(at2->getOtherTail(), at1->getOtherActiveTail()); 1421 1422 int accumulate = at2->getPolyLineSize() + at1->getPolyLineSize(); 1423 (at1->getOtherActiveTail())->setPolyLineSize(accumulate); 1424 (at2->getOtherActiveTail())->setPolyLineSize(accumulate); 1425 1426 at1->getOtherActiveTail()->copyHoles(*at1); 1427 at1->getOtherActiveTail()->copyHoles(*at2); 1428 destroyActiveTail(at1); 1429 destroyActiveTail(at2); 1430 return 0; 1431 } 1432 1433 //solid indicates if it was joined by a solit or a space 1434 template <typename Unit> 1435 template <typename PolygonT> joinChains(ActiveTail<Unit> * at1,ActiveTail<Unit> * at2,bool solid,std::vector<PolygonT> & outBufferTmp)1436 inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid, 1437 std::vector<PolygonT>& outBufferTmp) { 1438 //checks to see if we closed a figure 1439 if(at1->isOtherTail(*at2)){ 1440 //value of solid tells us if we closed solid or hole 1441 //and output the solid or handle the hole appropriately 1442 //if the hole needs to fracture across horizontal partition boundary we need to notify 1443 //the calling context to do so 1444 if(solid) { 1445 //the chains are being joined because there is solid to the right 1446 //this means that if the figure is closed at this point it must be a hole 1447 //because otherwise it would have to have another vertex to the right of this one 1448 //and would not be closed at this point 1449 return at1; 1450 } else { 1451 //assert pG != 0 1452 //the figure that was closed is a shell 1453 outBufferTmp.push_back(at1); 1454 at1->copyHoles(*at2); //there should not be holes on at2, but if there are, copy them over 1455 } 1456 return 0; 1457 } 1458 //join the two partial polygons into one large partial polygon 1459 at1->getTail()->joinTailToTail(*(at2->getTail())); 1460 *(at1->getOtherActiveTail()) = ActiveTail<Unit>(at1->getOtherTail(), at2->getOtherActiveTail()); 1461 *(at2->getOtherActiveTail()) = ActiveTail<Unit>(at2->getOtherTail(), at1->getOtherActiveTail()); 1462 1463 int accumulate = at2->getPolyLineSize() + at1->getPolyLineSize(); 1464 (at1->getOtherActiveTail())->setPolyLineSize(accumulate); 1465 (at2->getOtherActiveTail())->setPolyLineSize(accumulate); 1466 1467 at1->getOtherActiveTail()->copyHoles(*at1); 1468 at1->getOtherActiveTail()->copyHoles(*at2); 1469 destroyActiveTail(at1); 1470 destroyActiveTail(at2); 1471 return 0; 1472 } 1473 findAtNext(std::map<TKey,T> & theMap,typename std::map<TKey,T>::iterator pos,const TKey & key)1474 template <class TKey, class T> inline typename std::map<TKey, T>::iterator findAtNext(std::map<TKey, T>& theMap, 1475 typename std::map<TKey, T>::iterator pos, const TKey& key) 1476 { 1477 if(pos == theMap.end()) return theMap.find(key); 1478 //if they match the mapItr is pointing to the correct position 1479 if(pos->first < key) { 1480 return theMap.find(key); 1481 } 1482 if(pos->first > key) { 1483 return theMap.end(); 1484 } 1485 //else they are equal and no need to do anything to the iterator 1486 return pos; 1487 } 1488 1489 // createActiveTailsAsPair is called in these two end cases of geometry 1490 // 1. lower left concave corner 1491 // ###| 1492 // ###| 1493 // ###|### 1494 // ###|### 1495 // 2. lower left convex corner 1496 // |### 1497 // |### 1498 // | 1499 // | 1500 // In case 1 there may be a hole propigated up from the bottom. If the fracture option is enabled 1501 // the two active tails that form the filament fracture line edges can become the new active tail pair 1502 // by pushing x and y onto them. Otherwise the hole simply needs to be associated to one of the new active tails 1503 // with add hole 1504 template <typename Unit> createActiveTailsAsPair(Unit x,Unit y,bool solid,ActiveTail<Unit> * phole,bool fractureHoles)1505 inline std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> createActiveTailsAsPair(Unit x, Unit y, bool solid, ActiveTail<Unit>* phole, bool fractureHoles) { 1506 ActiveTail<Unit>* at1 = 0; 1507 ActiveTail<Unit>* at2 = 0; 1508 if(!phole || !fractureHoles){ 1509 at1 = createActiveTail<Unit>(); 1510 at2 = createActiveTail<Unit>(); 1511 (*at1) = ActiveTail<Unit>(VERTICAL, x, solid, at2); 1512 (*at2) = ActiveTail<Unit>(HORIZONTAL, y, !solid, at1); 1513 //provide a function through activeTail class to provide this 1514 at1->getTail()->joinHeadToHead(*(at2->getTail())); 1515 1516 at1->addPolyLineSize(1); 1517 at2->addPolyLineSize(1); 1518 1519 if(phole) 1520 at1->addHole(phole, fractureHoles); //assert fractureHoles == false 1521 return std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*>(at1, at2); 1522 } 1523 //assert phole is not null 1524 //assert fractureHoles is true 1525 if(phole->getOrient() == VERTICAL) { 1526 at2 = phole; 1527 } else { 1528 at2 = phole->getOtherActiveTail(); //should never be executed since orientation is expected to be vertical 1529 } 1530 //assert solid == false, we should be creating a corner with solid below and to the left if there was a hole 1531 at1 = at2->getOtherActiveTail(); 1532 //assert at1 is horizontal 1533 at1->pushCoordinate(x); 1534 //assert at2 is vertical 1535 at2->pushCoordinate(y); 1536 1537 return std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*>(at1, at2); 1538 } 1539 1540 /* 1541 * | 1542 * | 1543 * = 1544 * |######## 1545 * |######## (add a new ActiveTail in the tailMap_). 1546 * |######## 1547 * |######## 1548 * |######## 1549 * = 1550 * | 1551 * | 1552 * 1553 * NOTE: Call this only if you are sure that the $ledege$ is not in the tailMap_ 1554 */ 1555 template<bool orientT, typename Unit, typename polygon_concept_type> 1556 inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>:: insertNewLeftEdgeIntoTailMap(Unit currentX,Unit yBegin,Unit yEnd,typename std::map<Unit,ActiveTail<Unit> * >::iterator & hint)1557 insertNewLeftEdgeIntoTailMap(Unit currentX, Unit yBegin, Unit yEnd, 1558 typename std::map<Unit, ActiveTail<Unit> *>::iterator &hint){ 1559 ActiveTail<Unit> *currentTail = NULL; 1560 std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = 1561 createActiveTailsAsPair(currentX, yBegin, true, currentTail, 1562 fractureHoles_); 1563 currentTail = tailPair.first; 1564 if(!tailMap_.empty()){ 1565 ++hint; 1566 } 1567 hint = tailMap_.insert(hint, std::make_pair(yBegin, tailPair.second)); 1568 currentTail->pushCoordinate(yEnd); ++hint; 1569 hint = tailMap_.insert(hint, std::make_pair(yEnd, currentTail)); 1570 } 1571 1572 template<bool orientT, typename Unit, typename polygon_concept_type> 1573 inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>:: closePartialSimplePolygon(Unit currentX,ActiveTail<Unit> * pfig,ActiveTail<Unit> * ppfig)1574 closePartialSimplePolygon(Unit currentX, ActiveTail<Unit>*pfig, 1575 ActiveTail<Unit>*ppfig){ 1576 pfig->pushCoordinate(currentX); 1577 ActiveTail<Unit>::joinChains(pfig, ppfig, false, outputPolygons_); 1578 } 1579 /* 1580 * If the invariant is maintained correctly then left edges can do the 1581 * following. 1582 * 1583 * =### 1584 * ####### 1585 * ####### 1586 * ####### 1587 * ####### 1588 * =### 1589 * |### (input left edge) 1590 * |### 1591 * =### 1592 * ####### 1593 * ####### 1594 * =### 1595 */ 1596 template<bool orientT, typename Unit, typename polygon_concept_type> 1597 inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>:: updatePartialSimplePolygonsWithLeftEdges(Unit currentX,const std::vector<interval_data<Unit>> & leftEdges,size_t vertexThreshold)1598 updatePartialSimplePolygonsWithLeftEdges(Unit currentX, 1599 const std::vector<interval_data<Unit> > &leftEdges, size_t vertexThreshold){ 1600 typename std::map<Unit, ActiveTail<Unit>* >::iterator succ, succ1; 1601 typename std::map<Unit, ActiveTail<Unit>* >::iterator pred, pred1, hint; 1602 Unit begin, end; 1603 ActiveTail<Unit> *pfig, *ppfig; 1604 std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair; 1605 size_t pfig_size = 0; 1606 1607 hint = tailMap_.begin(); 1608 for(size_t i=0; i < leftEdges.size(); i++){ 1609 begin = leftEdges[i].get(LOW); end = leftEdges[i].get(HIGH); 1610 succ = findAtNext(tailMap_, hint, begin); 1611 pred = findAtNext(tailMap_, hint, end); 1612 1613 if(succ != tailMap_.end() && pred != tailMap_.end()){ //CASE-1// 1614 //join the corresponding active tails// 1615 pfig = succ->second; ppfig = pred->second; 1616 pfig_size = pfig->getPolyLineSize() + ppfig->getPolyLineSize(); 1617 1618 if(pfig_size >= vertexThreshold){ 1619 size_t bsize = pfig->getPolyLineSize(); 1620 size_t usize = ppfig->getPolyLineSize(); 1621 1622 if(usize+2 < vertexThreshold){ 1623 //cut-off the lower piece (succ1, succ) join (succ1, pred)// 1624 succ1 = succ; --succ1; 1625 assert((succ1 != tailMap_.end()) && 1626 ((succ->second)->getOtherActiveTail() == succ1->second)); 1627 closePartialSimplePolygon(currentX, succ1->second, succ->second); 1628 tailPair = createActiveTailsAsPair<Unit>(currentX, succ1->first, 1629 true, NULL, fractureHoles_); 1630 1631 //just update the succ1 with new ActiveTail<Unit>*// 1632 succ1->second = tailPair.second; 1633 ActiveTail<Unit>::joinChains(tailPair.first, pred->second, true, 1634 outputPolygons_); 1635 }else if(bsize+2 < vertexThreshold){ 1636 //cut-off the upper piece () join ()// 1637 pred1 = pred; ++pred1; 1638 assert(pred1 != tailMap_.end() && 1639 ((pred1->second)->getOtherActiveTail() == pred->second)); 1640 closePartialSimplePolygon(currentX, pred->second, pred1->second); 1641 1642 //just update the pred1 with ActiveTail<Unit>* = pfig// 1643 pred1->second = pfig; 1644 pfig->pushCoordinate(currentX); 1645 pfig->pushCoordinate(pred1->first); 1646 }else{ 1647 //cut both and create an left edge between (pred->first, succ1)// 1648 succ1 = succ; --succ1; 1649 pred1 = pred; ++pred1; 1650 assert(pred1 != tailMap_.end() && succ1 != tailMap_.end()); 1651 assert((pred1->second)->getOtherActiveTail() == pred->second); 1652 assert((succ1->second)->getOtherActiveTail() == succ->second); 1653 1654 closePartialSimplePolygon(currentX, succ1->second, succ->second); 1655 closePartialSimplePolygon(currentX, pred->second, pred1->second); 1656 1657 tailPair = createActiveTailsAsPair<Unit>(currentX, succ1->first, 1658 true, NULL, fractureHoles_); 1659 succ1->second = tailPair.second; 1660 pred1->second = tailPair.first; 1661 (tailPair.first)->pushCoordinate(pred1->first); 1662 } 1663 }else{ 1664 //just join them with closing// 1665 pfig->pushCoordinate(currentX); 1666 ActiveTail<Unit>::joinChains(pfig, ppfig, true, outputPolygons_); 1667 } 1668 hint = pred; ++hint; 1669 tailMap_.erase(succ); tailMap_.erase(pred); 1670 }else if(succ == tailMap_.end() && pred != tailMap_.end()){ //CASE-2// 1671 //succ is missing in the map, first insert it into the map// 1672 tailPair = createActiveTailsAsPair<Unit>(currentX, begin, true, NULL, 1673 fractureHoles_); 1674 hint = pred; ++hint; 1675 hint = tailMap_.insert(hint, std::make_pair(begin, tailPair.second)); 1676 1677 pfig = pred->second; 1678 pfig_size = pfig->getPolyLineSize() + 2; 1679 if(pfig_size >= vertexThreshold){ 1680 //cut-off piece from [pred, pred1] , add [begin, pred1]// 1681 pred1 = pred; ++pred1; 1682 assert((pred1 != tailMap_.end()) && 1683 ((pred1->second)->getOtherActiveTail() == pred->second)); 1684 closePartialSimplePolygon(currentX, pred->second, pred1->second); 1685 1686 //update: we need left edge between (begin, pred1->first)// 1687 pred1->second = tailPair.first; 1688 (tailPair.first)->pushCoordinate(pred1->first); 1689 }else{ 1690 //just join// 1691 ActiveTail<Unit>::joinChains(tailPair.first, pfig, 1692 true, outputPolygons_); 1693 } 1694 tailMap_.erase(pred); 1695 }else if(succ != tailMap_.end() && pred == tailMap_.end()){ //CASE-3// 1696 //pred is missing in the map, first insert it into the map// 1697 hint = succ; ++hint; 1698 hint = tailMap_.insert(hint, std::make_pair(end, (ActiveTail<Unit> *) NULL)); 1699 pfig = succ->second; 1700 pfig_size = pfig->getPolyLineSize() + 2; 1701 if(pfig_size >= vertexThreshold){ 1702 //this figure needs cutting here// 1703 succ1 = succ; --succ1; 1704 assert((succ1 != tailMap_.end()) && 1705 (succ1->second == pfig->getOtherActiveTail())); 1706 ppfig = succ1->second; 1707 closePartialSimplePolygon(currentX, ppfig, pfig); 1708 1709 //update: we need a left edge between (succ1->first, end)// 1710 tailPair = createActiveTailsAsPair<Unit>(currentX, succ1->first, 1711 true, NULL, fractureHoles_); 1712 succ1->second = tailPair.second; 1713 hint->second = tailPair.first; 1714 (tailPair.first)->pushCoordinate(end); 1715 }else{ 1716 //no cutting needed// 1717 hint->second = pfig; 1718 pfig->pushCoordinate(currentX); 1719 pfig->pushCoordinate(end); 1720 } 1721 tailMap_.erase(succ); 1722 }else{ 1723 //insert both pred and succ// 1724 insertNewLeftEdgeIntoTailMap(currentX, begin, end, hint); 1725 } 1726 } 1727 } 1728 1729 template<bool orientT, typename Unit, typename polygon_concept_type> 1730 inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>:: updatePartialSimplePolygonsWithRightEdges(Unit currentX,const std::vector<interval_data<Unit>> & rightEdges,size_t vertexThreshold)1731 updatePartialSimplePolygonsWithRightEdges(Unit currentX, 1732 const std::vector<interval_data<Unit> > &rightEdges, size_t vertexThreshold) 1733 { 1734 1735 typename std::map<Unit, ActiveTail<Unit>* >::iterator succ, pred, hint; 1736 std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair; 1737 Unit begin, end; 1738 size_t i = 0; 1739 //If rightEdges is non-empty Then tailMap_ is non-empty // 1740 assert(rightEdges.empty() || !tailMap_.empty() ); 1741 1742 while( i < rightEdges.size() ){ 1743 //find the interval in the tailMap which contains this interval// 1744 pred = tailMap_.lower_bound(rightEdges[i].get(HIGH)); 1745 assert(pred != tailMap_.end()); 1746 succ = pred; --succ; 1747 assert(pred != succ); 1748 end = pred->first; begin = succ->first; 1749 1750 //we now have a [begin, end] // 1751 bool found_solid_opening = false; 1752 bool erase_succ = true, erase_pred = true; 1753 Unit solid_opening_begin = 0; 1754 Unit solid_opening_end = 0; 1755 size_t j = i+1; 1756 ActiveTail<Unit> *pfig = succ->second; 1757 ActiveTail<Unit> *ppfig = pred->second; 1758 size_t partial_fig_size = pfig->getPolyLineSize(); 1759 //Invariant:// 1760 assert(succ->second && (pfig)->getOtherActiveTail() == ppfig); 1761 1762 hint = succ; 1763 Unit key = rightEdges[i].get(LOW); 1764 if(begin != key){ 1765 found_solid_opening = true; 1766 solid_opening_begin = begin; solid_opening_end = key; 1767 } 1768 1769 while(j < rightEdges.size() && rightEdges[j].get(HIGH) <= end){ 1770 if(rightEdges[j-1].get(HIGH) != rightEdges[j].get(LOW)){ 1771 if(!found_solid_opening){ 1772 found_solid_opening = true; 1773 solid_opening_begin = rightEdges[j-1].get(HIGH); 1774 solid_opening_end = rightEdges[j].get(LOW); 1775 }else{ 1776 ++hint; 1777 insertNewLeftEdgeIntoTailMap(currentX, 1778 rightEdges[j-1].get(HIGH), rightEdges[j].get(LOW), hint); 1779 } 1780 } 1781 j++; 1782 } 1783 1784 //trailing edge// 1785 if(end != rightEdges[j-1].get(HIGH)){ 1786 if(!found_solid_opening){ 1787 found_solid_opening = true; 1788 solid_opening_begin = rightEdges[j-1].get(HIGH); solid_opening_end = end; 1789 }else{ 1790 // a solid opening has been found already, we need to insert a new left 1791 // between [rightEdges[j-1].get(HIGH), end] 1792 Unit lbegin = rightEdges[j-1].get(HIGH); 1793 tailPair = createActiveTailsAsPair<Unit>(currentX, lbegin, true, NULL, 1794 fractureHoles_); 1795 hint = tailMap_.insert(pred, std::make_pair(lbegin, tailPair.second)); 1796 pred->second = tailPair.first; 1797 (tailPair.first)->pushCoordinate(end); 1798 erase_pred = false; 1799 } 1800 } 1801 1802 size_t vertex_delta = ((begin != solid_opening_begin) && 1803 (end != solid_opening_end)) ? 4 : 2; 1804 1805 if(!found_solid_opening){ 1806 //just close the figure, TODO: call closePartialPolygon// 1807 pfig->pushCoordinate(currentX); 1808 ActiveTail<Unit>::joinChains(pfig, ppfig, false, outputPolygons_); 1809 hint = pred; ++hint; 1810 }else if(partial_fig_size+vertex_delta >= vertexThreshold){ 1811 //close the figure and add a pseudo left-edge// 1812 closePartialSimplePolygon(currentX, pfig, ppfig); 1813 assert(begin != solid_opening_begin || end != solid_opening_end); 1814 1815 if(begin != solid_opening_begin && end != solid_opening_end){ 1816 insertNewLeftEdgeIntoTailMap(currentX, solid_opening_begin, 1817 solid_opening_end, hint); 1818 }else if(begin == solid_opening_begin){ 1819 //we just need to update the succ in the tailMap_// 1820 tailPair = createActiveTailsAsPair<Unit>(currentX, solid_opening_begin, 1821 true, NULL, fractureHoles_); 1822 succ->second = tailPair.second; 1823 hint = succ; ++hint; 1824 hint = tailMap_.insert(pred, std::make_pair(solid_opening_end, 1825 tailPair.first)); 1826 (tailPair.first)->pushCoordinate(solid_opening_end); 1827 erase_succ = false; 1828 }else{ 1829 //we just need to update the pred in the tailMap_// 1830 tailPair = createActiveTailsAsPair<Unit>(currentX, solid_opening_begin, 1831 true, NULL, fractureHoles_); 1832 hint = tailMap_.insert(pred, std::make_pair(solid_opening_begin, 1833 tailPair.second)); 1834 pred->second = tailPair.first; 1835 (tailPair.first)->pushCoordinate(solid_opening_end); 1836 erase_pred = false; 1837 } 1838 }else{ 1839 //continue the figure (by adding at-most two new vertices)// 1840 if(begin != solid_opening_begin){ 1841 pfig->pushCoordinate(currentX); 1842 pfig->pushCoordinate(solid_opening_begin); 1843 //insert solid_opening_begin// 1844 hint = succ; ++hint; 1845 hint = tailMap_.insert(hint, std::make_pair(solid_opening_begin, pfig)); 1846 }else{ 1847 erase_succ = false; 1848 } 1849 1850 if(end != solid_opening_end){ 1851 std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = 1852 createActiveTailsAsPair<Unit>(currentX, solid_opening_end, false, 1853 NULL, fractureHoles_); 1854 hint = pred; ++hint; 1855 hint = tailMap_.insert(hint, std::make_pair(solid_opening_end, 1856 tailPair.second)); 1857 ActiveTail<Unit>::joinChains(tailPair.first, ppfig, false, 1858 outputPolygons_); 1859 }else{ 1860 erase_pred = false; 1861 } 1862 } 1863 1864 //Remove the pred and succ if necessary// 1865 if(erase_succ){ 1866 tailMap_.erase(succ); 1867 } 1868 if(erase_pred){ 1869 tailMap_.erase(pred); 1870 } 1871 i = j; 1872 } 1873 } 1874 1875 // Maintains the following invariant: 1876 // a. All the partial polygons formed at any state can be closed 1877 // by a single edge. 1878 template<bool orientT, typename Unit, typename polygon_concept_type> 1879 inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>:: maintainPartialSimplePolygonInvariant(iterator & beginOutput,iterator & endOutput,Unit currentX,const std::vector<interval_data<Unit>> & l,const std::vector<interval_data<Unit>> & r,size_t vertexThreshold)1880 maintainPartialSimplePolygonInvariant(iterator& beginOutput, 1881 iterator& endOutput, Unit currentX, const std::vector<interval_data<Unit> >& l, 1882 const std::vector<interval_data<Unit> >& r, size_t vertexThreshold) { 1883 1884 clearOutput_(); 1885 if(!l.empty()){ 1886 updatePartialSimplePolygonsWithLeftEdges(currentX, l, vertexThreshold); 1887 } 1888 1889 if(!r.empty()){ 1890 updatePartialSimplePolygonsWithRightEdges(currentX, r, vertexThreshold); 1891 } 1892 beginOutput = outputPolygons_.begin(); 1893 endOutput = outputPolygons_.end(); 1894 1895 } 1896 1897 //Process edges connects vertical input edges (right or left edges of figures) to horizontal edges stored as member 1898 //data of the scanline object. It also creates now horizontal edges as needed to construct figures from edge data. 1899 // 1900 //There are only 12 geometric end cases where the scanline intersects a horizontal edge and even fewer unique 1901 //actions to take: 1902 // 1. Solid on both sides of the vertical partition after the current position and space on both sides before 1903 // ###|### 1904 // ###|### 1905 // | 1906 // | 1907 // This case does not need to be handled because there is no vertical edge at the current x coordinate. 1908 // 1909 // 2. Solid on both sides of the vertical partition before the current position and space on both sides after 1910 // | 1911 // | 1912 // ###|### 1913 // ###|### 1914 // This case does not need to be handled because there is no vertical edge at the current x coordinate. 1915 // 1916 // 3. Solid on the left of the vertical partition after the current position and space elsewhere 1917 // ###| 1918 // ###| 1919 // | 1920 // | 1921 // The horizontal edge from the left is found and turns upward because of the vertical right edge to become 1922 // the currently active vertical edge. 1923 // 1924 // 4. Solid on the left of the vertical partion before the current position and space elsewhere 1925 // | 1926 // | 1927 // ###| 1928 // ###| 1929 // The horizontal edge from the left is found and joined to the currently active vertical edge. 1930 // 1931 // 5. Solid to the right above and below and solid to the left above current position. 1932 // ###|### 1933 // ###|### 1934 // |### 1935 // |### 1936 // The horizontal edge from the left is found and joined to the currently active vertical edge, 1937 // potentially closing a hole. 1938 // 1939 // 6. Solid on the left of the vertical partion before the current position and solid to the right above and below 1940 // |### 1941 // |### 1942 // ###|### 1943 // ###|### 1944 // The horizontal edge from the left is found and turns upward because of the vertical right edge to become 1945 // the currently active vertical edge. 1946 // 1947 // 7. Solid on the right of the vertical partition after the current position and space elsewhere 1948 // |### 1949 // |### 1950 // | 1951 // | 1952 // Create two new ActiveTails, one is added to the horizontal edges and the other becomes the vertical currentTail 1953 // 1954 // 8. Solid on the right of the vertical partion before the current position and space elsewhere 1955 // | 1956 // | 1957 // |### 1958 // |### 1959 // The currentTail vertical edge turns right and is added to the horizontal edges data 1960 // 1961 // 9. Solid to the right above and solid to the left above and below current position. 1962 // ###|### 1963 // ###|### 1964 // ###| 1965 // ###| 1966 // The currentTail vertical edge turns right and is added to the horizontal edges data 1967 // 1968 // 10. Solid on the left of the vertical partion above and below the current position and solid to the right below 1969 // ###| 1970 // ###| 1971 // ###|### 1972 // ###|### 1973 // Create two new ActiveTails, one is added to the horizontal edges data and the other becomes the vertical currentTail 1974 // 1975 // 11. Solid to the right above and solid to the left below current position. 1976 // |### 1977 // |### 1978 // ###| 1979 // ###| 1980 // The currentTail vertical edge joins the horizontal edge from the left (may close a polygon) 1981 // Create two new ActiveTails, one is added to the horizontal edges data and the other becomes the vertical currentTail 1982 // 1983 // 12. Solid on the left of the vertical partion above the current position and solid to the right below 1984 // ###| 1985 // ###| 1986 // |### 1987 // |### 1988 // The currentTail vertical edge turns right and is added to the horizontal edges data. 1989 // The horizontal edge from the left turns upward and becomes the currentTail vertical edge 1990 // 1991 template <bool orientT, typename Unit, typename polygon_concept_type> 1992 inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>:: processEdges(iterator & beginOutput,iterator & endOutput,Unit currentX,std::vector<interval_data<Unit>> & leftEdges,std::vector<interval_data<Unit>> & rightEdges,size_t vertexThreshold)1993 processEdges(iterator& beginOutput, iterator& endOutput, 1994 Unit currentX, std::vector<interval_data<Unit> >& leftEdges, 1995 std::vector<interval_data<Unit> >& rightEdges, 1996 size_t vertexThreshold) { 1997 clearOutput_(); 1998 typename std::map<Unit, ActiveTail<Unit>*>::iterator nextMapItr; 1999 //foreach edge 2000 unsigned int leftIndex = 0; 2001 unsigned int rightIndex = 0; 2002 bool bottomAlreadyProcessed = false; 2003 ActiveTail<Unit>* currentTail = 0; 2004 const Unit UnitMax = (std::numeric_limits<Unit>::max)(); 2005 2006 if(vertexThreshold < (std::numeric_limits<size_t>::max)()){ 2007 maintainPartialSimplePolygonInvariant(beginOutput, endOutput, currentX, 2008 leftEdges, rightEdges, vertexThreshold); 2009 return; 2010 } 2011 2012 nextMapItr = tailMap_.begin(); 2013 while(leftIndex < leftEdges.size() || rightIndex < rightEdges.size()) { 2014 interval_data<Unit> edges[2] = {interval_data<Unit> (UnitMax, UnitMax), 2015 interval_data<Unit> (UnitMax, UnitMax)}; 2016 bool haveNextEdge = true; 2017 if(leftIndex < leftEdges.size()) 2018 edges[0] = leftEdges[leftIndex]; 2019 else 2020 haveNextEdge = false; 2021 if(rightIndex < rightEdges.size()) 2022 edges[1] = rightEdges[rightIndex]; 2023 else 2024 haveNextEdge = false; 2025 bool trailingEdge = edges[1].get(LOW) < edges[0].get(LOW); 2026 interval_data<Unit> & edge = edges[trailingEdge]; 2027 interval_data<Unit> & nextEdge = edges[!trailingEdge]; 2028 //process this edge 2029 if(!bottomAlreadyProcessed) { 2030 //assert currentTail = 0 2031 2032 //process the bottom end of this edge 2033 typename std::map<Unit, ActiveTail<Unit>*>::iterator thisMapItr = findAtNext(tailMap_, nextMapItr, edge.get(LOW)); 2034 if(thisMapItr != tailMap_.end()) { 2035 //there is an edge in the map at the low end of this edge 2036 //it needs to turn upward and become the current tail 2037 ActiveTail<Unit>* tail = thisMapItr->second; 2038 if(currentTail) { 2039 //stitch currentTail into this tail 2040 currentTail = tail->addHole(currentTail, fractureHoles_); 2041 if(!fractureHoles_) 2042 currentTail->pushCoordinate(currentX); 2043 } else { 2044 currentTail = tail; 2045 currentTail->pushCoordinate(currentX); 2046 } 2047 //assert currentTail->getOrient() == VERTICAL 2048 nextMapItr = thisMapItr; //set nextMapItr to the next position after this one 2049 ++nextMapItr; 2050 //remove thisMapItr from the map 2051 tailMap_.erase(thisMapItr); 2052 } else { 2053 //there is no edge in the map at the low end of this edge 2054 //we need to create one and another one to be the current vertical tail 2055 //if this is a trailing edge then there is space to the right of the vertical edge 2056 //so pass the inverse of trailingEdge to indicate solid to the right 2057 std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = 2058 createActiveTailsAsPair(currentX, edge.get(LOW), !trailingEdge, currentTail, fractureHoles_); 2059 currentTail = tailPair.first; 2060 tailMap_.insert(nextMapItr, std::pair<Unit, ActiveTail<Unit>*>(edge.get(LOW), tailPair.second)); 2061 // leave nextMapItr unchanged 2062 } 2063 2064 } 2065 if(haveNextEdge && edge.get(HIGH) == nextEdge.get(LOW)) { 2066 //the top of this edge is equal to the bottom of the next edge, process them both 2067 bottomAlreadyProcessed = true; 2068 typename std::map<Unit, ActiveTail<Unit>*>::iterator thisMapItr = findAtNext(tailMap_, nextMapItr, edge.get(HIGH)); 2069 if(thisMapItr == tailMap_.end()) //assert this should never happen 2070 return; 2071 if(trailingEdge) { 2072 //geometry at this position 2073 // |## 2074 // |## 2075 // ----- 2076 // ##| 2077 // ##| 2078 //current tail should join thisMapItr tail 2079 ActiveTail<Unit>* tail = thisMapItr->second; 2080 //pass false because they are being joined because space is to the right and it will close a solid figure 2081 ActiveTail<Unit>::joinChains(currentTail, tail, false, outputPolygons_); 2082 //two new tails are created, the vertical becomes current tail, the horizontal becomes thisMapItr tail 2083 //pass true becuase they are created at the lower left corner of some solid 2084 //pass null because there is no hole pointer possible 2085 std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = 2086 createActiveTailsAsPair<Unit>(currentX, edge.get(HIGH), true, 0, fractureHoles_); 2087 currentTail = tailPair.first; 2088 thisMapItr->second = tailPair.second; 2089 } else { 2090 //geometry at this position 2091 // ##| 2092 // ##| 2093 // ----- 2094 // |## 2095 // |## 2096 //current tail should turn right 2097 currentTail->pushCoordinate(edge.get(HIGH)); 2098 //thisMapItr tail should turn up 2099 thisMapItr->second->pushCoordinate(currentX); 2100 //thisMapItr tail becomes current tail and current tail becomes thisMapItr tail 2101 std::swap(currentTail, thisMapItr->second); 2102 } 2103 nextMapItr = thisMapItr; //set nextMapItr to the next position after this one 2104 ++nextMapItr; 2105 } else { 2106 //there is a gap between the top of this edge and the bottom of the next, process the top of this edge 2107 bottomAlreadyProcessed = false; 2108 //process the top of this edge 2109 typename std::map<Unit, ActiveTail<Unit>*>::iterator thisMapItr = findAtNext(tailMap_, nextMapItr, edge.get(HIGH)); 2110 if(thisMapItr != tailMap_.end()) { 2111 //thisMapItr is pointing to a horizontal edge in the map at the top of this vertical edge 2112 //we need to join them and potentially close a figure 2113 //assert currentTail != 0 2114 ActiveTail<Unit>* tail = thisMapItr->second; 2115 //pass the opositve of trailing edge to mean that they are joined because of solid to the right 2116 currentTail = ActiveTail<Unit>::joinChains(currentTail, tail, !trailingEdge, outputPolygons_); 2117 nextMapItr = thisMapItr; //set nextMapItr to the next position after this one 2118 ++nextMapItr; 2119 if(currentTail) { //figure is not closed// 2120 Unit nextItrY = UnitMax; 2121 if(nextMapItr != tailMap_.end()) { 2122 nextItrY = nextMapItr->first; 2123 } 2124 //for it to be a hole this must have been a left edge 2125 Unit leftY = UnitMax; 2126 if(leftIndex + 1 < leftEdges.size()) 2127 leftY = leftEdges[leftIndex+1].get(LOW); 2128 Unit rightY = nextEdge.get(LOW); 2129 if(!haveNextEdge || (nextItrY < leftY && nextItrY < rightY)) { 2130 //we need to add it to the next edge above it in the map 2131 tail = nextMapItr->second; 2132 tail = tail->addHole(currentTail, fractureHoles_); 2133 if(fractureHoles_) { 2134 //some small additional work stitching in the filament 2135 tail->pushCoordinate(nextItrY); 2136 nextMapItr->second = tail; 2137 } 2138 //set current tail to null 2139 currentTail = 0; 2140 } 2141 } 2142 //delete thisMapItr from the map 2143 tailMap_.erase(thisMapItr); 2144 } else { 2145 //currentTail must turn right and be added into the map 2146 currentTail->pushCoordinate(edge.get(HIGH)); 2147 //assert currentTail->getOrient() == HORIZONTAL 2148 tailMap_.insert(nextMapItr, std::pair<Unit, ActiveTail<Unit>*>(edge.get(HIGH), currentTail)); 2149 //set currentTail to null 2150 currentTail = 0; 2151 //leave nextMapItr unchanged, it is still next 2152 } 2153 } 2154 2155 //increment index 2156 leftIndex += !trailingEdge; 2157 rightIndex += trailingEdge; 2158 } //end while 2159 beginOutput = outputPolygons_.begin(); 2160 endOutput = outputPolygons_.end(); 2161 } //end function 2162 2163 template<bool orientT, typename Unit, typename polygon_concept_type> clearOutput_()2164 inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>::clearOutput_() { 2165 for(std::size_t i = 0; i < outputPolygons_.size(); ++i) { 2166 ActiveTail<Unit>* at1 = outputPolygons_[i].yield(); 2167 const std::list<ActiveTail<Unit>*>& holes = at1->getHoles(); 2168 for(typename std::list<ActiveTail<Unit>*>::const_iterator litr = holes.begin(); litr != holes.end(); ++litr) { 2169 //delete the hole 2170 (*litr)->destroyContents(); 2171 destroyActiveTail((*litr)->getOtherActiveTail()); 2172 destroyActiveTail((*litr)); 2173 } 2174 //delete the polygon 2175 at1->destroyContents(); 2176 //at2 contents are the same as at1, so it should not destroy them 2177 destroyActiveTail((at1)->getOtherActiveTail()); 2178 destroyActiveTail(at1); 2179 } 2180 outputPolygons_.clear(); 2181 } 2182 2183 } //polygon_formation namespace 2184 2185 template <bool orientT, typename Unit> 2186 struct geometry_concept<polygon_formation::PolyLinePolygonWithHolesData<orientT, Unit> > { 2187 typedef polygon_90_with_holes_concept type; 2188 }; 2189 2190 template <bool orientT, typename Unit> 2191 struct geometry_concept<polygon_formation::PolyLineHoleData<orientT, Unit> > { 2192 typedef polygon_90_concept type; 2193 }; 2194 2195 //public API to access polygon formation algorithm 2196 template <typename output_container, typename iterator_type, typename concept_type> get_polygons(output_container & container,iterator_type begin,iterator_type end,orientation_2d orient,bool fracture_holes,concept_type,size_t sliceThreshold=(std::numeric_limits<size_t>::max)())2197 unsigned int get_polygons(output_container& container, 2198 iterator_type begin, iterator_type end, orientation_2d orient, 2199 bool fracture_holes, concept_type, 2200 size_t sliceThreshold = (std::numeric_limits<size_t>::max)() ) { 2201 typedef typename output_container::value_type polygon_type; 2202 typedef typename std::iterator_traits<iterator_type>::value_type::first_type coordinate_type; 2203 polygon_type poly; 2204 unsigned int countPolygons = 0; 2205 typedef typename geometry_concept<polygon_type>::type polygon_concept_type; 2206 polygon_formation::ScanLineToPolygonItrs<true, coordinate_type, polygon_concept_type> scanlineToPolygonItrsV(fracture_holes); 2207 polygon_formation::ScanLineToPolygonItrs<false, coordinate_type, polygon_concept_type> scanlineToPolygonItrsH(fracture_holes); 2208 std::vector<interval_data<coordinate_type> > leftEdges; 2209 std::vector<interval_data<coordinate_type> > rightEdges; 2210 coordinate_type prevPos = (std::numeric_limits<coordinate_type>::max)(); 2211 coordinate_type prevY = (std::numeric_limits<coordinate_type>::max)(); 2212 int count = 0; 2213 for(iterator_type itr = begin; 2214 itr != end; ++ itr) { 2215 coordinate_type pos = (*itr).first; 2216 if(pos != prevPos) { 2217 if(orient == VERTICAL) { 2218 typename polygon_formation::ScanLineToPolygonItrs<true, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd; 2219 scanlineToPolygonItrsV.processEdges(itrPoly, itrPolyEnd, prevPos, 2220 leftEdges, rightEdges, sliceThreshold); 2221 for( ; itrPoly != itrPolyEnd; ++ itrPoly) { 2222 ++countPolygons; 2223 assign(poly, *itrPoly); 2224 container.insert(container.end(), poly); 2225 } 2226 } else { 2227 typename polygon_formation::ScanLineToPolygonItrs<false, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd; 2228 scanlineToPolygonItrsH.processEdges(itrPoly, itrPolyEnd, prevPos, 2229 leftEdges, rightEdges, sliceThreshold); 2230 for( ; itrPoly != itrPolyEnd; ++ itrPoly) { 2231 ++countPolygons; 2232 assign(poly, *itrPoly); 2233 container.insert(container.end(), poly); 2234 } 2235 } 2236 leftEdges.clear(); 2237 rightEdges.clear(); 2238 prevPos = pos; 2239 prevY = (*itr).second.first; 2240 count = (*itr).second.second; 2241 continue; 2242 } 2243 coordinate_type y = (*itr).second.first; 2244 if(count != 0 && y != prevY) { 2245 std::pair<interval_data<coordinate_type>, int> element(interval_data<coordinate_type>(prevY, y), count); 2246 if(element.second == 1) { 2247 if(leftEdges.size() && leftEdges.back().high() == element.first.low()) { 2248 encompass(leftEdges.back(), element.first); 2249 } else { 2250 leftEdges.push_back(element.first); 2251 } 2252 } else { 2253 if(rightEdges.size() && rightEdges.back().high() == element.first.low()) { 2254 encompass(rightEdges.back(), element.first); 2255 } else { 2256 rightEdges.push_back(element.first); 2257 } 2258 } 2259 2260 } 2261 prevY = y; 2262 count += (*itr).second.second; 2263 } 2264 if(orient == VERTICAL) { 2265 typename polygon_formation::ScanLineToPolygonItrs<true, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd; 2266 scanlineToPolygonItrsV.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges, sliceThreshold); 2267 for( ; itrPoly != itrPolyEnd; ++ itrPoly) { 2268 ++countPolygons; 2269 assign(poly, *itrPoly); 2270 container.insert(container.end(), poly); 2271 } 2272 } else { 2273 typename polygon_formation::ScanLineToPolygonItrs<false, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd; 2274 scanlineToPolygonItrsH.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges, sliceThreshold); 2275 2276 for( ; itrPoly != itrPolyEnd; ++ itrPoly) { 2277 ++countPolygons; 2278 assign(poly, *itrPoly); 2279 container.insert(container.end(), poly); 2280 } 2281 } 2282 return countPolygons; 2283 } 2284 2285 } 2286 } 2287 #endif 2288