[Boost-commit] svn:boost r85061 - in trunk: boost/polygon boost/polygon/detail libs/polygon/test

Subject: [Boost-commit] svn:boost r85061 - in trunk: boost/polygon boost/polygon/detail libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2013-07-17 16:43:55

Author: asydorchuk
Date: 2013-07-17 16:43:55 EDT (Wed, 17 Jul 2013)
New Revision: 85061
URL: http://svn.boost.org/trac/boost/changeset/85061

Log:
Polygon: Merging patch provided by Intel into trunk: "Fracturing enhancement to boost::polygon::polygon_90_set_data"

Text files modified: 
   trunk/boost/polygon/detail/polygon_formation.hpp |   790 ++++++++++++++++++++++++++++++++------- 
   trunk/boost/polygon/polygon_90_set_data.hpp      |    28 +                                       
   trunk/libs/polygon/test/gtl_boost_unit_test.cpp  |   248 ++++++++++++                            
   3 files changed, 922 insertions(+), 144 deletions(-)

Modified: trunk/boost/polygon/detail/polygon_formation.hpp
==============================================================================
--- trunk/boost/polygon/detail/polygon_formation.hpp	Wed Jul 17 10:38:39 2013	(r85060)
+++ trunk/boost/polygon/detail/polygon_formation.hpp	2013-07-17 16:43:55 EDT (Wed, 17 Jul 2013)	(r85061)
@@ -1,10 +1,12 @@
 /*
     Copyright 2008 Intel Corporation
-
+ 
     Use, modification and distribution are subject to the Boost Software License,
     Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
     http://www.boost.org/LICENSE_1_0.txt).
 */
