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

Question

Я не уверен, как подойти к этой проблеме. Я не уверен, насколько сложна задача. Моя цель - иметь алгоритм, который генерирует любой многоугольник. Моим единственным требованием является то, что многоугольник не является сложным (т. Е. Стороны не пересекаются). Я использую Matlab для выполнения математики, но что-то абстрактное приветствуется.

Любая помощь/направление?

EDIT:

Я думал больше кода, который может генерировать любой многоугольник даже такие вещи, как это:

Answer 1

Примечание: Я обновил свой ответ с решением, которое просто принимает в качестве входных данных желаемого числа сторон многоугольника, а пара не-интуитивных «магических чисел» как я был раньше ...

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

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

• Создайте триангуляцию Делоне, получив 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 

И вот некоторые результаты выборки:

Сформированные многоугольники могут быть либо convex or concave, но для большего числа желаемых сторон они почти наверняка будут вогнутыми. Многоугольники также генерируются из точек, случайным образом сгенерированных в единичном квадрате, поэтому многоугольники с большим числом сторон обычно выглядят так, как будто они имеют «квадратную» границу (например, нижний правый пример выше с 50-сторонним многоугольником). Чтобы изменить эту общую ограничительную форму, вы можете изменить способ случайного выбора начальных x и y точек (т. Е. Из распределения Гаусса и т. Д.).

Answer 2

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

1. Создание случайного радиуса, R

2. Генерировать N случайных точек по окружности окружности радиуса R

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

Answer 3

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

Обратите внимание, что все эти многоугольники будут иметь форму звезды. Создание более общего многоугольника - не простая проблема. Просто, чтобы дать вам волю проблемы - ознакомьтесь с 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 

Answer 4

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

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

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

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

Вот полный код питона:

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.