Алгоритм генерации случайного двумерного многоугольника

Ответ 1

Есть отличный способ сделать то, что вы хотите, используя преимущества классов MATLAB DelaunayTri и TriRep и различных методов, которые они используют для обработки треугольных сеток. Код ниже следует за этими шагами, чтобы создать произвольный простой многоугольник:

• Создайте количество случайных точек, равное требуемому количеству сторон плюс коэффициент выдумки. Коэффициент выдумки гарантирует, что, независимо от результата триангуляции, у нас должно быть достаточно граней, чтобы можно было обрезать треугольную сетку до многоугольника с требуемым количеством сторон.

• Создайте триангуляцию Делоне для точек, в результате чего получится выпуклый многоугольник, построенный из серии треугольных граней.

• Если граница триангуляции имеет больше ребер, чем нужно, выберите случайную треугольную грань на ребре, которое имеет уникальную вершину (т.е. Треугольник имеет только одно ребро с остальной частью триангуляции). Удаление этой треугольной грани уменьшит количество граничных ребер.

• Если граница триангуляции имеет меньше ребер, чем необходимо, или предыдущий шаг не смог найти треугольник для удаления, выберите случайный треугольный фасет на ребре, у которого только один из его ребер на границе триангуляции. Удаление этой треугольной грани увеличит количество граничных ребер.

• Если треугольные грани, соответствующие вышеуказанным критериям, не найдены, выведите предупреждение о том, что полигон с нужным количеством сторон не может быть найден, и верните координаты 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-сторонним многоугольником). Чтобы изменить эту общую ограничивающую форму, вы можете изменить способ случайного выбора начальных точек x и y (т.е. Из распределения Гаусса и т.д.).

Ответ 2

Я взял @MitchWheat и @templatetypedef идею точек выборки на круге и немного отнесся к ней.

В моем приложении мне нужно иметь возможность контролировать, насколько странны полигоны, т.е. начать с правильных многоугольников, и когда я проверю параметры, они становятся все более хаотичными. Основная идея указана в @templatetypedef; передвигайтесь по кругу, беря случайный шаг angular каждый раз, и на каждом шаге ставьте точку на случайный радиус. В уравнениях я генерирую шаги angular как

где theta_i и r_i дают угол и радиус каждой точки относительно центра, U (min, max) вытягивает случайное число из равномерного распределения, а N (mu, sigma) вытягивает случайное число из гауссовского распределения, и клип (x, min, max) порождает значение в диапазоне. Это дает нам два действительно приятных параметра для контроля того, насколько дикими являются полигоны - эпсилон, который я назову неравномерность, определяет, равномерны ли точки равномерно по кругу, и сигма, которую я назову spikeyness, который контролирует, насколько точки могут меняться от круга радиуса r_ave. Если вы установили оба из них в 0, вы получите совершенно правильные многоугольники, если вы их подведете, то полигоны станут более сумасшедшими.

Я быстро взбивал это на питоне и получал такие вещи:

Здесь полный код python:

import math, random

def 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.
    '''

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

    # generate n angle steps
    angleSteps = []
    lower = (2*math.pi / numVerts) - irregularity
    upper = (2*math.pi / numVerts) + irregularity
    sum = 0
    for i in range(numVerts) :
        tmp = random.uniform(lower, upper)
        angleSteps.append( tmp )
        sum = sum + tmp

    # normalize the steps so that point 0 and point n+1 are the same
    k = sum / (2*math.pi)
    for i in range(numVerts) :
        angleSteps[i] = angleSteps[i] / k

    # now generate the points
    points = []
    angle = random.uniform(0, 2*math.pi)
    for i in range(numVerts) :
        r_i = clip( random.gauss(aveRadius, spikeyness), 0, 2*aveRadius )
        x = ctrX + r_i*math.cos(angle)
        y = ctrY + r_i*math.sin(angle)
        points.append( (int(x),int(y)) )

        angle = angle + angleSteps[i]

    return points

 def clip(x, min, max) :
     if( min > max ) :  return x    
     elif( x < min ) :  return min
     elif( x > max ) :  return max
     else :             return x

@MateuszKonieczny - это код для создания изображения многоугольника из списка вершин.

verts = generatePolygon( ctrX=250, ctrY=250, aveRadius=100, irregularity=0.35, spikeyness=0.2, numVerts=16 )

black = (0,0,0)
white=(255,255,255)
im = Image.new('RGB', (500, 500), white)
imPxAccess = im.load()
draw = ImageDraw.Draw(im)
tupVerts = map(tuple,verts)

# either use .polygon(), if you want to fill the area with a solid colour
draw.polygon( tupVerts, outline=black,fill=white )

# or .line() if you want to control the line thickness, or use both methods together!
draw.line( tupVerts+[tupVerts[0]], width=2, fill=black )

im.show()

# now you can save the image (im), or do whatever else you want with it.

Ответ 3

Для выпуклого двумерного многоугольника (полностью с головы):

• Создайте случайный радиус, R

• Создайте N случайных точек на окружности окружности радиуса R

• Перемещайтесь по кругу и рисуйте прямые линии между соседними точками на круге.

Ответ 4

Как сказали @templatetypedef и @MitchWheat, это легко сделать, создав N случайные углы и радиусы. Важно сортировать углы, иначе это будет не простой полигон. Обратите внимание, что я использую аккуратный трюк, чтобы нарисовать замкнутые кривые - я описал это в здесь. Кстати, многоугольники могут быть вогнутыми.

Обратите внимание, что все эти полигоны будут иметь звездообразную форму. Создание более общего многоугольника - не простая проблема. Просто чтобы вы почувствовали вкус проблемы - проверьте  http://www.cosy.sbg.ac.at/~held/projects/rpg/rpg.html и http://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

Ответ 5

Вот рабочий порт для решения 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://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

Ответ 6

Как насчет генерации случайных точек, а затем выяснения, в каком порядке их разместить, чтобы ни одно из ребер не перекрывалось? Я не так много изучал, так что это не всегда возможно, но я думаю, что это... (Пожалуйста, дайте мне знать, если это не так, и если это так, точки, которые не соответствуют, могут быть отброшены или восстановлены Я также не уверен, существует ли эффективный способ сделать это для большого количества очков, но, по крайней мере, он должен быть очень быстрым для небольшого количества очков.