C++ Convex hull using Graham scan algorithm

Question

So i need to make a Convex hull using Graham scan algorithm, but i have problem, i get this kinda convex:

void draw_line(Line l, Canvas& canvas) {
  canvas.draw_line(l.a, l.b);
}


double drandom(){
  return rand() * 1. / RAND_MAX;
}

bool is_convex(const vector<PairXY> vertex){}

void draw_picture(Canvas & canvas) {
  vector <PairXY> vertex;
  vector <PairXY>:: const_iterator iter = vertex.begin();
  srand((unsigned)time(0));

Here i add random points of convex

  for (int i=5;i!=0;i--) {
  vertex.push_back(PairXY(drandom()*640,drandom()*480));
  }

Here i find the first and lowest point from which to start.

  for (int i=0;i!=5;i++) {
    if (vertex[i].y > vertex[i+1].y)
       vertex.push_back(vertex[i]);
  }

Here i sort all the remaining points.

  for (int m=1;m!=4;m++){
    for (int i=m;i!=5;i++) {
      if (vertex[i].x > vertex[i+1].x)
         vertex.push_back(vertex[i]);
    }
  }

  vector<PairXY>::const_iterator i=vertex.begin(), j=i;

Here i draw the convex.

  for(;++i != vertex.end(); j++)
      draw_line(Line(*j, *i), canvas);
      if (j != vertex.end())
        draw_line(Line(*j, *vertex.begin()), canvas);

}

Could somebody tell me what i am doing wrong?

Answer 1

Did you check your understanding of what push_back() does?

It seems like you think that vertex.push_back(vertex[i]) would move element i to the end. It doesn't. It pushes a copy of the element onto vertex.

That's your first problem in finding the lowest y. Your x test is not going to work either.

Maybe you could have two vectors - the original, unmodified, and a working vector that you place points into after testing them.

I also don't see where you implement the Graham scan sort by angle... you skipped that here right?

Style issue: you should also rewrite loop limits in terms of vector.size() or use iterators.