C ++ Выпуклая оболочка с использованием алгоритма сканирования Грэма - PullRequest
Новая
       15

C ++ Выпуклая оболочка с использованием алгоритма сканирования Грэма

1 голос
/ 07 декабря 2011

Так что мне нужно сделать выпуклую оболочку, используя алгоритм сканирования Грэма, но у меня есть проблема, я получаю своего рода выпуклость:

enter image description here

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));

Здесь я добавляю случайные точкииз выпуклых 

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

Здесь я нахожу первую и самую нижнюю точки, с которых нужно начинать. 

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

Здесь я сортирую все оставшиеся точки. 

  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;

Здесь я рисую выпуклый.

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

}

Может ли кто-нибудь сказать мне, что я делаю неправильно?

1 Ответ

0 голосов
/ 31 декабря 2011

Вы проверили свое понимание того, что делает push_back ()?

Кажется, вы думаете, что vertex.push_back (vertex [i]) переместит элемент i в конец.Это не так.Он помещает копию элемента в вершину.

Это ваша первая проблема в поиске самого низкого значения y.Ваш x-тест тоже не сработает.

Возможно, у вас может быть два вектора - исходный, неизмененный и рабочий вектор, в который вы помещаете точки после их тестирования.

Я также не вижу, где вы осуществляете сортировку по Грэму по углам ... Вы пропустили это здесь, верно?

Проблема стиля: вам также следует переписать пределы цикла с точки зрения вектора.size () или используйте итераторы.

...