生成随机二维多边形的算法 [英] Algorithm to generate random 2D polygon

问题描述

我不知道如何解决这个问题.我不确定这是一项多么复杂的任务.我的目标是拥有一种生成任何多边形的算法.我唯一的要求是多边形不复杂(即边不相交).我正在使用 Matlab 进行数学运算，但欢迎任何抽象的东西.

任何帮助/方向?

我在想更多可以生成任何多边形的代码，甚至像这样的东西:

解决方案

利用 MATLAB 类，有一种巧妙的方法可以完成您想做的事情 ，但是对于更多的所需边，它们几乎肯定会是凹的.多边形也是由单位正方形内随机生成的点生成的，因此边数较多的多边形通常看起来像具有方形"边界(例如上面右下角的 50 边多边形示例).要修改此一般边界形状，您可以更改随机选择初始 x 和 y 点的方式(即从高斯分布等中).

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.

Any aid/direction?

EDIT:

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

解决方案

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.

• 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.

• 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.

Here's the resulting function:

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:

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.).

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