随机多边形生成算法 [英] Algorithm for random polygon generation

问题描述

任何人都可以为随机多边形生成建议算法或代码。条件是多边形边不相交（意味着它应该像凸多边形）。

Can any one suggest algorithm or code for random polygon generation. Condition is that polygon sides are not intersect (means it should be like a convex polygon).

推荐答案

现在，还有一个，非常明显算法。



创建 N 相同范围内的点，例如点上的平方（0,0） ）和（1,1），其中 N 是一个随机数> = 3.对于获得的点集​​，建立一个凸包 。如果您阅读此内容，可以找到一些算法： http://en.wikipedia.org/wiki/Convex_hull [ ^ ]。



显然，您需要一个中间步骤：凸包可能看起来是同一条直线上的一组点，或者太靠近某条直线。诀窍是检测这种情况（如果你的凸壳算法没有失败）并通过这个解决方案，重复尝试。

-SA

Now, one more, pretty obvious algorithm.

Create N points in same range, for example, the square on the points (0,0) and (1, 1), where N is a random number >= 3. For the obtained set of points, build a convex hull. You can find some algorithm if you read this: http://en.wikipedia.org/wiki/Convex_hull[^].

Apparently, you would need one intermediate step: a convex hull may appear to be a set of points on the same straight line, or too close to some line. The trick is to detect this situation (if your convex hull algorithm not fails) and through out this solution, repeat the attempt.

—SA

由于没有指定随机分布，我建议采用以下简单方法：以三角形开始，除了三个点都在同一个的情况外，它总是一个凸多边形线，所以当它发生时扔掉它们。 （当你处理近似浮点运算时，永远不要检查任何相等的东西，创建一些'>'或'> ='标准，在这种情况下，例如，指定一个允许三角形的最小角度） 。在下一步中，添加一个随机点以用两个相邻的段替换线段（多边形侧）。在每一步中，很容易确定随机点（新顶点）的约束条件，以保持新多边形的凸起。

-SA

As the random distribution is not specified, I would suggest the following simple approach: start with a triangle, which is always a convex polygon except the case when all three point are on the same line, so throw out the cases when it happens. (As you are dealing with approximate floating-point arithmetic, never check anything for equality, create some '>' or '>=' criteria, in this case, for example, specify some minimal angle you would allow for a triangle). On next step, add a random point to replace a line segment (polygon side) with a two adjacent segments. On each step, it's easy to determine the constraints for a random point (new vertex) the way to keep the new polygon convex.

—SA

我只是想到了另一种更简单的算法。



以随机三角形开头，如解决方案一个，并且，在随机数量的步骤中，使用切角操作从N侧创建N + 1侧多边形。为此，采取两个随机但相邻的边。在每一侧，选择代表一侧的线段的随机点内部。用线段连接这两个点，该线段应替换切出角。这将创建两个新角（顶点）而不是切出角。继续下一步。



由于很容易看到，每一步都保证新的多边形是凸的，只要前一个多边形是凸的。当你从凸多边形（三角形）开始时，每一步上的多边形也是凸的。

-SA

I just got an idea of an alternative, simpler algorithm.

Start with a random triangle, as in Solution one, and, in a random number of steps, create a N+1-side polygon from an N-side using the "cut of a corner" operation. For this purpose, take two random but adjacent sides. In each side, choose a random point insider of the line segment representing a side. Connect these two points with a line segment, which should replace the "cut out" corner. This will create two new corners (vertices) instead of "cut-out" one. Proceed to the next step.

As it is easy to see, each step guarantees that a new polygon is convex provided the previous polygon was convex. As you start from a convex polygon (triangle), the polygon on each step is also convex.

—SA

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