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

Question

我不确定如何解决这个问题。我也不知道任务有多复杂。我的目标是拥有一个可以生成任意多边形的算法。唯一的要求是多边形不复杂（即边不相交）。我正在使用Matlab进行数学计算，但欢迎任何抽象的东西。

有什么帮助/指导吗？

编辑：

我更多地考虑了能够生成任何多边形的代码，甚至像这样的形状：

- s5s

---

“随机”是什么意思？你知道你要生成的分布吗？ - templatetypedef

@templatetypedef 显然他想要一个能够生成随机的简单多边形的算法，因为通常情况下，任意顺序的n个点都会产生自相交的多边形。 - Jorge

在随机半径的圆上的随机位置放置随机数量的点并连接它们，使它们成为连续的。 - dfens

这样的多边形有一个名字 - 简单多边形，确切地说。 - Sibbs Gambling

...任何抽象的东西都受欢迎。这是相关论文：Hada，Pratik Shankar，"生成2D形状的方法"（2014）。UNLV论文、学位论文、专业论文和顶峰论文。2182。 - Comrade Che

Answer 1

我采用了 @MitchWheat 和 @templatetypedef 的想法，对在圆上取样点的方法进行了一些扩展。

我的应用需要能够控制多边形的变形程度，即从正则多边形开始，逐渐增加参数后，它们会变得越来越混乱。基本想法与 @templatetypedef 所述相同：每次绕着圆走时随机选取角度步长，并在每一步处以随机半径放置一个点。用公式表示，我生成角度步长为：

其中θ_i和r_i分别给出每个点相对于圆心的角度和半径，U(min，max) 从均匀分布中获取随机数，N(mu，sigma) 从高斯分布中获取随机数，clip(x，min，max)将值限制在一定范围内。这为我们提供了两个非常好的参数来控制多边形的不规则程度 - epsilon，我将其称为不规则度，控制点是否沿圆周角度均匀分布；sigma，我将其称为尖锐度，控制点离平均半径r_ave的距离变化程度。如果将这两个参数都设置为0，则会得到完全正则的多边形，如果将它们增加，则多边形会变得越来越疯狂。

我很快就用 Python 编写了以下代码，并生成了一些这样的东西：

以下是完整的 Python 代码：

import math, random
from typing import List, Tuple


def generate_polygon(center: Tuple[float, float], avg_radius: float,
                     irregularity: float, spikiness: float,
                     num_vertices: int) -> List[Tuple[float, float]]:
    """
    Start with the center of the polygon at center, then creates the
    polygon by sampling points on a circle around the center.
    Random noise is added by varying the angular spacing between
    sequential points, and by varying the radial distance of each
    point from the centre.

    Args:
        center (Tuple[float, float]):
            a pair representing the center of the circumference used
            to generate the polygon.
        avg_radius (float):
            the average radius (distance of each generated vertex to
            the center of the circumference) used to generate points
            with a normal distribution.
        irregularity (float):
            variance of the spacing of the angles between consecutive
            vertices.
        spikiness (float):
            variance of the distance of each vertex to the center of
            the circumference.
        num_vertices (int):
            the number of vertices of the polygon.
    Returns:
        List[Tuple[float, float]]: list of vertices, in CCW order.
    """
    # Parameter check
    if irregularity < 0 or irregularity > 1:
        raise ValueError("Irregularity must be between 0 and 1.")
    if spikiness < 0 or spikiness > 1:
        raise ValueError("Spikiness must be between 0 and 1.")

    irregularity *= 2 * math.pi / num_vertices
    spikiness *= avg_radius
    angle_steps = random_angle_steps(num_vertices, irregularity)

    # now generate the points
    points = []
    angle = random.uniform(0, 2 * math.pi)
    for i in range(num_vertices):
        radius = clip(random.gauss(avg_radius, spikiness), 0, 2 * avg_radius)
        point = (center[0] + radius * math.cos(angle),
                 center[1] + radius * math.sin(angle))
        points.append(point)
        angle += angle_steps[i]

    return points

def random_angle_steps(steps: int, irregularity: float) -> List[float]:
    """Generates the division of a circumference in random angles.

    Args:
        steps (int):
            the number of angles to generate.
        irregularity (float):
            variance of the spacing of the angles between consecutive vertices.
    Returns:
        List[float]: the list of the random angles.
    """
    # generate n angle steps
    angles = []
    lower = (2 * math.pi / steps) - irregularity
    upper = (2 * math.pi / steps) + irregularity
    cumsum = 0
    for i in range(steps):
        angle = random.uniform(lower, upper)
        angles.append(angle)
        cumsum += angle

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

def clip(value, lower, upper):
    """
    Given an interval, values outside the interval are clipped to the interval
    edges.
    """
    return min(upper, max(value, lower))

---

@MateuszKonieczny 这是一段用于从顶点列表创建多边形图像的代码。

vertices = generate_polygon(center=(250, 250),
                            avg_radius=100,
                            irregularity=0.35,
                            spikiness=0.2,
                            num_vertices=16)

black = (0, 0, 0)
white = (255, 255, 255)
img = Image.new('RGB', (500, 500), white)
im_px_access = img.load()
draw = ImageDraw.Draw(img)

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

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

img.show()

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

- Mike Ounsworth

---

很遗憾，由于该算法使用极坐标，因此某些类型的多边形无法创建，例如这个：https://i.stack.imgur.com/bxa3b.png。 - Comrade Che

这种多边形被称为星凸多边形。 - Cris Luengo

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点的方式（即从高斯分布等中选择）。

- gnovice

---

虽然这是一个好答案，但还有另一个条件需要检查。如果您要移除的三角形只有一个边在凸壳上，那么您必须确保对面的顶点不在凸壳上，否则您将得到两个具有一个公共点的多边形。 - SmacL

@Shane：这种情况在上面的代码中已经考虑到了。行keep = all(ismember(triPoints, boundaryEdges(:,1)), 2);标记一个三角形被保留，如果它的所有顶点都位于自由边界上，即如果一个三角形有一条边和对立的顶点都在自由边界上，则该三角形将永远不会从三角剖分中移除，避免将多边形分成两部分。 - gnovice

Answer 3

针对一个凸2D多边形（完全是我自己想出来的）：

1. 生成一个随机半径 R

2. 在半径为 R 的圆周上生成 N 个随机点

3. 沿着圆周移动，并在相邻两点之间绘制直线。

- Mitch Wheat

---

我还可以补充一点，通常问题是在图上找到一个非相交的哈密顿回路。显然，对于一个n个顶点的图，有(n-1)!/2个这样的回路，这意味着n个随机点定义了(n-1)!/2个不同的多边形。如果你有一个检测两条边是否相交的函数（这很容易），那么你可以随机选择一个点，随机选择另一个点，测试这条边是否与现有边相交，并保留/拒绝该点等等。这样，你就可以在平面上创建一般的随机多边形。 - Jorge

这种方法，即使采用@templatetypedef建议的改进，有时也会产生无效的多边形。例如：https://i.stack.imgur.com/DNGd5.png - Georgy

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

- Andrey Rubshtein

Answer 5

这是一个针对Matlab的Mike 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://dev59.com/yGox5IYBdhLWcg3wvW3X
%}


    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

- MosGeo

Answer 6

拥有计算几何库的帮助下，一个简单而有效的技巧是：

• 生成随机点集
• 计算点集的凹壳
• (可选) 平滑凸壳（以去除狭窄的部分等）

可变凹度凸壳

带（高斯）平滑的凹壳

- micycle