C ++ bolle scheepsromp met Graham-scanalgoritme

Dus ik moet een convexe romp maken met behulp van Graham scan-algoritme, maar ik heb een probleem, ik krijg dit nogal convex:

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 vertex){}

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

Hier voeg ik willekeurige convexe punten toe

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

Hier vind ik het eerste en laagste punt om te beginnen.

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

Hier sorteer ik alle resterende punten.

  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::const_iterator i=vertex.begin(), j=i;

Hier teken ik de convexe.

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

}

Kan iemand me vertellen wat ik verkeerd doe?

1

1 antwoord

Heb je gekeken wat je weet wat push_back() doet?

Het lijkt alsof je denkt dat vertex.push_back (vertex [i]) element i naar het einde zou verplaatsen. Dat doet het niet. Het duwt een kopie van het element op hoekpunt.

Dat is je eerste probleem bij het vinden van de laagste y. Je x-test gaat ook niet werken.

Misschien zou je twee vectoren kunnen hebben - de originele, ongewijzigde en werkende vector waar je punten in plaatst na het testen ervan.

Ik zie ook niet waar je de Graham-scan soort voor hoek implementeert ... je hebt dat hier overgeslagen toch?

Stijlprobleem: u moet loop-limieten ook herschrijven in termen van vector.size() of iterators gebruiken.

0
toegevoegd