How to generate random vertices to form a convex polygon in c++?

Question

I need to generate a set of vertices for a simple convex polygon to do a minimum weight triangluation for that polygon using dynamic programming , I thought about taking a circle of radius r and then take 20 vertices moving counter clock wise and then i will form a 20 vertex convex polygon but i how can i do that

How would i know the vertex that lies on a circle of radius r ?

and is there another easier way of generating vertices for convex polygon other than that way

Any help greatly appreciated

Answer 1

btw. +1 for nice approach with that circle ...

1. do not care for number of vertexes

   {
   double x0=50.0,y0=50.0,r=50.0;  // circle params
   double a,da,x,y;
   // [view]                       // my view engine stuff can skip this
   glview2D::_lin l;
   view.pic_clear();
   l.col=0x00FFFFFF;
   // [/view]
   for (a=0.0;a<2.0*M_PI;)         // full circle
       {
       x=x0+(r*cos(a));
       y=y0+(r*sin(a));
       a+=(20.0+(40.0*Random()))*M_PI/180.0;              // random angle step < 20,60 > degrees
   
       // here add your x,y point to polygon
   
       // [view]                   // my view engine stuff can skip this
       l.p0=l.p1;                  // just add line (lust x,y and actual x,y)
       l.p1.p[0]=x;
       l.p1.p[1]=y;
       view.lin.add(l);
       // [/view]
       }
   // [view]                   // my view engine stuff can skip this
   view.lin[0].p0=l.p1;        // just join first and last point in first line (was point0,point0)
   // [view]
   }
   

2. if number of vertexes is known = N

   Set random step to be on average little less then 2PI / N for example:

   da=a0+(a1*Random());
   

   • a0=0.75*(2*M_PI/N) ... minimal da
   • a1=0.40*(2*M_PI/N) ... a0+(0.5*a1) is avg = 0.95 ... is less then 2PI/N

   inside for add break if vertex count reach N. If after for the vertex count is not N then recompute all from beginning because with random numbers you cannot take it that you always hit N vertexes this way !!!

3. sample output from source code above

PS.

You can also use ellipse if the circle shape is not good enough

x=x0+(rx*cos(a));
y=y0+(ry*sin(a));

• rx != ry

Answer 2

Generate your 20 random numbers between 0 and 2*pi, and sort them.

Now use a little basic trigonometry to convert to X,Y coordinates.

for (int i = 0; i < 20; i++)
{
    x = x0 + r*cos(angle[i]);
    y = y0 + r*sin(angle[i]);
    // ...
}

Answer 3

Here is a flexible and efficient way to generate convex polygon : -

1. Generate random points on the circle at center point (xc,yc)
2. tweak any point (xi,yi) in sequence of consecutive points
3. check if (x(i-1),y(i-1)) , (xi,yi) , (x(i+1),y(i+1)) form a left turn else reject the tweak.

if points are arranged in anti clockwise manner then left turn at point (x2,y2) :-

int crosspro = (x3-x2)*(y2-y1) - (y3-y2)*(x2-x1) 

if(crosspro>0) return(left_turn);

else return(right_turn);

Answer 4

This is my version of the circle method in Javascript.

  var x = [0];
  var y = [0];
  var r = 0;
  var angle = 0
  for (var i = 1; i < 20; i++) {
    angle += 0.3 + Math.random() * 0.3
    if (angle > 2 * Math.PI) {
      break; //stop before it becomes convex
    } 
    r = (5 + Math.random() * 20+Math.random()*50)
    x.push(x[i - 1] + r * Math.cos(angle));
    y.push(y[i - 1] + r * Math.sin(angle));
  }