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

Question

I need to draw a polygon in C ++. I set random dots in a vector and then connect them line by line. But sometimes these lines intersect, and I get something like this.

Is there any formula or something like that so the lines don't intersect?

Here is the piece of 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); } 

Answer 1

It looks like you're probably looking for it is “Simple” (as opposed to “Complex”). Polygon:

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

Not necessarily a unique solution for this:

List of polygon sorting points

This is why arranging points or path segments usually matters in polygon drawing mechanisms. If you are so inclined - however, you can find at least one non-complex polygon for many 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 indicated that your code repeats as written. You also do not define k in the excerpt that you shared, and it is better to use the multiple term for the vector of objects (“vertices”), rather than one that assumes that it is unique (“vertex”). Here is one fairly easy-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 many ways to manage iterations in C ++, although many of them are more detailed than their counterparts in other languages. A beautiful loop based on the for range has recently been added in C ++ 11, but your build environment may not yet support it.

Answer 2

It looks like you want a convex hull .

As for computing them, you have a few options .

I got lucky with the monotone chain algorithm .

Answer 3

sort an array before drawing it

Find the leftmost point than go ccw from there

those. left, where point y <first point y until it is found

rightmost point until found