Алгоритм генерации случайного 2D полигона

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

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

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

Я быстро вскрыл это в python и получил материал, подобный этому:

Вот полный код 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.

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

1. Генерируем случайный радиус, R

2. Сгенерируем N случайных точек на окружности радиуса R

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

Как @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

Вот это работает порт для MATLAB раствора Майк Ounsworth. Я не оптимизировал его для 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