如何生成一个随机凸多边形？ [英] How to generate a random convex polygon?

问题描述

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

• 坐标应该是整数;


• 多边形应该位于在具有角（0,0）和（C，C）的正方形内，其中C是给定的;
  
• 多边形应该具有接近给定数N的顶点数。
>

例如，生成具有10个顶点并位于方形[0..100] x [0..100]内的随机多边形。 p>

是什么让这项任务变得困难，是坐标应该是整数。事实上，我试过的方法是在给定的正方形中生成随机点集并计算这些点的凸包。但是由此产生的凸包相对于N来说是非常小的顶点。

有什么想法？

解决方案<

如果N< p> 3.生成一个有N个顶点的单位圆，随机旋转[0..90]度。

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

在设置好顶点后，从原点找到幅度最大的顶点。将每个顶点除以该量值以对多边形进行归一化，然后按（C / 2）进行缩放。转换为（C / 2，C / 2）并转换回整数。

I'm trying to devise a method for generating random 2D convex polygons. It has to have the following properties:

• coordinates should be integers;
• the polygon should lie inside a square with corners (0, 0) and (C, C), where C is given;
• the polygon should have number of vertices close to a given number N.

For example, generate random polygons that have 10 vertices and lie inside square [0..100]x[0..100].

What makes this task hard, is the fact that the coordinates should be integers.

The approach I tried was to generate random set of points in the given square and compute the convex hull of these points. But the resultant convex hull is very little vertices compared to N.

Any ideas?

解决方案

This isn't quite complete, but it may give you some ideas.

Bail out if N < 3. Generate a unit circle with N vertices, and rotate it random [0..90] degrees.

Randomly extrude each vertex outward from the origin, and use the sign of the cross product between each pair of adjacent vertices and the origin to determine convexity. This is the step where there are tradeoffs between speed and quality.

After getting your vertices set up, find the vertex with the largest magnitude from the origin. Divide every vertex by that magnitude to normalize the polygon, and then scale it back up by (C/2). Translate to (C/2, C/2) and cast back to integer.

这篇关于如何生成一个随机凸多边形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！