如何在c ++中生成随机顶点以形成凸多边形？

Question

我需要为一个简单的凸多边形生成一组顶点,以便使用动态编程对该多边形进行最小权重三角化,我考虑采用半径为r的圆,然后采用20个顶点逆时针方向移动,然后我将形成一个20顶点凸多边形,但我怎么能这样做

我怎么知道位于半径为r的圆上的顶点？

并且还有另一种更简单的方法来生成除此之外的凸多边形的顶点

任何帮助非常感谢

Answer 1

生成0到2*pi之间的20个随机数,并对它们进行排序.

现在使用一点基本三角函数转换为X,Y坐标.

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

Answer 2

顺便说一句.+1用于该圈子的好方法......

1. 不关心顶点的数量

   {
   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. 如果已知顶点数= N

   设置随机步骤平均少一点2PI / N,例如:

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

   • a0=0.75*(2*M_PI/N) ...最小的da
   • a1=0.40*(2*M_PI/N)...... a0+(0.5*a1)是avg = 0.95......不到了2PI/N

   如果顶点数达到,则添加中断N.如果在for顶点计数之后没有N那么从头开始重新计算,因为随机数你不能认为你总是以N这种方式点击顶点!

3. 上面源代码的示例输出

PS.

如果圆形形状不够好,也可以使用椭圆

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

• rx != ry