算法来产生随机2D多边形 [英] Algorithm to generate random 2D polygon

问题描述

我不知道如何解决这个问题。我不知道它是多么复杂的任务。我的目标是有一种算法，任何多边形。我的唯一的要求是该多边形不复杂（即两侧不相交）。我用Matlab做的数学，但抽象的东西是值得欢迎的。

I'm not sure how to approach this problem. I'm not sure how complex a task it is. My aim is to have an algorithm that generates any polygon. My only requirement is that the polygon is not complex (i.e. sides do not intersect). I'm using Matlab for doing the maths but anything abstract is welcome.

任何援助/方向？

编辑：

我想更多的code，可能产生的任何多边形甚至这样的事情：

I was thinking more of code that could generate any polygon even things like this:

推荐答案

注：我已经更新，而不是一对夫妇的我的一个解决方案，只是作为输入侧的所需数量的多边形答案，非直观的幻数就像我以前... 的

有一个整洁的方式做你想做的，采取的MATLAB类优势<一href="http://www.mathworks.com/help/techdoc/ref/delaunaytriclass.html">DelaunayTri和 TriRep ，他们采用的处理三角形网格的各种方法。下面的code遵循下列步骤来创建一个任意简单的多边形：

There's a neat way to do what you want by taking advantage of the MATLAB classes DelaunayTri and TriRep and the various methods they employ for handling triangular meshes. The code below follows these steps to create an arbitrary simple polygon:

• 生成若干个随机点等于边的期望数量加上一个修正因子的。该误差系数保证，无论三角测量的结果，我们应该有足够的方面要能够向下修整三角网格到多边形边的所需数量。

• Generate a number of random points equal to the desired number of sides plus a fudge factor. The fudge factor ensures that, regardless of the result of the triangulation, we should have enough facets to be able to trim the triangular mesh down to a polygon with the desired number of sides.

创建点的德洛奈三角剖分，导致凸多边形的是从一系列的构造三角面。

Create a Delaunay triangulation of the points, resulting in a convex polygon that is constructed from a series of triangular facets.

如果三角测量的边界比所需更多的边，挑上具有独特的顶点（即三角形只股票一个边缘的三角测量的其余部分）边缘的任意三角面片。删除此三角面将减少边界边的数量。

If the boundary of the triangulation has more edges than desired, pick a random triangular facet on the edge that has a unique vertex (i.e. the triangle only shares one edge with the rest of the triangulation). Removing this triangular facet will reduce the number of boundary edges.

如果三角测量的边界具有较少的边缘比需要的话，或previous步骤是无法找到一个三角形以除去，选择一个随机三角面上具有只在其一个边缘上的边缘三角边界。删除此三角面会增加边界边的数量。

If the boundary of the triangulation has fewer edges than desired, or the previous step was unable to find a triangle to remove, pick a random triangular facet on the edge that has only one of its edges on the triangulation boundary. Removing this triangular facet will increase the number of boundary edges.

如果没有三角面可找到符合上述标准，发布与边的所需数目的多边形无法找到一个警告，并返回x和当前三角边界的y坐标。否则，保持除去三角面直到边缘的期望数量被满足，则返回x和三角边界的y坐标。

If no triangular facets can be found matching the above criteria, post a warning that a polygon with the desired number of sides couldn't be found and return the x and y coordinates of the current triangulation boundary. Otherwise, keep removing triangular facets until the desired number of edges is met, then return the x and y coordinates of triangulation boundary.

下面是所产生的功能：

function [x, y, dt] = simple_polygon(numSides)

    if numSides < 3
        x = [];
        y = [];
        dt = DelaunayTri();
        return
    end

    oldState = warning('off', 'MATLAB:TriRep:PtsNotInTriWarnId');

    fudge = ceil(numSides/10);
    x = rand(numSides+fudge, 1);
    y = rand(numSides+fudge, 1);
    dt = DelaunayTri(x, y);
    boundaryEdges = freeBoundary(dt);
    numEdges = size(boundaryEdges, 1);

    while numEdges ~= numSides
        if numEdges > numSides
            triIndex = vertexAttachments(dt, boundaryEdges(:,1));
            triIndex = triIndex(randperm(numel(triIndex)));
            keep = (cellfun('size', triIndex, 2) ~= 1);
        end
        if (numEdges < numSides) || all(keep)
            triIndex = edgeAttachments(dt, boundaryEdges);
            triIndex = triIndex(randperm(numel(triIndex)));
            triPoints = dt([triIndex{:}], :);
            keep = all(ismember(triPoints, boundaryEdges(:,1)), 2);
        end
        if all(keep)
            warning('Couldn''t achieve desired number of sides!');
            break
        end
        triPoints = dt.Triangulation;
        triPoints(triIndex{find(~keep, 1)}, :) = [];
        dt = TriRep(triPoints, x, y);
        boundaryEdges = freeBoundary(dt);
        numEdges = size(boundaryEdges, 1);
    end

    boundaryEdges = [boundaryEdges(:,1); boundaryEdges(1,1)];
    x = dt.X(boundaryEdges, 1);
    y = dt.X(boundaryEdges, 2);

    warning(oldState);

end

和这里有一些样品的结果：

And here are some sample results:

所产生的多边形可以是凸或凹的，但对于更大的期望的边的数量，他们几乎肯定是凹。也从内一个单位正方形随机生成的点产生的多边形，所以多边形较大侧的数字将通常看起来他们有一个方形边界（如右下方示例与上面的50边的​​多边形）。要修改这个一般边界的形状，你可以改变的方式初始 X 和是点是随机选择的（即由高斯分布等）。

The generated polygons could be either convex or concave, but for larger numbers of desired sides they will almost certainly be concave. The polygons are also generated from points randomly generated within a unit square, so polygons with larger numbers of sides will generally look like they have a "squarish" boundary (such as the lower right example above with the 50-sided polygon). To modify this general bounding shape, you can change the way the initial x and y points are randomly chosen (i.e. from a Gaussian distribution, etc.).

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