如何在C++中绘制多边形使得线不相交？

发布于 2024-12-17 16:21:15 字数 1006 浏览 0 评论 0原文

我需要用 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);
}

原文

I need to draw a polygon in C++. I set random points in vector and then connect them via lines. But sometimes those lines intersect and i get something like this.

enter image description here

Is there any formula or something like that, so that the lines wouldn't cross?

Here is part of the code:

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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

悲喜皆因你 2024-12-24 16:21:15

听起来你想要一个凸包。

就计算它们而言，您有几个选项。

我很幸运单调链算法。

回复收藏 0 原文

拒绝两难 2024-12-24 16:21:15

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

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++ 中有很多管理迭代的方法，尽管其中许多方法比其他语言中的对应方法更冗长。最近有一个不错的基于范围的 for C++11 中添加了循环，但您的构建环境可能尚不支持它。

It sounds like what you are probably looking for is a "Simple" (as opposed to "Complex") Polygon:

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

There's not necessarily a unique solution to that:

Sort point list into polygon

This is why the ordering of points or path segments typically matters in polygon drawing engines. If you are so inclined--however--you can find at least one non-complex polygon for a set of points:

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

Others have pointed out your code is repetitive as written. You also don't define k in the excerpt you shared, and it's better to use a plural term for a vector of objects ("vertices") rather than one suggesting it is singular ("vertex"). Here's one fairly simple-to-understand set of changes that should generalize to any number of vertices:

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

There are a lot of ways to manage iterations in C++, although many of them are more verbose than their counterparts in other languages. Recently a nice range-based for loop was added in C++11, but your build environment may not support it yet.

回复收藏 0 原文