Как нарисовать полигон в C ++ таким образом, чтобы линии не пересекались?

Question

Мне нужно нарисовать многоугольник в C ++. Я устанавливаю случайные точки в векторе, а затем соединяю их через линии. Но иногда эти линии пересекаются, и я получаю что-то вроде этого.

Есть ли какая-нибудь формула или что-то подобное, чтобы линии не пересекались?

Вот часть кода:

void draw_picture(Canvas & canvas) {
  PairXY a,b,c,d,e;
  int k;
  vector <PairXY> vertex;
  vertex.push_back(PairXY(drandom(k),drandom(k)));
  vertex.push_back(PairXY(drandom(k),drandom(k)));
  vertex.push_back(PairXY(drandom(k),drandom(k)));
  vertex.push_back(PairXY(drandom(k),drandom(k)));
  vertex.push_back(PairXY(drandom(k),drandom(k)));

  vector <PairXY>::const_iterator iter;

  iter = vertex.begin();
  a=*iter;
  iter = vertex.begin()+1;
  b=*iter;
  iter = vertex.begin()+2;
  c=*iter;
  iter = vertex.begin()+3;
  d=*iter;
  iter = vertex.begin()+4;
  e=*iter;

  Line l1(a,b);
  draw_line(l1,canvas);
  Line l2(b,c);
  draw_line(l2,canvas);
  Line l3(c,d);
  draw_line(l3,canvas);
  Line l4(d,e);
  draw_line(l4,canvas);
  Line l5(e,a);
  draw_line(l5,canvas);
}

Answer 1

Звучит так, будто вы хотите выпуклую оболочку .

Что касается их вычисления, у вас есть несколько вариантов .

* 1008повезло с алгоритмом монотонной цепочки .

Answer 2

Звучит так, как будто вы, вероятно, ищете «Простой» (в отличие от «Сложного») полигон:

http://en.wikipedia.org/wiki/Simple_polygon

Не обязательно есть уникальное решение для этого:

Сортировка списка точек в многоугольник

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

http://www.computational -geometry.org / списки рассылки / compgeom-анонс / 2003-март / 000727.html

http://www.computational -geometry.org / списки рассылки / compgeom-анонс / 2003-март / 000732.html

---

Другие отметили, что ваш код повторяется, как написано. Вы также не определяете k в отрывке, которым вы поделились, и лучше использовать термин множественного числа для вектора объектов («вершин»), а не один, предполагающий, что он является единственным («вершина»). Вот один довольно простой для понимания набор изменений, который следует обобщить на любое количество вершин:

void draw_picture(Canvas & canvas, int k, int numVertices = 5) {
  vector<PairXY> vertices;
  for (int index = 0; index < numVertices; index++) { 
      vertices.push_back(PairXY(drandom(k),drandom(k)));
  }

  vector<PairXY>::const_iterator iter = vertices.begin();
  while (iter != vertices.end()) {
     PairXY startPoint = *iter;
     iter++;
     if (iter == vertices.end()) {
         Line edgeLine (startPoint, vertices[0]);
         draw_line(edgeLine, canvas);
     } else {
         Line edgeLine (startPoint, *iter);
         draw_line(edgeLine, canvas);
     }
   }
}

Существует множество способов управления итерациями в C ++, хотя многие из них более многословны, чем их аналоги в других языках. Недавно в C ++ 11 был добавлен loop с диапазоном *1031*, но ваша среда сборки может его еще не поддерживать.

Answer 3

отсортировать массив перед его рисованием

Найти самую левую точку, чем идти против часовой стрелки оттуда

то есть крайнюю левую точку, где точка y <первая точка y, пока ничего не найдено </p>

крайняя справапока ничего не найдено