生成随机2D多边形的算法

Question

我不知道如何解决这个问题.我不确定它的任务有多复杂.我的目标是拥有一个生成任何多边形的算法.我唯一的要求是多边形不复杂(即边不相交).我正在使用Matlab进行数学运算,但欢迎任何抽象的东西.

任何援助/指导？

编辑:

我正在考虑更多可以生成任何多边形的代码甚至是这样的:

Answer 1

我拿了@MitchWheat和@ templatetypedef的想法,在一个圆圈上采样点,并把它放得更远.

在我的应用程序中,我需要能够控制多边形的奇怪程度,即从常规多边形开始,当我调高参数时,它们变得越来越混乱.基本思路如@templatetypedef所述; 每次以一个随机的角度步长绕着圆圈行走,并且在每个步骤中将一个点放在随机半径上.在方程式中,我生成角度步长为

其中theta_i和r_i给出每个点相对于中心的角度和半径,U(min,max)从均匀分布中拉出一个随机数,N(mu,sigma)从高斯分布中拉出一个随机数,并剪辑(x,min,max)将值阈值化为范围.这给了我们两个非常好的参数来控制多边形的多么狂野 - 我称之为不规则的 epsilon 控制点是否围绕圆圈均匀地成角度空间,而sigma我称之为spikeyness控制多少点可以从半径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.

Answer 2

通过利用MATLAB类DelaunayTri以及TriRep它们用于处理三角形网格的各种方法,有一种巧妙的方法可以做你想要的.下面的代码遵循以下步骤来创建任意简单的多边形:

• 生成一些等于所需边数的随机点加上一个软糖因子.软糖因子确保无论三角测量的结果如何,我们都应该有足够的面以能够将三角形网格修剪成具有所需边数的多边形.

• 创建点的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边多边形).要修改此一般边界形状,您可以更改初始x和y点随机选择的方式(即从高斯分布等).

Answer 3

对于凸二维多边形(完全偏离我的头顶):

1. 生成随机半径R

2. 在Radius R的圆周上生成N个随机点

3. 围绕圆圈移动并在圆上相邻点之间绘制直线.

Answer 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