Mathematica怎么生成随机凸四(多)边形？

Question

Graphics /@ Polygon /@ RandomReal[{-5, 5}, {10, 4, 2}]

这样生成的有凸的也有不凸的

Answer 1

我也贴一种方法吧，经测试发现构造出来的多边形是凸的概率几乎接近于1，但是，我不知道是否会产生非凸的多边形，测试了几十次，没有发现非凸的情况。各位有反例或者改进的话请告诉我，谢谢！

这种方法还有一个好处，就是多边形的边数是确定的，内置函数 ConvexHullMesh 得到的多边形的边数可能比点数小，在 n 比较大的时候，不容易构造出边数确定的凸多边形。

Clear[convexPolygon]; 
convexPolygon[n_] /; n > 2 := 
 Module[{a0, a, r0, r1, r2, x, y}, a0 = RandomReal[1, n]; 
  a = 2*Pi*(RandomReal[] + Accumulate[a0/Total[a0]]); 
  r0 = RandomReal[1, n]; 
  r1 = r0/Total[r0]; {x, y} = Accumulate /@ {r1*Cos[a], r1*Sin[a]}; 
  r2 = Accumulate@r1; 
  Graphics@Polygon@
    Transpose[Prepend @@@ {{x - x[[n]]*r2, 0}, {y - y[[n]]*r2, 0}}]];

以下是一些例子：

n = 4 时

n = 6 时

n = 10 时

n = 100 时

Comments

从幸福结局问题（ https://zh.wikipedia.org/wiki/%E5%B9%B8%E7%A6%8F%E7%B5%90%E5%B1%80%E5%95%8F%E9%A1%8C ）的相关结论来看，n=4的时候我那个方法还是能用的……说实话你这个方法我没怎么看懂囧，不妨解释下？

---

我来试着解释下。首先{x,y}生成螺旋折线，可知最后一段折线与原点到初始点的线段平行，且归一化保证了此螺旋恰好只绕一圈。然后将终点平移至原点，其余诸点以相同方向平移，平移量以螺旋至此的长度按比例缩减。最后我是用几何的方法证明这样平移后的各顶点将保持凸性不变（这一步想了一个小时……不过反正开会没事）。不知道对不对，在各位大神面前班门弄斧了。

Answer 2

我只能想到先生成再判断是否凸的思路。

版本10新加的那一大堆计算几何的函数应该会有帮助，不过我还在版本9，所以就用下程序包吧：

 

<< ComputationalGeometry`
Clear[convexhull]
While[Length@convexhull =!= 4, 
 data2D = RandomReal[{-5, 5}, {4, 2}]; convexhull = ConvexHull@data2D]
Graphics@GraphicsComplex[data2D, Polygon@convexhull]