algorithm - 生成隨機2D多邊形的算法




matlab random (4)

注意:我已經用一個解決方案更新了我的答案,該解決方案只需要輸入多邊形所需數量的邊,而不是像我以前那樣的幾個非直觀的“幻數”...

通過利用MATLAB類DelaunayTriTriRep以及它們用於處理三角形網格的各種方法,有一種巧妙的方法可以做你想要的。 下面的代碼遵循以下步驟來創建任意簡單的多邊形

  • 生成一些等於所需邊數加上軟糖因子的隨機點。 軟糖因子確保無論三角測量的結果如何,我們都應該有足夠的面以便能夠將三角形網格修剪成具有所需邊數的多邊形。

  • 創建點的Delaunay三角剖分,從而產生由一系列三角形面構成的凸多邊形

  • 如果三角剖分的邊界具有比期望更多的邊,則在具有唯一頂點的邊上選擇隨機三角形面(即,三角形僅與三角剖分的其餘部分共享一條邊)。 移除此三角形面將減少邊界邊緣的數量。

  • 如果三角測量的邊界具有比期望的邊緣更少的邊緣,或者前一步驟無法找到要移除的三角形,則在邊緣上選擇隨機三角形面,其在三角剖分邊界上僅具有其一個邊緣。 移除此三角形面會增加邊界邊緣的數量。

  • 如果找不到與上述標準匹配的三角形面,則發出警告,指出無法找到具有所需邊數的多邊形,並返回當前三角剖分邊界的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

以下是一些示例結果:

生成的多邊形可以是凸的或凹的 ,但是對於更大數量的所需邊,它們幾乎肯定是凹的。 多邊形也是從單位正方形內隨機生成的點生成的,因此具有較大邊數的多邊形通常看起來像具有“方形”邊界(例如上面右下方的50邊多邊形)。 要修改此一般邊界形狀,您可以更改隨機選擇初始xy點的方式(即從高斯分佈等)。

我不知道如何解決這個問題。 我不確定它的任務有多複雜。 我的目標是有一個生成任何多邊形的算法。 我唯一的要求是多邊形不復雜(即邊不相交)。 我正在使用Matlab進行數學運算,但歡迎任何抽象的東西。

任何援助/指導?

編輯:

我正在考慮更多可以生成任何多邊形的代碼甚至是這樣的:


對於凸二維多邊形(完全偏離我的頭頂):

  1. 生成隨機半徑R

  2. 在Radius R的圓周上生成N個隨機點

  3. 圍繞圓圈移動並在圓圈上的相鄰點之間繪製直線。


正如@templatetypedef和@MitchWheat所說,通過生成N隨機角度和半徑很容易實現。 對角度進行排序很重要,否則它將不是簡單的多邊形。 請注意,我使用一個巧妙的技巧繪製閉合曲線 - 我在here描述它。 順便說一句,多邊形可能是凹的

請注意,所有這些多邊形都是星形的。 生成更通用的多邊形根本不是一個簡單的問題。 只是為了讓您體驗一下這個問題 - 請查看http://www.cosy.sbg.ac.at/~held/projects/rpg/rpg.htmlhttp://compgeom.cs.uiuc.edu/~jeffe/open/randompoly.html

function CreateRandomPoly()
    figure();
    colors = {'r','g','b','k'};
    for i=1:5
        [x,y]=CreatePoly();
        c = colors{ mod(i-1,numel(colors))+1};
        plotc(x,y,c);
        hold on;
    end        
end

function [x,y]=CreatePoly()
    numOfPoints = randi(30);
    theta = randi(360,[1 numOfPoints]);
    theta = theta * pi / 180;
    theta = sort(theta);
    rho = randi(200,size(theta));
    [x,y] = pol2cart(theta,rho);    
    xCenter = randi([-1000 1000]);
    yCenter = randi([-1000 1000]);
    x = x + xCenter;
    y = y + yCenter;    
end

function plotc(x,y,varargin)
    x = [x(:) ; x(1)];
    y = [y(:) ; y(1)];
    plot(x,y,varargin{:})
end

這是Mike Ounsworth解決方案的Matlab工作端口。 我沒有為matlab優化它。 我可能會稍後更新解決方案。

function [points] = generatePolygon(ctrX, ctrY, aveRadius, irregularity, spikeyness, numVerts)

%{
Start with the centre of the polygon at ctrX, ctrY, 
then creates the polygon by sampling points on a circle around the centre. 
Randon noise is added by varying the angular spacing between sequential points,
and by varying the radial distance of each point from the centre.

Params:
ctrX, ctrY - coordinates of the "centre" of the polygon
aveRadius - in px, the average radius of this polygon, this roughly controls how large the polygon is, really only useful for order of magnitude.
irregularity - [0,1] indicating how much variance there is in the angular spacing of vertices. [0,1] will map to [0, 2pi/numberOfVerts]
spikeyness - [0,1] indicating how much variance there is in each vertex from the circle of radius aveRadius. [0,1] will map to [0, aveRadius]
numVerts - self-explanatory

Returns a list of vertices, in CCW order.

Website: https://.com/questions/8997099/algorithm-to-generate-random-2d-polygon
%}


    irregularity = clip( irregularity, 0,1 ) * 2*pi/ numVerts;
    spikeyness = clip( spikeyness, 0,1 ) * aveRadius;

    % generate n angle steps
    angleSteps = [];
    lower = (2*pi / numVerts) - irregularity;
    upper = (2*pi / numVerts) + irregularity;
    sum = 0;
    for i =1:numVerts
        tmp = unifrnd(lower, upper);
        angleSteps(i) = tmp;
        sum = sum + tmp;
    end

    % normalize the steps so that point 0 and point n+1 are the same
    k = sum / (2*pi);
    for i =1:numVerts
        angleSteps(i) = angleSteps(i) / k;
    end

    % now generate the points
    points = [];
    angle = unifrnd(0, 2*pi);
    for i =1:numVerts
        r_i = clip( normrnd(aveRadius, spikeyness), 0, 2*aveRadius);
        x = ctrX + r_i* cos(angle);
        y = ctrY + r_i* sin(angle);
        points(i,:)= [(x),(y)];
        angle = angle + angleSteps(i);
    end

end


function value = clip(x, min, max)
   if( min > max ); value = x; return; end
   if( x  < min ) ; value = min; return; end
   if( x  > max ) ; value = max; return; end
   value = x;
end




computational-geometry