algorithm - 生成随机2D多边形的算法

我不确定如何解决这个问题。我不确定任务有多复杂。我的目标是拥有一种可以生成任何多边形的算法。我唯一的要求是多边形不复杂(即边不相交)。我正在使用Matlab进行数学运算，但是任何抽象的形式都可以接受。

有帮助/指示吗？

编辑:

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

最佳答案

利用MATLAB类 DelaunayTri 和 TriRep 以及它们用于处理三角形网格的各种方法，有一种巧妙的方法来执行您想要的操作。以下代码按照以下步骤创建任意simple polygon:

生成等于所需边数和软糖因子的随机点数。通过软键因素，无论三角剖分的结果如何，我们都应具有足够的小平面，以便能够将三角形网格修剪为具有所需边数的多边形。

创建点的Delaunay三角剖分，从而形成由一系列三角形小平面构成的convex polygon。

如果三角剖分的边界具有比所需的更多的边，请在具有唯一顶点的边上选择一个随机的三角形小平面(即，三角形仅与三角剖分的其余部分共享一个边)。删除此三角形小平面将减少边界边的数量。

如果三角剖分的边界的边缘少于所需的边缘，或者上一步无法找到要删除的三角形，请在仅三角剖分边界的一个边缘的边缘上选择一个随机的三角形小平面。删除此三角形小平面将增加边界边的数量。

如果找不到符合上述条件的三角形面，请发出警告，提示找不到所需边数的多边形，并返回当前三角剖分边界的x和y坐标。否则，请继续删除三角形小平面，直到满足所需的边数，然后返回三角剖分边界的x和y坐标。

这是结果函数:

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

以下是一些示例结果:

生成的多边形可以是凸的也可以是concave，但是对于所需的更多侧面，几乎可以肯定它们是凹的。多边形也是从在单位正方形内随机生成的点生成的，因此具有较多边数的多边形通常看起来像具有“方形”边界(例如，上面带有50边多边形的右下示例)。要修改此总体边界形状，您可以更改随机选择初始x和y点的方式(即从高斯分布等)。