1

だから私はグラハム スキャン アルゴリズムを使用して凸包を作成する必要がありますが、問題があります。

ここに画像の説明を入力

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

}

誰かが私が間違っていることを教えてもらえますか?

4

1 に答える 1

0

push_back() が何をするかについての理解を確認しましたか?

vertex.push_back(vertex[i]) が要素 i を最後に移動すると思うようです。そうではありません。要素のコピーを頂点にプッシュします。

これが、最小の y を見つける最初の問題です。x テストも機能しません。

おそらく、元の変更されていないベクトルと、テスト後にポイントを配置する作業ベクトルの 2 つのベクトルを使用できます。

また、グラハムスキャンの角度による並べ替えを実装している場所もわかりません...ここではそれをスキップしましたよね?

スタイルの問題: vector.size() に関してループ制限を書き直すか、反復子を使用する必要があります。

于 2011-12-30T22:41:03.983 に答える