如何在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);
}

- Eldarion

---

你可能想学习关于循环（loops）的知识... - Kerrek SB

一组点可以形成多个多边形。你具体想要什么？ - Pubby

Answer 1

听起来你想要一个凸包。

至于计算它们，你有几个选择。

我用单调链算法运气很好。

- genpfault

---

这将确保没有交叉的线，但会防止例如星形。 - Oliver Charlesworth

Answer 2

听起来你可能正在寻找的是“简单”（而不是“复杂”）多边形：

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

这并不一定有唯一的解决方案： 将点列表排序为多边形 这就是为什么在多边形绘图引擎中，点或路径段的顺序通常很重要。然而，如果你愿意，你可以找到至少一个非复杂多边形来表示一组点：

http://www.computational-geometry.org/mailing-lists/compgeom-announce/2003-March/000727.html

http://www.computational-geometry.org/mailing-lists/compgeom-announce/2003-March/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中添加了一个好用的基于范围的for循环，但你的构建环境可能还不支持它。

- HostileFork says dont trust SE

Answer 3

在绘制数组之前对其进行排序

找到最左边的点，然后从那里逆时针旋转

即 最左边的点y <第一个点y，直到找不到为止

找到最右边的点，直到找不到为止

- Joe McGrath

---

这里的起点可以描述为连接最左和最右点的线的中点。 - Joe McGrath