如何生成随机凸多边形？

Question

我试图设计一种方法来生成随机2D凸多边形。它必须具有以下属性：

• 坐标应该是整数;
• 多边形应该位于具有角（0,0）和（C，C）的正方形内，其中C是给定的;
• 多边形应该具有接近于给定数目N.

例如顶点的数目，产生具有10个顶点并位于正方形[0..100]×内随机多边形[0..100] 。

是什么让这项任务变得困难，是坐标应该是整数。

我尝试的方法是在给定的正方形中生成随机点集并计算这些点的凸包。但由此产生的凸包与N相比是非常小的顶点。

任何想法？

Answer 1

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

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

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

获得顶点后，找到具有来自原点的最大量级的顶点。将每个顶点除以该量值以对多边形进行归一化，然后按（C/2）进行缩放。转换为（C/2，C/2）并转换回整数。

Answer 2

一个简单的算法是：

1. 开始随机线（两个顶点和两个边多边形）
2. 以多边形
3. 就这个边缘新的随机点P的随机边E
4. 取垂直于E的直线L通过点P.通过计算直线T与由与E相邻的两条边所定义的直线之间的交点，计算当凸面没有断裂时P的最大偏移量。
5. 在该范围内随机偏移点P.
6. 如果不够分，重复从2

Answer 3

您最初的做法是正确的 - 计算的凸包是你能满足随机性，凸性和integerness的唯一途径。

我认为优化算法以获得“更多点”的唯一方法是将它们围绕一个圆圈而不是完全随机地进行组织。你的积分应该更接近你的正方形的“边缘”而不是靠近中心。在中心，概率应该是〜0，因为多边形必须是凸的。

一个简单的选项是设置出现点的最小半径 - 可能是C/2或C * 0.75。计算C平方的中心，如果一个点太靠近，将它从中心移开，直到达到最小距离。

Answer 4

这是我知道的最快的算法，它以相等的概率生成每个凸多边形。输出具有N个顶点，运行时间为O（N log N），所以它可以非常快地生成更大的多边形。

• 生成两个列表，X和Y，N随机整数介于0和C.确保有没有重复。
• 排序X和Y并存储它们的最大和最小元素。
• 将其他（不是最大或最小）元素随机分为两组：X1和X2，以及Y1和Y2。
• 在这些列表的开始和结尾处重新插入最小和最大元素（minX，开头为X1和X2,maxX，最后等）。
• 找到连续差异（X1[i + 1] - X1[i]），颠倒第二组订单（X2[i] - X2[i + 1]）。将它们存储在列表XVec和YVec中。
• 随机化（洗牌）YVec并将每一对XVec[i]和YVec[i]视为一个2D矢量。
• 将这些向量按角度排序，然后将它们端到端地放置以形成多边形。
• 将多边形移动到原始的最小和最大坐标。

动画和Java实现在这里可用：Generating Random Convex Polygons。

该算法基于Pavel Valtr的论文：“Probability that n random points are in convex position”。离散&计算几何13.1（1995）：637-643。