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

Question

我需要为一个简单的凸多边形生成一组顶点，以便使用动态规划来进行最小权值三角剖分。我考虑取一个半径为r的圆，然后以逆时针方向移动20个顶点，那么我就可以形成一个20个顶点的凸多边形，但我应该如何做呢？

如何确定位于半径为r的圆上的顶点？

除此之外，还有其他更容易生成凸多边形顶点的方法吗？

非常感谢任何帮助。

- user3196567

---

可能是如何生成随机凸多边形？的重复问题。 - Mangara

Answer 1

生成20个0到2*pi之间的随机数，并将它们排序。

现在使用一些基本的三角函数，将它们转换成X,Y坐标。

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

- Mark Ransom

---

但是我应该如何对它们进行排序呢？根据什么标准我需要进行排序？ - user3196567

@user3196567，它们只是数字。按升序排列它们，或者如果您更喜欢按降序排列也可以 - 这无关紧要。 - Mark Ransom

Answer 2

顺便说一下，对于那个圆形的不错方法，我点赞。

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

附注：

如果圆形不够好，您也可以使用椭圆形

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

• rx != ry

- Spektre

Answer 3

这是一种灵活高效的生成凸多边形的方法：-

1. 在圆心点(xc,yc)上随机生成点。
2. 调整连续点序列中的任何一个点(xi,yi)。
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);

- Vikram Bhat

Answer 4

这是我在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));
  }

- lilgreenland