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

Question

我需要为一个简单的凸多边形生成一组顶点，用动态规划对该多边形进行最小权三角测量，我考虑取一个半径为r的圆，然后取20个顶点逆时针，然后形成一个20个顶点凸多边形，但我如何做到这一点？

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

还有比这种方法更容易生成凸多边形顶点的方法吗？

任何帮助都非常感谢

Answer 1

顺便说一下。+1代表那个圆圈的好方法.

1. 不关心顶点的数量 {双x0=50.0，y0=50.0，r=50.0；//圈旁双a，da，x，y；/ / view / my视图引擎可以跳过这个glview2D::_lin l；view.pic_clear()；l.col=0x00FFFFFF；/view for (a=0.0;a<2.0*M_PI;) /全圆{ x=x0+(r*cos(a))；y=y0+(r*sin(a))；A+=(20.0+(40.0*随机()*M_PI/180.0；//随机角度步长< 20,60 >度//这里添加x，y点到多边形//视图// my视图引擎可以跳过这个l.p0=l.p1；//只是添加行(欲望x，y和实际x，y) l.p1.p=x；l.p1.p1=y；view.lin.add(l)；/view } // view // view.lin.add可以跳过这个view.lin.p0=l.p1；//只连接第一行( point0，point0) // view }中的第一点和最后一点。
2. 如果已知顶点数= N，则为 将随机步长设置为平均比2PI / N小一点，例如： Da=a0+(A1*随机())；

- `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`

内部添加中断，如果顶点计数达到N。如果在for之后顶点计数不是N，那么从一开始就重新计算所有，因为对于随机数，您不能接受总是这样命中N顶点！

1. 示例从上的源代码输出

​

​

PS.

如果圆形状不够好，也可以使用省略号。

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

• rx != ry

Answer 2

在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 3

下面是一种灵活有效的凸多边形生成方法：-

1. 在圆心点(xc，yc)上生成随机点
2. 按连续点的顺序调整任意点(十一，一)
3. 检查是否(x(i-1)，y(i-1))，(xi，yi)，(x(i+1)，y(i+1))形成左转，否则拒绝调整。

如果按逆时针方向排列点，则在(x2,y2)点左转:-

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

if(crosspro>0) return(left_turn);

else return(right_turn);