如何生成随机凸多边形？

Question

我正在尝试设计一种生成随机2D凸多边形的方法.它必须具有以下属性:

例如,生成具有10个顶点并位于square [0..100] x [0..100]内的随机多边形.

使这项任务变得困难的原因是坐标应该是整数.

我尝试的方法是在给定的方格中生成随机的点集并计算这些点的凸包.但是与N相比,合成的凸包是非常小的顶点.

有任何想法吗？

Answer 1

这是我知道的最快的算法，它以相等的概率生成每个凸多边形。输出正好有 N 个顶点，运行时间为 O(N log N)，因此它可以非常快速地生成甚至大的多边形。

生成两个列表，X并且Y，0和C之间做出N个随机整数确认没有重复。
排序X并Y存储它们的最大和最小元素。
将其他（不是最大或最小）元素随机分为两组：X1and X2、 andY1和Y2。
重新插入在这些列表的开始和结束的最小和最大的元素（minX在开始X1和X2，maxX在端部等）。
找出连续的差异 ( X1[i + 1] - X1[i])，反转第二组 ( X2[i] - X2[i + 1])的顺序。将这些存储在列表XVec和YVec.
随机化（洗牌）YVec并将每一对XVec[i]和YVec[i]作为一个二维向量。
按角度对这些向量进行排序，然后将它们首尾相连以形成多边形。
将多边形移动到原始的最小和最大坐标。

此处提供动画和 Java 实现：生成随机凸多边形。

该算法基于 Pavel Valtr 的一篇论文：“ n 个随机点处于凸位置的概率”。离散与计算几何 13.1 (1995)：637-643。

Answer 2

这并不完全完整，但它可能会给您一些想法。

如果 N < 3，则退出。生成一个具有 N 个顶点的单位圆，并将其随机旋转 [0..90] 度。

从原点向外随机挤出每个顶点，并使用每对相邻顶点与原点之间的叉积的符号来确定凸性。这是速度和质量之间需要权衡的步骤。

设置顶点后，找到距离原点最大量值的顶点。将每个顶点除以该大小以标准化多边形，然后将其按 (C/2) 缩放。转换为 (C/2, C/2) 并转换回整数。