C++:List iterators are pointing to the wrong location -

warning. huge question length.

hi. so, i'm trying write program takes sequence of n points in xy plane input (a simple polygon), along line ax + =c, , outputs list of polygons line divides original 1 into.

so define following :

      struct point     {         public:         float x, y;         list <point>::iterator it;//if point intersection point, points position in other list in class polygon point located. value not defined point in list pts (see class polygon)         bool operator <(point );         int pair;//paired intersection points have identical pairing values          int poly;//poly shows if part of polygon or not         point intersection( point, point, line);//returns point of intersection           void output();          };      class polygon     {         public:         int n;         list <point> pts;//stores points of original polygon intersection points         list <point> intr;// stores intersection points         void init_it();//initialises iterators of points present in original polygon         void init_pair();//initialises "pair" consecutive points 1,1,0,0,1,1... //this allows pairing of consecutive points line intersects convenient traversal of polygon in 1 direction         void intersects(line);//solves every relevant side of polygon line list of relevant points         void output();         polygon()         {n=0;}     };      class line     {         public:         float a,b,c;             float eval(point p);     }; 

look @ intersects() , main() functions here.

void polygon::intersects(line l) {     list <point>::iterator i=pts.begin();     list <point>::iterator j=i;      while(true)     {            j++;         if (j==pts.end())                j=pts.begin();                          if(intersect(*i,*j,l))            {             point p=intersection(*i,*j,l);             pts.insert(j,p);             intr.push_front(p);             i++;             list <point>::iterator k=intr.begin();             (*i).it=k;             (*k).it=i;             (*k).poly=(*i).poly=0;         }     i=j; }  }    

(snippet main())

while(p.n>0)//flag= new beginning, beg= current beginning     {          //initialise stuff         while(i!=beg)            {               t.pts.push_back(*i);             if( (*i).poly==1 )//point original polygon              {             //do stuff, increment             }             else if(((*i).poly)==0)             {                 //do                    list <point>:: iterator j= (*i).it;                 list <point>:: iterator k1=j,k2=j;                 if( j==p.intr.begin() )                 {                     j++;                 }                 else if(j==end)                 {                     j--;                 }                 else                 {// gets infinite loop here                       k1--;                     k2++;                     if((*j).pair==(*k1).pair)                     {                          j--;                     }                     else                     {                         j++;                     }                 }                 t.pts.push_back(*j);                 i=(*j).it;// line supposed set next iterator in "intr" list, doesnt change!               }             else             i++;         }      output.push_back(t);     } 

the problem here in main() function. when write i=(*j).it, not return value want to. iterator seems pointing same point, leading infinite loop. can't find problem it.

here's sample test case answer:

test case:

12 0 0 0 5 5 5 5 2 2 2 2 3 4 3 4 4 1 4 1 1 5 1 5 0 1 0 3 

answer expected:

4 8 0 0 0 5 3 5 3 4 1 4 1 1 3 1 3 0 4 2 2 2 3 3 3 3 2 4 3 0 3 1 5 1 5 0 8 3 2 3 3 4 3 4 4 3 4 3 5 5 5 5 2 

note: algorithm used here seems work (checked other people who'd used similar one), seem have made mistake in implementing it.

your question has lot of code review. but, on other hand, know geometric problem perfectly. i'm going provide solution:

first, classes hold lines , points (simplified):

struct point_2d {     float x , y;      point_2d( float _x = 0.0f , float _y = 0.0f) : x( _x ) , y( _y ) {} };   struct line {     float a,b,c,d; //ax + + c = 0      float relative_position(const point_2d& point) { return a*point.x + b*point.y + c; } };   using polygon = std::vector<point_2d>; 

here solution based on stl algorithms (i prefer this):

std::pair<polygon,polygon> divide_polygon(const polygon& poly , const line& ln) {     polygon up_poly;     polygon down_poly;      std::partition_copy( std::begin( poly ) , std::end( poly ) , std::back_inserter( up_poly ) , std::back_inserter( down_poly ) , [](const point_2d& point) { return ln.relative_position( point ) >= 0; });      return std::make_pair( up_poly , down_poly ); } 

note closed answer 2 first lines of question (the abstract description of problem). code works perfectly, , takes advantage of stl (algorithms, containers, etc). i'm not giving exact answer problem. i'm not going provide solution online judge problem. thats homework.