ceph/src/boost/boost/polygon/detail/polygon_formation.hpp

   1 /*
   2     Copyright 2008 Intel Corporation
   3
   4     Use, modification and distribution are subject to the Boost Software License,
   5     Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6     http://www.boost.org/LICENSE_1_0.txt).
   7 */
   8 #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
 326     inline size_t getPolyLineSize(){
 327        return polyLineSize_;
 328     }
 329
 330     inline void setPolyLineSize(int delta){
 331        polyLineSize_ = delta;
 332     }
 333
 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:
 349       inline iterator() : pLine_(), pLineEnd_(), index_(), indexEnd_(), startEnd_() {}
 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
 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
 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       }
 436       inline const iterator operator++(int) {
 437         iterator tmp(*this);
 438         ++(*this);
 439         return tmp;
 440       }
 441       inline bool operator==(const iterator& that) const {
 442         return pLine_ == that.pLine_ && index_ == that.index_;
 443       }
 444       inline bool operator!=(const iterator& that) const {
 445         return pLine_ != that.pLine_ || index_ != that.index_;
 446       }
 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;
 608     inline PolyLineHoleData() : p_(0) {}
 609     inline PolyLineHoleData(ActiveTail<Unit>* p) : p_(p) {}
 610     //use default copy and assign
 611     inline compact_iterator_type begin_compact() const { return p_->begin(true, (orientT ? VERTICAL : HORIZONTAL)); }
 612     inline compact_iterator_type end_compact() const { return p_->end(); }
 613     inline iterator_type begin() const { return iterator_type(begin_compact(), end_compact()); }
 614     inline iterator_type end() const { return iterator_type(end_compact(), end_compact()); }
 615     inline std::size_t size() const {
 616        return p_->getPolyLineSize();
 617     }
 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:
 635       inline iteratorHoles() : itr_() {}
 636       inline iteratorHoles(typename ActiveTail<Unit>::iteratorHoles itr) : itr_(itr) {}
 637       //use bitwise copy and assign provided by the compiler
 638       inline iteratorHoles& operator++() {
 639         ++itr_;
 640         return *this;
 641       }
 642       inline const iteratorHoles operator++(int) {
 643         iteratorHoles tmp(*this);
 644         ++(*this);
 645         return tmp;
 646       }
 647       inline bool operator==(const iteratorHoles& that) const {
 648         return itr_ == that.itr_;
 649       }
 650       inline bool operator!=(const iteratorHoles& that) const {
 651         return itr_ != that.itr_;
 652       }
 653       inline PolyLineHoleData<orientT, Unit> operator*() { return PolyLineHoleData<orientT, Unit>(*itr_);}
 654     };
 655     typedef iteratorHoles iterator_holes_type;
 656
 657     inline PolyLinePolygonWithHolesData() : p_(0) {}
 658     inline PolyLinePolygonWithHolesData(ActiveTail<Unit>* p) : p_(p) {}
 659     //use default copy and assign
 660     inline compact_iterator_type begin_compact() const { return p_->begin(false, (orientT ? VERTICAL : HORIZONTAL)); }
 661     inline compact_iterator_type end_compact() const { return p_->end(); }
 662     inline iterator_type begin() const { return iterator_type(begin_compact(), end_compact()); }
 663     inline iterator_type end() const { return iterator_type(end_compact(), end_compact()); }
 664     inline iteratorHoles begin_holes() const { return iteratorHoles(p_->beginHoles()); }
 665     inline iteratorHoles end_holes() const { return iteratorHoles(p_->endHoles()); }
 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
 668     inline std::size_t size_holes() const { return 0; }
 669     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;
 697     inline ScanLineToPolygonItrs() : tailMap_(), outputPolygons_(), fractureHoles_(false)  {}
 698     /* construct a scanline with the proper offsets, protocol and options */
 699     inline ScanLineToPolygonItrs(bool fractureHoles) : tailMap_(), outputPolygons_(), fractureHoles_(fractureHoles) {}
 700
 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
 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:*/
 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>
 828   inline bool to_bool(const T& val) { return val != 0; }
 829
 830   //default constructor (for preallocation)
 831   template <typename Unit>
 832   inline PolyLine<Unit>::PolyLine() : ptdata_() ,headp_(0), tailp_(0), state_(-1) {}
 833
 834   //constructor
 835   template <typename Unit>
 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>
 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>
 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>
 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>
 870   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>
 878   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>
 884   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>
 890   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>
 897   inline bool PolyLine<Unit>::verticalTail() const {
 898     return to_bool(verticalHead() ^ oddLength());
 899   }
 900
 901   template <typename Unit>
 902   inline orientation_2d PolyLine<Unit>::tailOrient() const {
 903     return (verticalTail() ? VERTICAL : HORIZONTAL);
 904   }
 905
 906   template <typename Unit>
 907   inline orientation_2d PolyLine<Unit>::headOrient() const {
 908     return (verticalHead() ? VERTICAL : HORIZONTAL);
 909   }
 910
 911   template <typename Unit>
 912   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>
 919   inline bool PolyLine<Unit>::headToTail() const {
 920     return to_bool(state_ & HEAD_TO_TAIL);
 921   }
 922
 923   template <typename Unit>
 924   inline bool PolyLine<Unit>::headToHead() const {
 925     return to_bool(!headToTail());
 926   }
 927
 928   template <typename Unit>
 929   inline bool PolyLine<Unit>::tailToHead() const {
 930     return to_bool(!tailToTail());
 931   }
 932
 933   template <typename Unit>
 934   inline bool PolyLine<Unit>::tailToTail() const {
 935     return to_bool(state_ & TAIL_TO_TAIL);
 936   }
 937
 938   template <typename Unit>
 939   inline Side PolyLine<Unit>::solidSide() const {
 940     return solidToRight(); }
 941
 942   template <typename Unit>
 943   inline bool PolyLine<Unit>::solidToRight() const {
 944     return to_bool(state_ & SOLID_TO_RIGHT) != 0;
 945   }
 946
 947   template <typename Unit>
 948   inline bool PolyLine<Unit>::active() const {
 949     return !to_bool(tailp_);
 950   }
 951
 952   template <typename Unit>
 953   inline PolyLine<Unit>& PolyLine<Unit>::pushCoordinate(Unit coord) {
 954     ptdata_.push_back(coord);
 955     return *this;
 956   }
 957
 958   template <typename Unit>
 959   inline PolyLine<Unit>& PolyLine<Unit>::popCoordinate() {
 960     ptdata_.pop_back();
 961     return *this;
 962   }
 963
 964   template <typename Unit>
 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>
 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>
 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>
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>
1008   inline PolyLine<Unit>& PolyLine<Unit>::joinToTail(PolyLine<Unit>& that, End end) {
1009     return joinTo(TAIL, that, end);
1010   }
1011   template <typename Unit>
1012   inline PolyLine<Unit>& PolyLine<Unit>::joinToHead(PolyLine<Unit>& that, End end) {
1013     return joinTo(HEAD, that, end);
1014   }
1015   template <typename Unit>
1016   inline PolyLine<Unit>& PolyLine<Unit>::joinHeadToHead(PolyLine<Unit>& that) {
1017     return joinToHead(that, HEAD);
1018   }
1019   template <typename Unit>
1020   inline PolyLine<Unit>& PolyLine<Unit>::joinHeadToTail(PolyLine<Unit>& that) {
1021     return joinToHead(that, TAIL);
1022   }
1023   template <typename Unit>
1024   inline PolyLine<Unit>& PolyLine<Unit>::joinTailToHead(PolyLine<Unit>& that) {
1025     return joinToTail(that, HEAD);
1026   }
1027   template <typename Unit>
1028   inline PolyLine<Unit>& PolyLine<Unit>::joinTailToTail(PolyLine<Unit>& that) {
1029     return joinToTail(that, TAIL);
1030   }
1031
1032   template <typename Unit>
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>
1042   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>
1049   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>
1054   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>
1070   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>
1075   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>
1081   inline unsigned int PolyLine<Unit>::numSegments() const {
1082     return ptdata_.size();
1083   }
1084
1085   template <typename Unit>
1086   inline PolyLine<Unit>* PolyLine<Unit>::next(End end) const {
1087     return (end ? tailp_ : headp_);
1088   }
1089
1090   template <typename Unit>
1091   inline ActiveTail<Unit>::ActiveTail() : tailp_(0), otherTailp_(0), holesList_(),
1092    polyLineSize_(0) {}
1093
1094   template <typename Unit>
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>
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>
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>
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>
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>
1128   inline bool ActiveTail<Unit>::operator==(const ActiveTail<Unit>& b) const {
1129     return tailp_ == b.tailp_ && otherTailp_ == b.otherTailp_;
1130   }
1131
1132   template <typename Unit>
1133   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>
1138   inline bool ActiveTail<Unit>::operator<=(const ActiveTail<Unit>& b) const {
1139     return !(*this > b); }
1140
1141   template <typename Unit>
1142   inline bool ActiveTail<Unit>::operator>(const ActiveTail<Unit>& b) const {
1143     return b < (*this); }
1144
1145   template <typename Unit>
1146   inline bool ActiveTail<Unit>::operator>=(const ActiveTail<Unit>& b) const {
1147     return !(*this < b); }
1148
1149   template <typename Unit>
1150   inline PolyLine<Unit>* ActiveTail<Unit>::getTail() const {
1151     return tailp_; }
1152
1153   template <typename Unit>
1154   inline PolyLine<Unit>* ActiveTail<Unit>::getOtherTail() const {
1155     return otherTailp_->tailp_; }
1156
1157   template <typename Unit>
1158   inline ActiveTail<Unit>* ActiveTail<Unit>::getOtherActiveTail() const {
1159     return otherTailp_; }
1160
1161   template <typename Unit>
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>
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>
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>
1211   inline const std::list<ActiveTail<Unit>*>& ActiveTail<Unit>::getHoles() const {
1212     return holesList_;
1213   }
1214
1215   template <typename Unit>
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>
1221   inline bool ActiveTail<Unit>::solidToRight() const {
1222     return getTail()->solidToRight(); }
1223
1224   template <typename Unit>
1225   inline Unit ActiveTail<Unit>::getCoord() const {
1226     return getTail()->getEndCoord(); }
1227
1228   template <typename Unit>
1229   inline Unit ActiveTail<Unit>::getCoordinate() const {
1230     return getCoord(); }
1231
1232   template <typename Unit>
1233   inline orientation_2d ActiveTail<Unit>::getOrient() const {
1234     return getTail()->tailOrient(); }
1235
1236   template <typename Unit>
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>
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>
1259   inline void destroyPolyLine(PolyLine<Unit>* pLine) {
1260     delete pLine;
1261   }
1262
1263   template <typename Unit>
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>
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>
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>
1292   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>
1297   inline typename ActiveTail<Unit>::iterator ActiveTail<Unit>::end() const {
1298     return iterator();
1299   }
1300
1301   template <typename Unit>
1302   inline typename ActiveTail<Unit>::iteratorHoles ActiveTail<Unit>::beginHoles() const {
1303     return holesList_.begin();
1304   }
1305
1306   template <typename Unit>
1307   inline typename ActiveTail<Unit>::iteratorHoles ActiveTail<Unit>::endHoles() const {
1308     return holesList_.end();
1309   }
1310
1311   template <typename Unit>
1312   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>
1318   inline void ActiveTail<Unit>::writeOutFigureHoleItrs(iteratorHoles& beginOut, iteratorHoles& endOut) const {
1319     beginOut = beginHoles();
1320     endOut = endHoles();
1321   }
1322
1323   template <typename Unit>
1324   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>
1362   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>
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>
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
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>
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>::
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>::
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>::
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>::
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>::
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>::
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>
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>
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