How to draw a polygon in C++ such that the lines do not intersect?

Question

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

There can be multiple polygons formed from a set of points. What exactly do you want? — Pubby, Nov 23 '11 at 00:10

genpfault · Answer 1 · 2011-11-23T00:16:57.683

4

Sounds like you want a convex hull.

As far as calculating them goes, you have several options.

I've had good luck with the monotone chain algorithm.

edited Nov 23 '11 at 00:16

answered Nov 23 '11 at 00:08

genpfault

51,148
11
85
139

3

That would guarantee no crossing lines, but it would prevent e.g. star shapes. – Oliver Charlesworth Nov 23 '11 at 00:09

score 2 · Accepted Answer · edited May 23 '17 at 12:30

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.

score 0 · Answer 3 · answered Nov 23 '11 at 01:35

0

sort the array before drawing it

Find the left most point than go CCW from there

ie leftmost where point y < first point y until none found

rightmost point until none found

answered Nov 23 '11 at 01:35

Joe McGrath

1,481
10
26

the origin here could be described as the point at the middle of the line that connects the leftmost and rightmost point, – Joe McGrath Nov 23 '11 at 18:38

How to draw a polygon in C++ such that the lines do not intersect?

3 Answers3