Algorithmus zum Erzeugen eines zufälligen 2D-Polygons

Hinweis: ich habe aktualisiert, meine Antwort mit einer Lösung, die einfach nimmt als Eingabe eine gewünschte Anzahl von Seiten für das polygon, statt ein paar nicht-intuitive "magischen zahlen", wie ich vor hatte...

Es ist eine nette Weise, das zu tun, was Sie wollen, nutzen Sie die MATLAB-Klassen DelaunayTri und TriRep und die verschiedenen Methoden, die Sie beschäftigen, für die Handhabung von dreieckigen Maschen. Der code unten folgt diese Schritte und erstellen Sie eine beliebige einfache polygon:

• Generieren einer Anzahl zufälliger Punkte gleich der gewünschten Anzahl der Seiten plus eine fudge-Faktor. Der fudge-Faktor stellt sicher, dass unabhängig vom Ergebnis der triangulation, wir sollten genügend Facetten, um in der Lage sein, um schneiden Sie die dreieckige Gitter nach unten auf eine Fläche mit der gewünschten Anzahl der Seiten.

• Erstellen Delaunay-triangulation der Punkte, was eine konvexes polygondie aufgebaut ist aus einer Reihe von dreieckigen Facetten.

• Wenn die Grenze der triangulation hat mehr Kanten als gewünscht, wählen Sie eine zufällige dreieckige Facette auf dem Rand, hat einen eindeutigen Knoten (d.h. das Dreieck teilt eine Kante mit dem rest der triangulation). Das entfernen dieses dreieckige Facette wird die Anzahl der Begrenzungskanten.

• Wenn die Grenze der triangulation hat weniger Kanten als die gewünschte, oder der Vorherige Schritt nicht in der Lage war zu finden, ein Dreieck zu entfernen, wählen Sie eine zufällige dreieckige Facette auf dem Rand, hat nur eine Kante, die auf der triangulation Grenze. Das entfernen dieses dreieckige Facette erhöht sich die Anzahl von Begrenzungskanten.

• Wenn keine dreieckigen Facetten können gefunden werden, die den oben genannten Kriterien, stellen Sie eine Warnung, dass ein polygon mit der gewünschten Anzahl an Seiten nicht gefunden werden konnte und die Rückkehr der x-und y-Koordinaten der aktuellen triangulation Grenze. Ansonsten halten entfernen dreieckigen Facetten, bis die gewünschte Anzahl der Kanten erfüllt ist, dann wieder die x-und y-Koordinaten der triangulation Grenze.

Hier ist die resultierende Funktion:

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

Und hier sind einige Beispiel-Ergebnisse:

Den generierten Polygone werden könnte, entweder konvex oder konkavaber für eine größere Anzahl von gewünschten Seiten werden Sie fast sicher konkav. Die Polygone werden ebenfalls generiert aus Punkten, die zufällig generiert in einem Gerät Platz, also Polygone mit einer größeren Anzahl von Seiten wird in der Regel schauen, wie Sie einen "quadratischen" - Grenze (wie der unteren rechten Beispiel oben mit den 50-seitiges polygon). Zum ändern dieser Allgemeinen umschließende Form, Sie können ändern, wie der erste x und y Punkte werden nach dem Zufallsprinzip ausgewählt (D. H. von einer Gauß-Verteilung, usw.).

InformationsquelleAutor der Antwort gnovice

Für ein 2D-polygon konvex (völlig aus der Spitze von meinem Kopf):

1. Generiert einen zufälligen radius, R

2. Generieren N zufällige Punkte auf dem Umfang eines Kreises mit dem Radius R

3. Bewegen sich um den Kreis und gerade Linien zwischen benachbarten Punkten auf dem Kreis.

InformationsquelleAutor der Antwort Mitch Wheat

Hier ist eine funktionierende Schnittstelle für Matlab von Mike Ounsworth Lösung. Ich habe nicht optimiert für matlab. Ich könnte aktualisieren Sie die Lösung später.

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://stackoverflow.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

InformationsquelleAutor der Antwort MosGeo