+#include<iostream>
+#include<cassert>
 #ifndef BOOST_POLYGON_POLYGON_FORMATION_HPP
 #define BOOST_POLYGON_POLYGON_FORMATION_HPP
 namespace boost { namespace polygon{
@@ -25,24 +27,24 @@
    * TAIL End is represented by true because TAIL comes after head and 1 after 0
    */
   const End TAIL = true;
-
+   
   /*
    * 2D turning direction, left and right sides (is a boolean value since it has two states.)
    */
   typedef bool Side;
-
+   
   /*
    * LEFT Side is 0 because we inuitively think left to right; left < right
    */
   const Side LEFT = false;
-
+   
   /*
    * RIGHT Side is 1 so that right > left
    */
   const Side RIGHT = true;
 
   /*
-   * The PolyLine class is data storage and services for building and representing partial polygons.
+   * The PolyLine class is data storage and services for building and representing partial polygons.  
    * As the polyline is added to it extends its storage to accomodate the data.
    * PolyLines can be joined head-to-head/head-to-tail when it is determined that two polylines are
    * part of the same polygon.
@@ -59,14 +61,14 @@
   class PolyLine {
   private:
     //data
-
+     
     /*
      * ptdata_ a vector of coordiantes
      * if VERTICAL_HEAD, first coordiante is an X
      * else first coordinate is a Y
      */
     std::vector<Unit> ptdata_;
-
+   
     /*
      * head and tail points to other polylines before and after this in a chain
      */
@@ -87,18 +89,18 @@
      * default constructor (for preallocation)
      */
     PolyLine();
-
+   
     /*
      * constructor that takes the orientation, coordiante and side to which there is solid
      */
     PolyLine(orientation_2d orient, Unit coord, Side side);
-
+   
     //copy constructor
     PolyLine(const PolyLine& pline);
-
+   
     //destructor
     ~PolyLine();
-
+   
     //assignment operator
     PolyLine& operator=(const PolyLine& that);
 
@@ -118,18 +120,18 @@
     /*
      * returns true if first coordinate is an X value (first segment is vertical)
      */
-    bool verticalHead() const;
+    bool verticalHead() const; 
 
     /*
      * returns the orientation_2d fo the tail
      */
     orientation_2d tailOrient() const;
-
+      
     /*
      * returns true if last coordinate is an X value (last segment is vertical)
      */
     bool verticalTail() const;
-
+     
     /*
      * retrun true if PolyLine has odd number of coordiantes
      */
@@ -157,7 +159,7 @@
      * retrun true if the tail of this polyline is connect to the head of a polyline
      */
     bool tailToHead() const;
-
+     
     /*
      * retrun the side on which there is solid for this polyline
      */
@@ -177,12 +179,12 @@
      * adds a coordinate value to the end of the polyline changing the tail orientation
      */
     PolyLine& pushCoordinate(Unit coord);
-
+       
     /*
      * removes a coordinate value at the end of the polyline changing the tail orientation
      */
     PolyLine& popCoordinate();
-
+      
     /*
      * extends the tail of the polyline to include the point, changing orientation if needed
      */
@@ -299,7 +301,7 @@
    * that edge is supposed to be solid or space.  Any incomplete polygon will have two active tails.  Active tails
    * may be joined together to merge two incomplete polygons into a larger incomplete polygon.  If two active tails
    * that are to be merged are the oppositve ends of the same incomplete polygon that indicates that the polygon
-   * has been closed and is complete.  The active tail keeps a pointer to the other active tail of its incomplete
+   * has been closed and is complete.  The active tail keeps a pointer to the other active tail of its incomplete 
    * polygon so that it is easy to check this condition.  These pointers are updated when active tails are joined.
    * The active tail also keeps a list of pointers to active tail objects that serve as handles to closed holes.  In
    * this way a hole can be associated to another incomplete polygon, which will eventually be its enclosing shell,
@@ -314,11 +316,25 @@
   class ActiveTail {
   private:
     //data
-    PolyLine<Unit>* tailp_;
+    PolyLine<Unit>* tailp_; 
     ActiveTail *otherTailp_;
     std::list<ActiveTail*> holesList_;
+    //Sum of all the polylines which constitute the active tail (including holes)//
+    size_t polyLineSize_;  
   public:
 
+    inline size_t getPolyLineSize(){
+       return polyLineSize_;
+    }
+
+    inline void setPolyLineSize(int delta){
+       polyLineSize_ = delta;
+    }
+
+    inline void addPolyLineSize(int delta){
+       polyLineSize_ += delta;
+    }
+    
     /*
      * iterator over coordinates of the figure
      */
@@ -331,7 +347,7 @@
       End startEnd_;
     public:
       inline iterator() : pLine_(), pLineEnd_(), index_(), indexEnd_(), startEnd_() {}
-      inline iterator(const ActiveTail* at, bool isHole, orientation_2d orient) :
+      inline iterator(const ActiveTail* at, bool isHole, orientation_2d orient) : 
         pLine_(), pLineEnd_(), index_(), indexEnd_(), startEnd_() {
         //if it is a hole and orientation is vertical or it is not a hole and orientation is horizontal
         //we want to use this active tail, otherwise we want to use the other active tail
@@ -343,7 +359,10 @@
         //now we have the right winding direction
         //if it is horizontal we need to skip the first element
         pLine_ = at->getTail();
-        index_ = at->getTail()->numSegments() - 1;
+
+        if(at->getTail()->numSegments() > 0)
+         index_ = at->getTail()->numSegments() - 1;
+
         if((at->getOrient() == HORIZONTAL) ^ (orient == HORIZONTAL)) {
           pLineEnd_ = at->getTail();
           indexEnd_ = pLineEnd_->numSegments() - 1;
@@ -358,10 +377,27 @@
           } else { --index_; }
         } else {
           pLineEnd_ = at->getOtherActiveTail()->getTail();
+          if(pLineEnd_->numSegments() > 0)
           indexEnd_ = pLineEnd_->numSegments() - 1;
         }
         at->getTail()->joinTailToTail(*(at->getOtherActiveTail()->getTail()));
       }
+
+      inline size_t size(void){
+        size_t count = 0;
+        End dir = startEnd_;
+        PolyLine<Unit> const * currLine = pLine_;
+        size_t ops = 0;
+        while(currLine != pLineEnd_){
+           ops++;
+           count += currLine->numSegments();
+           currLine = currLine->next(dir == HEAD ? TAIL : HEAD); 
+           dir = currLine->endConnectivity(dir == HEAD ? TAIL : HEAD); 
+        }
+        count += pLineEnd_->numSegments();
+        return count; //no. of vertices 
+      }
+
       //use bitwise copy and assign provided by the compiler
       inline iterator& operator++() {
         if(pLine_ == pLineEnd_ && index_ == indexEnd_) {
@@ -560,7 +596,7 @@
   /* deallocate an activetail object */
   template <typename Unit>
   void destroyActiveTail(ActiveTail<Unit>* aTail);
-
+     
   template<bool orientT, typename Unit>
   class PolyLineHoleData {
   private:
@@ -576,7 +612,9 @@
     inline compact_iterator_type end_compact() const { return p_->end(); }
     inline iterator_type begin() const { return iterator_type(begin_compact(), end_compact()); }
     inline iterator_type end() const { return iterator_type(end_compact(), end_compact()); }
-    inline std::size_t size() const { return 0; }
+    inline std::size_t size() const { 
+       return p_->getPolyLineSize();
+    }
     inline ActiveTail<Unit>* yield() { return p_; }
     template<class iT>
     inline PolyLineHoleData& set(iT inputBegin, iT inputEnd) {
@@ -586,7 +624,7 @@
     inline PolyLineHoleData& set_compact(iT inputBegin, iT inputEnd) {
       return *this;
     }
-
+   
   };
 
   template<bool orientT, typename Unit>
@@ -646,7 +684,7 @@
     inline PolyLinePolygonWithHolesData& set_compact(iT inputBegin, iT inputEnd) {
       return *this;
     }
-
+   
     // initialize a polygon from x,y values, it is assumed that the first is an x
     // and that the input is a well behaved polygon
     template<class iT>
@@ -679,18 +717,83 @@
     std::vector<PolyLinePolygonData> outputPolygons_;
     bool fractureHoles_;
   public:
-    typedef typename std::vector<PolyLinePolygonData>::iterator iterator;
+    typedef typename std::vector<PolyLinePolygonData>::iterator iterator; 
     inline ScanLineToPolygonItrs() : tailMap_(), outputPolygons_(), fractureHoles_(false)  {}
     /* construct a scanline with the proper offsets, protocol and options */
     inline ScanLineToPolygonItrs(bool fractureHoles) : tailMap_(), outputPolygons_(), fractureHoles_(fractureHoles) {}
-
+   
     ~ScanLineToPolygonItrs() { clearOutput_(); }
-
+   
     /* process all vertical edges, left and right, at a unique x coordinate, edges must be sorted low to high */
-    void processEdges(iterator& beginOutput, iterator& endOutput,
-                      Unit currentX, std::vector<interval_data<Unit> >& leftEdges,
-                      std::vector<interval_data<Unit> >& rightEdges);
-
+    void processEdges(iterator& beginOutput, iterator& endOutput, 
+                      Unit currentX, std::vector<interval_data<Unit> >& leftEdges, 
+                      std::vector<interval_data<Unit> >& rightEdges,
+                      size_t vertexThreshold=std::numeric_limits<size_t>::max() );
+    
+   /**********************************************************************
+    *methods implementing new polygon formation code                                                                    
+    *
+    **********************************************************************/
+    void updatePartialSimplePolygonsWithRightEdges(Unit currentX, 
+         const std::vector<interval_data<Unit> >& leftEdges, size_t threshold);
+
+    void updatePartialSimplePolygonsWithLeftEdges(Unit currentX, 
+         const std::vector<interval_data<Unit> >& leftEdges, size_t threshold);
+
+    void closePartialSimplePolygon(Unit, ActiveTail<Unit>*, ActiveTail<Unit>*);
+
+    void maintainPartialSimplePolygonInvariant(iterator& ,iterator& ,Unit,
+         const std::vector<interval_data<Unit> >&, 
+         const std::vector<interval_data<Unit> >&, 
+         size_t vertexThreshold=std::numeric_limits<size_t>::max());
+
+    void insertNewLeftEdgeIntoTailMap(Unit, Unit, Unit,
+      typename std::map<Unit, ActiveTail<Unit>*>::iterator &);
+    /**********************************************************************/
+
+    inline size_t getTailMapSize(){
+       typename std::map<Unit, ActiveTail<Unit>* >::const_iterator itr;
+       size_t tsize = 0;
+       for(itr=tailMap_.begin(); itr!=tailMap_.end(); ++itr){
+          tsize +=  (itr->second)->getPolyLineSize();
+       }
+       return tsize;
+    }
+   /*print the active tails in this map:*/
+   inline void print(){
+      typename std::map<Unit, ActiveTail<Unit>* >::const_iterator itr;
+      printf("=========TailMap[%lu]=========\n", tailMap_.size());
+      for(itr=tailMap_.begin(); itr!=tailMap_.end(); ++itr){
+         std::cout<< "[" << itr->first << "] : " << std::endl;
+         //print active tail//
+         ActiveTail<Unit> const *t = (itr->second);
+         PolyLine<Unit> const *pBegin = t->getTail();
+         PolyLine<Unit> const *pEnd = t->getOtherActiveTail()->getTail();
+         std::string sorient = pBegin->solidToRight() ? "RIGHT" : "LEFT"; 
+         std::cout<< " ActiveTail.tailp_ (solid= " << sorient ;
+         End dir = TAIL;
+         while(pBegin!=pEnd){
+            std::cout << pBegin  << "={ ";
+            for(size_t i=0; i<pBegin->numSegments(); i++){
+               point_data<Unit> u = pBegin->getPoint(i);
+               std::cout << "(" << u.x() << "," << u.y() << ") ";
+            }
+            std::cout << "}  ";
+            pBegin = pBegin->next(dir == HEAD ? TAIL : HEAD);
+            dir = pBegin->endConnectivity(dir == HEAD ? TAIL : HEAD);
+         }
+         if(pEnd){
+            std::cout << pEnd << "={ ";
+            for(size_t i=0; i<pEnd->numSegments(); i++){
+               point_data<Unit> u = pEnd->getPoint(i);
+               std::cout << "(" << u.x() << "," << u.y() << ") ";
+            }
+            std::cout << "}  ";
+         }
+         std::cout << " end= " << pEnd << std::endl;
+      }
+   }
+   
   private:
     void clearOutput_();
   };
@@ -706,9 +809,9 @@
 //     inline ScanLineToPolygons() : scanline_() {}
 //     /* construct a scanline with the proper offsets, protocol and options */
 //     inline ScanLineToPolygons(bool fractureHoles) : scanline_(fractureHoles) {}
-
+   
 //     /* process all vertical edges, left and right, at a unique x coordinate, edges must be sorted low to high */
-//     inline void processEdges(std::vector<Unit>& outBufferTmp, Unit currentX, std::vector<interval_data<Unit> >& leftEdges,
+//     inline void processEdges(std::vector<Unit>& outBufferTmp, Unit currentX, std::vector<interval_data<Unit> >& leftEdges, 
 //                              std::vector<interval_data<Unit> >& rightEdges) {
 //       typename ScanLineToPolygonItrs<true, Unit>::iterator itr, endItr;
 //       scanline_.processEdges(itr, endItr, currentX, leftEdges, rightEdges);
@@ -754,12 +857,12 @@
 
   //constructor
   template <typename Unit>
-  inline PolyLine<Unit>::PolyLine(orientation_2d orient, Unit coord, Side side) :
+  inline PolyLine<Unit>::PolyLine(orientation_2d orient, Unit coord, Side side) : 
     ptdata_(1, coord),
     headp_(0),
     tailp_(0),
     state_(orient.to_int() +
-           (side << 3)) {}
+           (side << 3)){}
 
   //copy constructor
   template <typename Unit>
@@ -796,7 +899,7 @@
 
   //valid PolyLine
   template <typename Unit>
-  inline bool PolyLine<Unit>::isValid() const {
+  inline bool PolyLine<Unit>::isValid() const { 
     return state_ > -1; }
 
   //first coordinate is an X value
@@ -818,7 +921,7 @@
   inline bool PolyLine<Unit>::verticalTail() const {
     return to_bool(verticalHead() ^ oddLength());
   }
-
+     
   template <typename Unit>
   inline orientation_2d PolyLine<Unit>::tailOrient() const {
     return (verticalTail() ? VERTICAL : HORIZONTAL);
@@ -850,16 +953,16 @@
   inline bool PolyLine<Unit>::tailToHead() const {
     return to_bool(!tailToTail());
   }
-
+     
   template <typename Unit>
   inline bool PolyLine<Unit>::tailToTail() const {
     return to_bool(state_ & TAIL_TO_TAIL);
   }
 
   template <typename Unit>
-  inline Side PolyLine<Unit>::solidSide() const {
+  inline Side PolyLine<Unit>::solidSide() const { 
     return solidToRight(); }
-
+      
   template <typename Unit>
   inline bool PolyLine<Unit>::solidToRight() const {
     return to_bool(state_ & SOLID_TO_RIGHT) != 0;
@@ -884,12 +987,14 @@
 
   template <typename Unit>
   inline PolyLine<Unit>& PolyLine<Unit>::pushPoint(const point_data<Unit>& point) {
-    point_data<Unit> endPt = getEndPoint();
-    //vertical is true, horizontal is false
-    if((tailOrient().to_int() ? point.get(VERTICAL) == endPt.get(VERTICAL) : point.get(HORIZONTAL) == endPt.get(HORIZONTAL))) {
-      //we were pushing a colinear segment
-      return popCoordinate();
-    }
+     if(numSegments()){
+       point_data<Unit> endPt = getEndPoint();
+       //vertical is true, horizontal is false
+       if((tailOrient().to_int() ? point.get(VERTICAL) == endPt.get(VERTICAL) : point.get(HORIZONTAL) == endPt.get(HORIZONTAL))) {
+         //we were pushing a colinear segment
+         return popCoordinate();
+       }
+     }
     return pushCoordinate(tailOrient().to_int() ? point.get(VERTICAL) : point.get(HORIZONTAL));
   }
 
@@ -1007,28 +1112,31 @@
   }
 
   template <typename Unit>
-  inline ActiveTail<Unit>::ActiveTail() : tailp_(0), otherTailp_(0), holesList_() {}
+  inline ActiveTail<Unit>::ActiveTail() : tailp_(0), otherTailp_(0), holesList_(), 
+   polyLineSize_(0) {}
 
   template <typename Unit>
-  inline ActiveTail<Unit>::ActiveTail(orientation_2d orient, Unit coord, Side solidToRight, ActiveTail* otherTailp) :
-    tailp_(0), otherTailp_(0), holesList_() {
+  inline ActiveTail<Unit>::ActiveTail(orientation_2d orient, Unit coord, Side solidToRight, ActiveTail* otherTailp) : 
+    tailp_(0), otherTailp_(0), holesList_(), polyLineSize_(0) {
     tailp_ = createPolyLine(orient, coord, solidToRight);
     otherTailp_ = otherTailp;
+    polyLineSize_ = tailp_->numSegments();
   }
 
   template <typename Unit>
-  inline ActiveTail<Unit>::ActiveTail(PolyLine<Unit>* active, ActiveTail<Unit>* otherTailp) :
-    tailp_(active), otherTailp_(otherTailp), holesList_() {}
+  inline ActiveTail<Unit>::ActiveTail(PolyLine<Unit>* active, ActiveTail<Unit>* otherTailp) : 
+    tailp_(active), otherTailp_(otherTailp), holesList_(), 
+      polyLineSize_(0) {}
 
   //copy constructor
   template <typename Unit>
-  inline ActiveTail<Unit>::ActiveTail(const ActiveTail<Unit>& that) : tailp_(that.tailp_), otherTailp_(that.otherTailp_), holesList_() {}
+  inline ActiveTail<Unit>::ActiveTail(const ActiveTail<Unit>& that) : tailp_(that.tailp_), otherTailp_(that.otherTailp_), holesList_(), polyLineSize_(that.polyLineSize_) {}
 
   //destructor
   template <typename Unit>
-  inline ActiveTail<Unit>::~ActiveTail() {
+  inline ActiveTail<Unit>::~ActiveTail() { 
     //clear them in case the memory is read later
-    tailp_ = 0; otherTailp_ = 0;
+    tailp_ = 0; otherTailp_ = 0; 
   }
 
   template <typename Unit>
@@ -1036,6 +1144,7 @@
     //self assignment is safe in this case
     tailp_ = that.tailp_;
     otherTailp_ = that.otherTailp_;
+    polyLineSize_ = that.polyLineSize_;
     return *this;
   }
 
@@ -1050,45 +1159,50 @@
   }
 
   template <typename Unit>
-  inline bool ActiveTail<Unit>::operator<=(const ActiveTail<Unit>& b) const {
+  inline bool ActiveTail<Unit>::operator<=(const ActiveTail<Unit>& b) const { 
     return !(*this > b); }
-
+   
   template <typename Unit>
-  inline bool ActiveTail<Unit>::operator>(const ActiveTail<Unit>& b) const {
+  inline bool ActiveTail<Unit>::operator>(const ActiveTail<Unit>& b) const { 
     return b < (*this); }
-
+   
   template <typename Unit>
-  inline bool ActiveTail<Unit>::operator>=(const ActiveTail<Unit>& b) const {
+  inline bool ActiveTail<Unit>::operator>=(const ActiveTail<Unit>& b) const { 
     return !(*this < b); }
 
   template <typename Unit>
-  inline PolyLine<Unit>* ActiveTail<Unit>::getTail() const {
+  inline PolyLine<Unit>* ActiveTail<Unit>::getTail() const { 
     return tailp_; }
 
   template <typename Unit>
-  inline PolyLine<Unit>* ActiveTail<Unit>::getOtherTail() const {
+  inline PolyLine<Unit>* ActiveTail<Unit>::getOtherTail() const { 
     return otherTailp_->tailp_; }
 
   template <typename Unit>
-  inline ActiveTail<Unit>* ActiveTail<Unit>::getOtherActiveTail() const {
+  inline ActiveTail<Unit>* ActiveTail<Unit>::getOtherActiveTail() const { 
     return otherTailp_; }
 
   template <typename Unit>
   inline bool ActiveTail<Unit>::isOtherTail(const ActiveTail<Unit>& b) {
     //       assert( (tailp_ == b.getOtherTail() && getOtherTail() == b.tailp_) ||
-    //                     (tailp_ != b.getOtherTail() && getOtherTail() != b.tailp_))
+    //                     (tailp_ != b.getOtherTail() && getOtherTail() != b.tailp_)) 
     //         ("ActiveTail: Active tails out of sync");
     return otherTailp_ == &b;
   }
 
   template <typename Unit>
   inline ActiveTail<Unit>& ActiveTail<Unit>::updateTail(PolyLine<Unit>* newTail) {
+    //subtract the old size and add new size//
+    int delta = newTail->numSegments() - tailp_->numSegments();
+    addPolyLineSize(delta);
+    otherTailp_->addPolyLineSize(delta);
     tailp_ = newTail;
     return *this;
   }
 
   template <typename Unit>
   inline ActiveTail<Unit>* ActiveTail<Unit>::addHole(ActiveTail<Unit>* hole, bool fractureHoles) {
+
     if(!fractureHoles){
       holesList_.push_back(hole);
       copyHoles(*hole);
@@ -1100,7 +1214,7 @@
     if(other->getOrient() == VERTICAL) {
       //assert that hole.getOrient() == HORIZONTAL
       //this case should never happen
-      h = hole;
+      h = hole;  
       v = other;
     } else {
       //assert that hole.getOrient() == VERTICAL
@@ -1128,30 +1242,34 @@
   }
 
   template <typename Unit>
-  inline bool ActiveTail<Unit>::solidToRight() const {
+  inline bool ActiveTail<Unit>::solidToRight() const { 
     return getTail()->solidToRight(); }
 
   template <typename Unit>
-  inline Unit ActiveTail<Unit>::getCoord() const {
+  inline Unit ActiveTail<Unit>::getCoord() const { 
     return getTail()->getEndCoord(); }
-
+ 
   template <typename Unit>
-  inline Unit ActiveTail<Unit>::getCoordinate() const {
-    return getCoord(); }
+  inline Unit ActiveTail<Unit>::getCoordinate() const { 
+    return getCoord(); } 
 
   template <typename Unit>
-  inline orientation_2d ActiveTail<Unit>::getOrient() const {
+  inline orientation_2d ActiveTail<Unit>::getOrient() const { 
     return getTail()->tailOrient(); }
 
   template <typename Unit>
-  inline void ActiveTail<Unit>::pushCoordinate(Unit coord) {
+  inline void ActiveTail<Unit>::pushCoordinate(Unit coord) { 
     //appropriately handle any co-linear polyline segments by calling push point internally
     point_data<Unit> p;
     p.set(HORIZONTAL, coord);
     p.set(VERTICAL, coord);
     //if we are vertical assign the last coordinate (an X) to p.x, else to p.y
     p.set(getOrient().get_perpendicular(), getCoordinate());
+    int oldSegments = tailp_->numSegments();
     tailp_->pushPoint(p);
+    int delta = tailp_->numSegments() - oldSegments;
+    addPolyLineSize(delta);
+    otherTailp_->addPolyLineSize(delta);
   }
 
 
@@ -1241,16 +1359,16 @@
     if((getOrient() == HORIZONTAL) ^ !isHole) {
       //our first coordinate is a y value, so we need to rotate it to the end
       typename std::vector<Unit>::iterator tmpItr = outVec.begin();
-      tmpItr += size;
+      tmpItr += size; 
       outVec.erase(++tmpItr); //erase the 2nd element
     }
     End startEnd = tailp_->endConnectivity(HEAD);
     if(isHole) startEnd = otherTailp_->tailp_->endConnectivity(HEAD);
     while(nextPolyLinep) {
       bool nextStartEnd = nextPolyLinep->endConnectivity(!startEnd);
-      nextPolyLinep = nextPolyLinep->writeOut(outVec, startEnd);
+      nextPolyLinep = nextPolyLinep->writeOut(outVec, startEnd); 
       startEnd = nextStartEnd;
-    }
+    }      
     if((getOrient() == HORIZONTAL) ^ !isHole) {
       //we want to push the y value onto the end since we ought to have ended with an x
       outVec.push_back(firsty); //should never be executed because we want first value to be an x
@@ -1284,7 +1402,7 @@
 
   //solid indicates if it was joined by a solit or a space
   template <typename Unit>
-  inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid, std::vector<Unit>& outBufferTmp)
+  inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid, std::vector<Unit>& outBufferTmp) 
   {
     //checks to see if we closed a figure
     if(at1->isOtherTail(*at2)){
@@ -1324,6 +1442,11 @@
     at1->getTail()->joinTailToTail(*(at2->getTail()));
     *(at1->getOtherActiveTail()) = ActiveTail(at1->getOtherTail(), at2->getOtherActiveTail());
     *(at2->getOtherActiveTail()) = ActiveTail(at2->getOtherTail(), at1->getOtherActiveTail());
+
+    int accumulate = at2->getPolyLineSize() + at1->getPolyLineSize();
+    (at1->getOtherActiveTail())->setPolyLineSize(accumulate);
+    (at2->getOtherActiveTail())->setPolyLineSize(accumulate);
+
     at1->getOtherActiveTail()->copyHoles(*at1);
     at1->getOtherActiveTail()->copyHoles(*at2);
     destroyActiveTail(at1);
@@ -1334,7 +1457,7 @@
   //solid indicates if it was joined by a solit or a space
   template <typename Unit>
   template <typename PolygonT>
-  inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid,
+  inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid, 
                                                         std::vector<PolygonT>& outBufferTmp) {
     //checks to see if we closed a figure
     if(at1->isOtherTail(*at2)){
@@ -1348,7 +1471,7 @@
         //because otherwise it would have to have another vertex to the right of this one
         //and would not be closed at this point
         return at1;
-      } else {
+      } else {    
         //assert pG != 0
         //the figure that was closed is a shell
         outBufferTmp.push_back(at1);
@@ -1360,6 +1483,11 @@
     at1->getTail()->joinTailToTail(*(at2->getTail()));
     *(at1->getOtherActiveTail()) = ActiveTail<Unit>(at1->getOtherTail(), at2->getOtherActiveTail());
     *(at2->getOtherActiveTail()) = ActiveTail<Unit>(at2->getOtherTail(), at1->getOtherActiveTail());
+
+    int accumulate = at2->getPolyLineSize() + at1->getPolyLineSize();
+    (at1->getOtherActiveTail())->setPolyLineSize(accumulate);
+    (at2->getOtherActiveTail())->setPolyLineSize(accumulate);
+
     at1->getOtherActiveTail()->copyHoles(*at1);
     at1->getOtherActiveTail()->copyHoles(*at2);
     destroyActiveTail(at1);
@@ -1367,8 +1495,8 @@
     return 0;
   }
 
-  template <class TKey, class T> inline typename std::map<TKey, T>::iterator findAtNext(std::map<TKey, T>& theMap,
-                                                                                        typename std::map<TKey, T>::iterator pos, const TKey& key)
+  template <class TKey, class T> inline typename std::map<TKey, T>::iterator findAtNext(std::map<TKey, T>& theMap, 
+                                                                                        typename std::map<TKey, T>::iterator pos, const TKey& key) 
   {
     if(pos == theMap.end()) return theMap.find(key);
     //if they match the mapItr is pointing to the correct position
@@ -1377,22 +1505,22 @@
     }
     if(pos->first > key) {
       return theMap.end();
-    }
+    } 
     //else they are equal and no need to do anything to the iterator
     return pos;
   }
 
   // createActiveTailsAsPair is called in these two end cases of geometry
   // 1. lower left concave corner
+  //         ###| 
   //         ###|
-  //         ###|
-  //         ###|###
+  //         ###|### 
   //         ###|###
   // 2. lower left convex corner
-  //            |###
-  //            |###
-  //            |
-  //            |
+  //            |###          
+  //            |###         
+  //            |            
+  //            |     
   // In case 1 there may be a hole propigated up from the bottom.  If the fracture option is enabled
   // the two active tails that form the filament fracture line edges can become the new active tail pair
   // by pushing x and y onto them.  Otherwise the hole simply needs to be associated to one of the new active tails
@@ -1408,7 +1536,11 @@
       (*at2) = ActiveTail<Unit>(HORIZONTAL, y, !solid, at1);
       //provide a function through activeTail class to provide this
       at1->getTail()->joinHeadToHead(*(at2->getTail()));
-      if(phole)
+
+      at1->addPolyLineSize(1);
+      at2->addPolyLineSize(1);
+
+      if(phole) 
         at1->addHole(phole, fractureHoles); //assert fractureHoles == false
       return std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*>(at1, at2);
     }
@@ -1425,118 +1557,485 @@
     at1->pushCoordinate(x);
     //assert at2 is vertical
     at2->pushCoordinate(y);
+
     return std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*>(at1, at2);
   }
 
+  /* 
+   *     |
+   *     |
+   *     =
+   *     |########
+   *     |########  (add a new ActiveTail in the tailMap_).
+   *     |########
+   *     |########
+   *     |########
+   *     =
+   *     |
+   *     |
+   *
+   * NOTE: Call this only if you are sure that the $ledege$ is not in the tailMap_
+   */
+  template<bool orientT, typename Unit, typename polygon_concept_type>
+  inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>::
+  insertNewLeftEdgeIntoTailMap(Unit currentX, Unit yBegin, Unit yEnd,
+   typename std::map<Unit, ActiveTail<Unit> *>::iterator &hint){
+     ActiveTail<Unit> *currentTail = NULL;
+     std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = 
+      createActiveTailsAsPair(currentX, yBegin, true, currentTail, 
+         fractureHoles_);
+     currentTail = tailPair.first; 
+     if(!tailMap_.empty()){
+        ++hint;
+     }
+     hint = tailMap_.insert(hint, std::make_pair(yBegin, tailPair.second));
+     currentTail->pushCoordinate(yEnd); ++hint;
+     hint = tailMap_.insert(hint, std::make_pair(yEnd, currentTail));
+  }
+
+  template<bool orientT, typename Unit, typename polygon_concept_type>
+  inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>::
+  closePartialSimplePolygon(Unit currentX, ActiveTail<Unit>*pfig,
+      ActiveTail<Unit>*ppfig){
+     pfig->pushCoordinate(currentX);
+     ActiveTail<Unit>::joinChains(pfig, ppfig, false, outputPolygons_);
+  }
+  /*
+   * If the invariant is maintained correctly then left edges can do the
+   * following.
+   *
+   *               =###
+   *            #######
+   *            #######
+   *            #######
+   *            #######
+   *               =###
+   *               |### (input left edge)
+   *               |###
+   *               =###
+   *            #######
+   *            #######
+   *               =###
+   */
+  template<bool orientT, typename Unit, typename polygon_concept_type>
+  inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>::
+  updatePartialSimplePolygonsWithLeftEdges(Unit currentX,
+   const std::vector<interval_data<Unit> > &leftEdges, size_t vertexThreshold){
+     typename std::map<Unit, ActiveTail<Unit>* >::iterator succ, succ1;
+     typename std::map<Unit, ActiveTail<Unit>* >::iterator pred, pred1, hint;
+     Unit begin, end;
+     ActiveTail<Unit> *pfig, *ppfig;
+     std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair;
+     size_t pfig_size = 0;
+
+     hint = tailMap_.begin();
+     for(size_t i=0; i < leftEdges.size(); i++){
+        begin = leftEdges[i].get(LOW); end = leftEdges[i].get(HIGH);
+        succ = findAtNext(tailMap_, hint, begin); 
+        pred = findAtNext(tailMap_, hint, end); 
+
+        if(succ != tailMap_.end() && pred != tailMap_.end()){ //CASE-1//
+           //join the corresponding active tails//
+           pfig = succ->second; ppfig = pred->second;
+           pfig_size = pfig->getPolyLineSize() + ppfig->getPolyLineSize();
+
+           if(pfig_size >= vertexThreshold){
+              size_t bsize = pfig->getPolyLineSize();
+              size_t usize = ppfig->getPolyLineSize();
+
+              if(usize+2 < vertexThreshold){
+                 //cut-off the lower piece (succ1, succ) join (succ1, pred)//
+                 succ1 = succ; --succ1;
+                 assert((succ1 != tailMap_.end()) && 
+                  ((succ->second)->getOtherActiveTail() == succ1->second));
+                 closePartialSimplePolygon(currentX, succ1->second, succ->second);
+                 tailPair = createActiveTailsAsPair<Unit>(currentX, succ1->first,
+                     true, NULL, fractureHoles_);
+
+                 //just update the succ1 with new ActiveTail<Unit>*//
+                 succ1->second = tailPair.second;
+                 ActiveTail<Unit>::joinChains(tailPair.first, pred->second, true,
+                     outputPolygons_);
+              }else if(bsize+2 < vertexThreshold){
+                 //cut-off the upper piece () join ()//
+                 pred1 = pred; ++pred1;
+                 assert(pred1 != tailMap_.end() && 
+                  ((pred1->second)->getOtherActiveTail() == pred->second));
+                 closePartialSimplePolygon(currentX, pred->second, pred1->second);
+
+                 //just update the pred1 with ActiveTail<Unit>* = pfig//
+                 pred1->second = pfig;
+                 pfig->pushCoordinate(currentX);
+                 pfig->pushCoordinate(pred1->first);
+              }else{ 
+                 //cut both and create an left edge between (pred->first, succ1)//
+                 succ1 = succ; --succ1; 
+                 pred1 = pred; ++pred1;
+                 assert(pred1 != tailMap_.end() && succ1 != tailMap_.end()); 
+                 assert((pred1->second)->getOtherActiveTail() == pred->second);
+                 assert((succ1->second)->getOtherActiveTail() == succ->second);
+
+                 closePartialSimplePolygon(currentX, succ1->second, succ->second);
+                 closePartialSimplePolygon(currentX, pred->second, pred1->second);
+
+                 tailPair = createActiveTailsAsPair<Unit>(currentX, succ1->first,
+                     true, NULL, fractureHoles_);
+                 succ1->second = tailPair.second;
+                 pred1->second = tailPair.first;
+                 (tailPair.first)->pushCoordinate(pred1->first);
+              }
+           }else{
+              //just join them with closing//
+              pfig->pushCoordinate(currentX);
+              ActiveTail<Unit>::joinChains(pfig, ppfig, true, outputPolygons_);
+           }
+           hint = pred; ++hint; 
+           tailMap_.erase(succ); tailMap_.erase(pred);
+        }else if(succ == tailMap_.end() && pred != tailMap_.end()){ //CASE-2//
+           //succ is missing in the map, first insert it into the map//
+           tailPair = createActiveTailsAsPair<Unit>(currentX, begin, true, NULL, 
+               fractureHoles_);
+           hint = pred; ++hint;
+           hint = tailMap_.insert(hint, std::make_pair(begin, tailPair.second));
+
+           pfig = pred->second;
+           pfig_size = pfig->getPolyLineSize() + 2;
+           if(pfig_size >= vertexThreshold){
+              //cut-off piece from [pred, pred1] , add [begin, pred1]//
+              pred1 = pred; ++pred1;
+              assert((pred1 != tailMap_.end()) && 
+               ((pred1->second)->getOtherActiveTail() == pred->second));
+              closePartialSimplePolygon(currentX, pred->second, pred1->second);
+
+              //update: we need left edge between (begin, pred1->first)//
+              pred1->second = tailPair.first;
+              (tailPair.first)->pushCoordinate(pred1->first);
+           }else{
+              //just join//
+              ActiveTail<Unit>::joinChains(tailPair.first, pfig, 
+                  true, outputPolygons_);
+           }
+           tailMap_.erase(pred);
+        }else if(succ != tailMap_.end() && pred == tailMap_.end()){ //CASE-3//
+            //pred is missing in the map, first insert it into the map//
+            hint = succ; ++hint;
+            hint = tailMap_.insert(hint, std::make_pair(end, (ActiveTail<Unit> *) NULL));
+            pfig = succ->second;
+            pfig_size = pfig->getPolyLineSize() + 2;
+            if(pfig_size >= vertexThreshold){
+               //this figure needs cutting here//
+               succ1 = succ; --succ1;
+               assert((succ1 != tailMap_.end()) &&
+                  (succ1->second == pfig->getOtherActiveTail()));
+               ppfig = succ1->second;
+               closePartialSimplePolygon(currentX, ppfig, pfig);
+
+               //update: we need a left edge between (succ1->first, end)//
+               tailPair = createActiveTailsAsPair<Unit>(currentX, succ1->first,
+                  true, NULL, fractureHoles_);
+               succ1->second = tailPair.second;
+               hint->second = tailPair.first;
+               (tailPair.first)->pushCoordinate(end);
+            }else{
+               //no cutting needed//
+               hint->second = pfig;
+               pfig->pushCoordinate(currentX);
+               pfig->pushCoordinate(end);
+            }
+            tailMap_.erase(succ);
+        }else{
+           //insert both pred and succ//
+           insertNewLeftEdgeIntoTailMap(currentX, begin, end, hint);
+        }
+     }
+  }
+
+  template<bool orientT, typename Unit, typename polygon_concept_type>
+  inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>::
+  updatePartialSimplePolygonsWithRightEdges(Unit currentX,
+   const std::vector<interval_data<Unit> > &rightEdges, size_t vertexThreshold) 
+   {
+    
+     typename std::map<Unit, ActiveTail<Unit>* >::iterator succ, pred, hint;
+     std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair; 
+     Unit begin, end;
+     size_t i = 0;
+     //If rightEdges is non-empty Then tailMap_ is non-empty //
+     assert(rightEdges.empty() || !tailMap_.empty() );
+
+     while( i < rightEdges.size() ){
+        //find the interval in the tailMap which contains this interval// 
+        pred = tailMap_.lower_bound(rightEdges[i].get(HIGH)); 
+        assert(pred != tailMap_.end());
+        succ = pred; --succ;
+        assert(pred != succ);
+        end =  pred->first; begin = succ->first;
+
+        //we now have a [begin, end] //
+        bool found_solid_opening = false;
+        bool erase_succ = true, erase_pred = true;
+        Unit solid_opening_begin, solid_opening_end;
+        size_t j = i+1;
+        ActiveTail<Unit> *pfig = succ->second;
+        ActiveTail<Unit> *ppfig = pred->second;
+        size_t partial_fig_size = pfig->getPolyLineSize();
+        //Invariant://
+        assert(succ->second && (pfig)->getOtherActiveTail() == ppfig);
+
+        hint = succ;
+        Unit key = rightEdges[i].get(LOW);
+        if(begin != key){
+           found_solid_opening = true;
+           solid_opening_begin = begin; solid_opening_end = key;
+        }
+
+        while(j < rightEdges.size() && rightEdges[j].get(HIGH) <= end){
+           if(rightEdges[j-1].get(HIGH) != rightEdges[j].get(LOW)){
+              if(!found_solid_opening){
+                 found_solid_opening = true;
+                 solid_opening_begin = rightEdges[j-1].get(HIGH); 
+                 solid_opening_end = rightEdges[j].get(LOW);
+              }else{
+                 ++hint;
+                 insertNewLeftEdgeIntoTailMap(currentX, 
+                     rightEdges[j-1].get(HIGH), rightEdges[j].get(LOW), hint);
+              }
+           }
+           j++;
+        }
+
+        //trailing edge//
+        if(end != rightEdges[j-1].get(HIGH)){
+           if(!found_solid_opening){
+              found_solid_opening = true;
+              solid_opening_begin = rightEdges[j-1].get(HIGH); solid_opening_end = end;
+           }else{ 
+              // a solid opening has been found already, we need to insert a new left 
+              // between [rightEdges[j-1].get(HIGH), end]  
+              Unit lbegin = rightEdges[j-1].get(HIGH);
+              tailPair = createActiveTailsAsPair<Unit>(currentX, lbegin, true, NULL,
+                  fractureHoles_);
+              hint = tailMap_.insert(pred, std::make_pair(lbegin, tailPair.second));
+              pred->second = tailPair.first;
+              (tailPair.first)->pushCoordinate(end);
+              erase_pred = false;
+           }
+        }
+
+        size_t vertex_delta = ((begin != solid_opening_begin) && 
+               (end != solid_opening_end)) ? 4 : 2;
+
+        if(!found_solid_opening){
+           //just close the figure, TODO: call closePartialPolygon//
+           pfig->pushCoordinate(currentX);
+           ActiveTail<Unit>::joinChains(pfig, ppfig, false, outputPolygons_);
+           hint = pred; ++hint;
+        }else if(partial_fig_size+vertex_delta >= vertexThreshold){
+           //close the figure and add a pseudo left-edge//
+           closePartialSimplePolygon(currentX, pfig, ppfig);
+           assert(begin != solid_opening_begin || end != solid_opening_end);
+
+           if(begin != solid_opening_begin && end != solid_opening_end){
+               insertNewLeftEdgeIntoTailMap(currentX, solid_opening_begin, 
+                     solid_opening_end, hint);
+           }else if(begin == solid_opening_begin){
+              //we just need to update the succ in the tailMap_//
+              tailPair = createActiveTailsAsPair<Unit>(currentX, solid_opening_begin,
+                  true, NULL, fractureHoles_);
+              succ->second = tailPair.second;
+              hint = succ; ++hint;
+              hint = tailMap_.insert(pred, std::make_pair(solid_opening_end, 
+                  tailPair.first));
+              (tailPair.first)->pushCoordinate(solid_opening_end);
+              erase_succ = false;
+           }else{
+              //we just need to update the pred in the tailMap_//
+              tailPair = createActiveTailsAsPair<Unit>(currentX, solid_opening_begin,
+                  true, NULL, fractureHoles_);
+              hint = tailMap_.insert(pred, std::make_pair(solid_opening_begin,
+                  tailPair.second));
+              pred->second = tailPair.first;
+              (tailPair.first)->pushCoordinate(solid_opening_end);
+              erase_pred = false;
+           }
+        }else{
+           //continue the figure (by adding at-most two new vertices)//
+           if(begin != solid_opening_begin){
+              pfig->pushCoordinate(currentX);
+              pfig->pushCoordinate(solid_opening_begin);
+              //insert solid_opening_begin//
+              hint = succ; ++hint;
+              hint = tailMap_.insert(hint, std::make_pair(solid_opening_begin, pfig));
+           }else{
+              erase_succ = false;
+           }
+
+           if(end != solid_opening_end){
+              std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = 
+               createActiveTailsAsPair<Unit>(currentX, solid_opening_end, false, 
+                     NULL, fractureHoles_);
+              hint = pred; ++hint;
+              hint = tailMap_.insert(hint, std::make_pair(solid_opening_end, 
+                  tailPair.second));
+              ActiveTail<Unit>::joinChains(tailPair.first, ppfig, false, 
+                  outputPolygons_);
+           }else{
+              erase_pred = false;
+           }
+        }
+
+        //Remove the pred and succ if necessary//
+        if(erase_succ){
+           tailMap_.erase(succ);
+        }
+        if(erase_pred){
+           tailMap_.erase(pred);
+        }
+        i = j;
+     }
+ }
+
+ // Maintains the following invariant:
+ // a. All the partial polygons formed at any state can be closed 
+ //    by a single edge.
+ template<bool orientT, typename Unit, typename polygon_concept_type>
+ inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>::
+ maintainPartialSimplePolygonInvariant(iterator& beginOutput, 
+   iterator& endOutput, Unit currentX, const std::vector<interval_data<Unit> >& l, 
+      const std::vector<interval_data<Unit> >& r, size_t vertexThreshold) {
+
+      clearOutput_();
+      if(!l.empty()){
+         updatePartialSimplePolygonsWithLeftEdges(currentX, l, vertexThreshold);
+      }
+
+      if(!r.empty()){
+         updatePartialSimplePolygonsWithRightEdges(currentX, r, vertexThreshold);
+      }
+      beginOutput = outputPolygons_.begin();
+      endOutput = outputPolygons_.end();
+
+  }
+   
   //Process edges connects vertical input edges (right or left edges of figures) to horizontal edges stored as member
   //data of the scanline object.  It also creates now horizontal edges as needed to construct figures from edge data.
   //
-  //There are only 12 geometric end cases where the scanline intersects a horizontal edge and even fewer unique
+  //There are only 12 geometric end cases where the scanline intersects a horizontal edge and even fewer unique 
   //actions to take:
   // 1. Solid on both sides of the vertical partition after the current position and space on both sides before
-  //         ###|###
-  //         ###|###
-  //            |
-  //            |
+  //         ###|###          
+  //         ###|###         
+  //            |            
+  //            |            
   //    This case does not need to be handled because there is no vertical edge at the current x coordinate.
   //
   // 2. Solid on both sides of the vertical partition before the current position and space on both sides after
-  //            |
-  //            |
-  //         ###|###
-  //         ###|###
+  //            |            
+  //            |            
+  //         ###|###          
+  //         ###|###         
   //    This case does not need to be handled because there is no vertical edge at the current x coordinate.
   //
   // 3. Solid on the left of the vertical partition after the current position and space elsewhere
-  //         ###|
-  //         ###|
-  //            |
-  //            |
+  //         ###|          
+  //         ###|         
+  //            |            
+  //            |     
   //    The horizontal edge from the left is found and turns upward because of the vertical right edge to become
   //    the currently active vertical edge.
   //
   // 4. Solid on the left of the vertical partion before the current position and space elsewhere
-  //            |
-  //            |
-  //         ###|
+  //            |            
+  //            |            
+  //         ###| 
   //         ###|
   //    The horizontal edge from the left is found and joined to the currently active vertical edge.
   //
   // 5. Solid to the right above and below and solid to the left above current position.
-  //         ###|###
-  //         ###|###
-  //            |###
-  //            |###
+  //         ###|###          
+  //         ###|###         
+  //            |###            
+  //            |###            
   //    The horizontal edge from the left is found and joined to the currently active vertical edge,
   //    potentially closing a hole.
   //
   // 6. Solid on the left of the vertical partion before the current position and solid to the right above and below
   //            |###
-  //            |###
-  //         ###|###
+  //            |###            
+  //         ###|### 
   //         ###|###
   //    The horizontal edge from the left is found and turns upward because of the vertical right edge to become
   //    the currently active vertical edge.
   //
   // 7. Solid on the right of the vertical partition after the current position and space elsewhere
-  //            |###
-  //            |###
-  //            |
-  //            |
+  //            |###          
+  //            |###         
+  //            |            
+  //            |     
   //    Create two new ActiveTails, one is added to the horizontal edges and the other becomes the vertical currentTail
   //
   // 8. Solid on the right of the vertical partion before the current position and space elsewhere
-  //            |
-  //            |
-  //            |###
+  //            |            
+  //            |            
+  //            |### 
   //            |###
   //    The currentTail vertical edge turns right and is added to the horizontal edges data
   //
   // 9. Solid to the right above and solid to the left above and below current position.
-  //         ###|###
-  //         ###|###
-  //         ###|
+  //         ###|###          
+  //         ###|###         
+  //         ###| 
   //         ###|
   //    The currentTail vertical edge turns right and is added to the horizontal edges data
   //
   // 10. Solid on the left of the vertical partion above and below the current position and solid to the right below
+  //         ###| 
   //         ###|
-  //         ###|
-  //         ###|###
+  //         ###|### 
   //         ###|###
   //    Create two new ActiveTails, one is added to the horizontal edges data and the other becomes the vertical currentTail
   //
   // 11. Solid to the right above and solid to the left below current position.
+  //            |### 
   //            |###
-  //            |###
-  //         ###|
+  //         ###| 
   //         ###|
   //    The currentTail vertical edge joins the horizontal edge from the left (may close a polygon)
   //    Create two new ActiveTails, one is added to the horizontal edges data and the other becomes the vertical currentTail
   //
   // 12. Solid on the left of the vertical partion above the current position and solid to the right below
+  //         ###| 
   //         ###|
-  //         ###|
-  //            |###
+  //            |### 
   //            |###
   //    The currentTail vertical edge turns right and is added to the horizontal edges data.
   //    The horizontal edge from the left turns upward and becomes the currentTail vertical edge
   //
   template <bool orientT, typename Unit, typename polygon_concept_type>
   inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>::
-  processEdges(iterator& beginOutput, iterator& endOutput,
-               Unit currentX, std::vector<interval_data<Unit> >& leftEdges,
-               std::vector<interval_data<Unit> >& rightEdges) {
+  processEdges(iterator& beginOutput, iterator& endOutput, 
+               Unit currentX, std::vector<interval_data<Unit> >& leftEdges, 
+               std::vector<interval_data<Unit> >& rightEdges,
+               size_t vertexThreshold) {
     clearOutput_();
-    typename std::map<Unit, ActiveTail<Unit>*>::iterator nextMapItr = tailMap_.begin();
+    typename std::map<Unit, ActiveTail<Unit>*>::iterator nextMapItr; 
     //foreach edge
     unsigned int leftIndex = 0;
     unsigned int rightIndex = 0;
     bool bottomAlreadyProcessed = false;
     ActiveTail<Unit>* currentTail = 0;
     const Unit UnitMax = (std::numeric_limits<Unit>::max)();
+
+    if(vertexThreshold < std::numeric_limits<size_t>::max()){
+      maintainPartialSimplePolygonInvariant(beginOutput, endOutput, currentX,
+         leftEdges, rightEdges, vertexThreshold);
+      return;
+    }
+
+    nextMapItr = tailMap_.begin();
     while(leftIndex < leftEdges.size() || rightIndex < rightEdges.size()) {
-      interval_data<Unit>  edges[2] = {interval_data<Unit> (UnitMax, UnitMax), interval_data<Unit> (UnitMax, UnitMax)};
+      interval_data<Unit>  edges[2] = {interval_data<Unit> (UnitMax, UnitMax), 
+         interval_data<Unit> (UnitMax, UnitMax)};
       bool haveNextEdge = true;
       if(leftIndex < leftEdges.size())
         edges[0] = leftEdges[leftIndex];
@@ -1551,7 +2050,7 @@
       interval_data<Unit> & nextEdge = edges[!trailingEdge];
       //process this edge
       if(!bottomAlreadyProcessed) {
-        //assert currentTail = 0
+        //assert currentTail = 0 
 
         //process the bottom end of this edge
         typename std::map<Unit, ActiveTail<Unit>*>::iterator thisMapItr = findAtNext(tailMap_, nextMapItr, edge.get(LOW));
@@ -1578,7 +2077,7 @@
           //we need to create one and another one to be the current vertical tail
           //if this is a trailing edge then there is space to the right of the vertical edge
           //so pass the inverse of trailingEdge to indicate solid to the right
-          std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair =
+          std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = 
             createActiveTailsAsPair(currentX, edge.get(LOW), !trailingEdge, currentTail, fractureHoles_);
           currentTail = tailPair.first;
           tailMap_.insert(nextMapItr, std::pair<Unit, ActiveTail<Unit>*>(edge.get(LOW), tailPair.second));
@@ -1606,7 +2105,7 @@
           //two new tails are created, the vertical becomes current tail, the horizontal becomes thisMapItr tail
           //pass true becuase they are created at the lower left corner of some solid
           //pass null because there is no hole pointer possible
-          std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair =
+          std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = 
             createActiveTailsAsPair<Unit>(currentX, edge.get(HIGH), true, 0, fractureHoles_);
           currentTail = tailPair.first;
           thisMapItr->second = tailPair.second;
@@ -1640,7 +2139,7 @@
           currentTail = ActiveTail<Unit>::joinChains(currentTail, tail, !trailingEdge, outputPolygons_);
           nextMapItr = thisMapItr; //set nextMapItr to the next position after this one
           ++nextMapItr;
-          if(currentTail) {
+          if(currentTail) { //figure is not closed//
             Unit nextItrY = UnitMax;
             if(nextMapItr != tailMap_.end()) {
               nextItrY = nextMapItr->first;
@@ -1662,7 +2161,7 @@
               //set current tail to null
               currentTail = 0;
             }
-          }
+          }  
           //delete thisMapItr from the map
           tailMap_.erase(thisMapItr);
         } else {
@@ -1675,7 +2174,7 @@
           //leave nextMapItr unchanged, it is still next
         }
       }
-
+ 
       //increment index
       leftIndex += !trailingEdge;
       rightIndex += trailingEdge;
@@ -1718,8 +2217,10 @@
 
   //public API to access polygon formation algorithm
   template <typename output_container, typename iterator_type, typename concept_type>
-  unsigned int get_polygons(output_container& container, iterator_type begin, iterator_type end,
-                    orientation_2d orient, bool fracture_holes, concept_type ) {
+  unsigned int get_polygons(output_container& container, 
+      iterator_type begin, iterator_type end, orientation_2d orient, 
+      bool fracture_holes, concept_type, 
+      size_t sliceThreshold = std::numeric_limits<size_t>::max() ) {
     typedef typename output_container::value_type polygon_type;
     typedef typename std::iterator_traits<iterator_type>::value_type::first_type coordinate_type;
     polygon_type poly;
@@ -1738,7 +2239,8 @@
       if(pos != prevPos) {
         if(orient == VERTICAL) {
           typename polygon_formation::ScanLineToPolygonItrs<true, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd;
-          scanlineToPolygonItrsV.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges);
+           scanlineToPolygonItrsV.processEdges(itrPoly, itrPolyEnd, prevPos, 
+               leftEdges, rightEdges, sliceThreshold);
           for( ; itrPoly != itrPolyEnd; ++ itrPoly) {
             ++countPolygons;
             assign(poly, *itrPoly);
@@ -1746,7 +2248,8 @@
           }
         } else {
           typename polygon_formation::ScanLineToPolygonItrs<false, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd;
-          scanlineToPolygonItrsH.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges);
+          scanlineToPolygonItrsH.processEdges(itrPoly, itrPolyEnd, prevPos, 
+               leftEdges, rightEdges, sliceThreshold);
           for( ; itrPoly != itrPolyEnd; ++ itrPoly) {
             ++countPolygons;
             assign(poly, *itrPoly);
@@ -1783,7 +2286,7 @@
     }
     if(orient == VERTICAL) {
       typename polygon_formation::ScanLineToPolygonItrs<true, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd;
-      scanlineToPolygonItrsV.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges);
+      scanlineToPolygonItrsV.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges, sliceThreshold);
       for( ; itrPoly != itrPolyEnd; ++ itrPoly) {
         ++countPolygons;
         assign(poly, *itrPoly);
@@ -1791,7 +2294,8 @@
       }
     } else {
       typename polygon_formation::ScanLineToPolygonItrs<false, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd;
-      scanlineToPolygonItrsH.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges);
+      scanlineToPolygonItrsH.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges,  sliceThreshold);
+
       for( ; itrPoly != itrPolyEnd; ++ itrPoly) {
         ++countPolygons;
         assign(poly, *itrPoly);

Modified: trunk/boost/polygon/polygon_90_set_data.hpp
==============================================================================
--- trunk/boost/polygon/polygon_90_set_data.hpp	Wed Jul 17 10:38:39 2013	(r85060)
+++ trunk/boost/polygon/polygon_90_set_data.hpp	2013-07-17 16:43:55 EDT (Wed, 17 Jul 2013)	(r85061)
@@ -164,6 +164,12 @@
     }
 
     template <typename output_container>
+    inline void get(output_container& output, size_t vthreshold) const {
+      get_dispatch(output, typename geometry_concept<typename output_container::value_type>::type(), vthreshold);
+    }
+
+
+    template <typename output_container>
     inline void get_polygons(output_container& output) const {
       get_dispatch(output, polygon_90_concept());
     }
@@ -829,10 +835,25 @@
     void get_dispatch(output_container& output, polygon_90_concept tag) const {
       get_fracture(output, true, tag);
     }
+
+    template <typename output_container>
+    void get_dispatch(output_container& output, polygon_90_concept tag, 
+      size_t vthreshold) const {
+      get_fracture(output, true, tag, vthreshold);
+    }
+
     template <typename output_container>
     void get_dispatch(output_container& output, polygon_90_with_holes_concept tag) const {
       get_fracture(output, false, tag);
     }
+
+    template <typename output_container>
+    void get_dispatch(output_container& output, polygon_90_with_holes_concept tag,
+      size_t vthreshold) const {
+      get_fracture(output, false, tag, vthreshold);
+    }
+
+
     template <typename output_container>
     void get_dispatch(output_container& output, polygon_45_concept tag) const {
       get_fracture(output, true, tag);
@@ -854,6 +875,13 @@
       clean();
       ::boost::polygon::get_polygons(container, data_.begin(), data_.end(), orient_, fracture_holes, tag);
     }
+
+    template <typename output_container, typename concept_type>
+    void get_fracture(output_container& container, bool fracture_holes, concept_type tag,
+      size_t vthreshold) const {
+      clean();
+      ::boost::polygon::get_polygons(container, data_.begin(), data_.end(), orient_, fracture_holes, tag, vthreshold);
+    }
   };
 
   template <typename coordinate_type>

Modified: trunk/libs/polygon/test/gtl_boost_unit_test.cpp
==============================================================================
--- trunk/libs/polygon/test/gtl_boost_unit_test.cpp	Wed Jul 17 10:38:39 2013	(r85060)
+++ trunk/libs/polygon/test/gtl_boost_unit_test.cpp	2013-07-17 16:43:55 EDT (Wed, 17 Jul 2013)	(r85061)
@@ -6,7 +6,7 @@
   http://www.boost.org/LICENSE_1_0.txt).
 */
 #include <iostream>
-//#define BOOST_POLYGON_NO_DEPS
+#define BOOST_POLYGON_NO_DEPS
 #include <boost/polygon/polygon.hpp>
 
 namespace gtl = boost::polygon;
@@ -2221,6 +2221,239 @@
   return gtl::equivalence(rect, rect2);
 }
 
+/*************New Polygon Formation Tests********************/
+/*
+ *
+ * Test Input:
+ * +--------------------+
+ * |        +-------+   |
+ * |        |       |   |
+ * |        |       |   |
+ * +-----+  |       |   |
+ *       |  |       |   |
+ *       |  |       |   |
+ * +-----+  |       |   |
+ * |        |       |   |
+ * |        |       |   |
+ * |        +-------+   |
+ * +--------+           |
+ *          |           |
+ *          |           |
+ * +--------+           |
+ * |                    |
+ * |                    |
+ * +--------+           |
+ *          |           |
+ *          |           |
+ * +--------+           |
+ * |                    |
+ * |                    |
+ * +--------------------+
+ *
+ * Test Plan: 
+ * a. call 'get(out, param)' , param >=4 
+ * b. check if each polygon in the container is <= param
+ * c. check the area of all the pieces sum up to original piece
+ */
+typedef int intDC;
+typedef boost::polygon::polygon_90_with_holes_data<intDC> GTLPolygon;
+typedef boost::polygon::polygon_90_set_data<intDC> GTLPolygonSet;
+typedef boost::polygon::polygon_90_concept GTLPolygonConcept;
+typedef boost::polygon::point_data<intDC> GTLPoint;
+inline void PrintPolygon(const GTLPolygon&);
+inline GTLPolygon CreateGTLPolygon(const int*, size_t); 
+int test_new_polygon_formation(int argc, char** argv){
+   //                                               //
+   // Sub-Test-1: do a Boolean and call the new get //
+   //                                               //
+   int coordinates[] = {0,0, 10,0, 10,10, 0,10};
+   int coordinates1[] = {9,1, 20,1, 20,10, 9,10};
+   std::vector<GTLPoint> pts;
+   size_t count = sizeof(coordinates)/(2*sizeof(intDC)); 
+   size_t count1 = sizeof(coordinates1)/(2*sizeof(intDC));
+   GTLPolygon poly, poly1;
+   GTLPolygonSet polySet;
+   
+   poly = CreateGTLPolygon(coordinates, count);
+   poly1 = CreateGTLPolygon(coordinates1, count1);
+
+   polySet.insert(poly);
+   polySet.insert(poly1);
+
+   std::vector<GTLPolygon> result;
+   polySet.get(result, 100);
+
+   if(result.size() > 1){
+      std::cerr << "FAILED: expecting only one polygon because the"
+         " threshold is 100" << std::endl;
+      return 1;
+   }
+
+   if(result[0].size() != 6){
+      std::cerr << "FAILED: expecting only 6 vertices" << std::endl;
+      return 1;
+   }
+
+   if(area(result[0]) != 190){
+      std::cerr <<"FAILED: expecting only 6 vertices" << std::endl;
+      return 1;
+   }
+
+   //expect no more than 1 polygon
+   std::cout << "Found " << result.size() << "polygons after union" 
+      << std::endl;
+   for(size_t i=0; i<result.size(); i++){
+      PrintPolygon(result[i]);
+   }
+
+   intDC shell_coords[] = {0,0, 10,0, 10,21, 0,21, 0,15, 3,15, 3,13,
+      0,13, 0,10, 5,10, 5,8, 0,8, 0,5, 5,5, 5,3, 0,3};
+   intDC hole_coords[] = {4,11, 7,11, 7,19, 4,19};
+   GTLPolygon slice_polygon, slice_hole;
+   count = sizeof(shell_coords)/(2*sizeof(intDC));
+   count1 = sizeof(hole_coords)/(2*sizeof(intDC));
+
+   slice_polygon = CreateGTLPolygon(shell_coords, count);
+   slice_hole = CreateGTLPolygon(hole_coords, count1);
+
+   result.clear();
+   polySet.clear();
+   polySet.insert(slice_polygon);
+   polySet.insert(slice_hole, true);
+
+   polySet.get(result);
+   double gold_area = 0;
+   std::cout << "Found " << result.size() << " slices" << std::endl;
+   for(size_t i=0; i<result.size(); i++){
+      PrintPolygon(result[i]);
+      gold_area += area(result[i]); 
+   }
+
+   result.clear();
+   polySet.get(result, 6);
+   double platinum_area = 0;
+   std::cout << "Found " << result.size() << " slices" << std::endl;
+   for(size_t i=0; i<result.size(); i++){
+      PrintPolygon(result[i]);
+      platinum_area += area(result[i]); 
+      if(result[i].size() > 6){
+         std::cerr << "FAILED: expecting size to be less than 6" << std::endl;
+         return 1;
+      }
+   }
+
+   std::cout << "platinum_area = " << platinum_area << " , gold_area=" 
+      << gold_area << std::endl;
+   if( platinum_area != gold_area){
+      std::cerr << "FAILED: Area mismatch" << std::endl;
+      return 1;
+   }
+   std::cout << "[SUB-TEST-1] PASSED\n";
+
+   result.clear();
+   polySet.get(result, 4);
+   platinum_area = 0;
+   std::cout << "Found " << result.size() << " slices" << std::endl;
+   for(size_t i=0; i<result.size(); i++){
+      PrintPolygon(result[i]);
+      platinum_area += area(result[i]); 
+      if(result[i].size() > 4){ 
+         std::cerr << "FAILED: expecting size to be < 4" << std::endl;
+         return 1;
+      }
+   }
+
+   std::cout << "platinum_area=" << platinum_area << ", gold_area=" 
+      << gold_area << std::endl;
+
+   if( platinum_area != gold_area){
+      std::cerr << "FAILED: Area mismatch" << std::endl;
+      return 1;
+   }
+
+   std::cout << "[SUB-TEST-1] PASSED" << std::endl;
+   return 0;
+}
+
+/* 
+ * INPUT:
+ *   +--------+
+ *   |        |
+ *   |        |
+ *   |        +---+
+ *   |            |
+ *   |        +---+
+ *   |        |
+ *   +--------+
+ *            X 
+ *            
+ * TEST PLAN: as the sweepline moves and reaches
+ * X the number of vertices in the solid jumps by 4
+ * instead of 2. So make sure we don't get a 6 vertex
+ * polygon when the threshold is 4 and 6.
+ */
+int test_new_polygon_formation_marginal_threshold(int argc, char**){
+   std::vector<GTLPoint> pts;
+   GTLPolygon polygon;
+   GTLPolygonSet pset;
+   std::vector<GTLPolygon> result;
+   intDC coords[] = {0,0, 15,0, 15,10, 10,10, 10,15, 5,15, 5,10, 0,10};
+   size_t count = sizeof(coords)/(2*sizeof(intDC));
+
+   polygon = CreateGTLPolygon(coords, count);
+   pset.insert(polygon);
+
+   for(size_t i=0; i<1; i++){
+      pset.get(result, i ? 4 : 6);
+      double gold_area = 175, plat_area = 0;
+      for(size_t i=0; i<result.size(); i++){
+         if(result[i].size() > (i ? 4 : 6) ){
+            size_t expected = i ? 4 : 6;
+            std::cerr << "FAILED: Expecting no more than " <<
+               expected << " vertices" << std::endl;
+            return 1;
+         }
+         PrintPolygon(result[i]);
+         plat_area += area(result[i]); 
+      }
+
+      if(plat_area != gold_area){
+         std::cerr << "FAILED area mismatch gold=" << gold_area <<
+            " plat=" << plat_area << std::endl;
+         return 1;
+      }
+   }
+   std::cout << "Test Passed" << std::endl;
+   return 0;
+}
+
+inline void PrintPolygon(const GTLPolygon& p){
+   //get an iterator of the point_data<int>
+   boost::polygon::point_data<int> pt;
+   boost::polygon::polygon_90_data<int>::iterator_type itr;
+
+   size_t vertex_id = 0;
+   for(itr = p.begin(); itr != p.end(); ++itr){
+      pt = *itr;
+      std::cout << "Vertex-" << ++vertex_id << "(" << pt.x() <<
+         "," << pt.y() << ")" << std::endl;
+   }
+}
+
+// size: is the number of vertices //
+inline GTLPolygon CreateGTLPolygon(const int *coords, size_t size){
+   GTLPolygon r;
+   std::vector<GTLPoint> pts;
+
+   for(size_t i=0; i<size; i++){
+      pts.push_back( GTLPoint(coords[2*i], coords[2*i+1]) );
+   }
+   boost::polygon::set_points(r, pts.begin(), pts.end());
+   return r;
+}
+
+/************************************************************/
+
 int main() {
   test_view_as();
   //this test fails and I'd like to get it to pass
@@ -3615,6 +3848,19 @@
     assert_s(segs.size() == 4, "intersection3");
   }
 
+
+  /*New polygon_formation tests*/ 
+  if(test_new_polygon_formation(0,NULL)){
+     std::cerr << "[test_new_polygon_formation] failed" << std::endl;
+     return 1;
+  }
+
+  if(test_new_polygon_formation_marginal_threshold(0,NULL)){
+     std::cerr << "[test_new_polygon_formation_marginal_threshold] failed" 
+         << std::endl;
+     return 1;
+  }
+
   std::cout << "ALL TESTS COMPLETE\n";
   return 0;
 }