生成随机二维多边形的算法

Question

我不确定如何解决这个问题。我不确定这是一项多么复杂的任务。我的目标是拥有一种生成任何多边形的算法。我唯一的要求是多边形不复杂(即边不相交)。我正在使用 Matlab 进行数学运算，但欢迎使用任何抽象的内容。

任何帮助/指导？

编辑:

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

Answer 1

我采纳了@MitchWheat 和@templatetypedef 关于在圆上采样点的想法，并将其更进一步。

在我的应用程序中，我需要能够控制多边形的怪异程度，即从规则多边形开始，随着我调高参数，它们会变得越来越困惑。基本思想如@templatetypedef所述；每次绕着圆圈走一个随机的角度步长，并在每一步中在随机半径处放置一个点。在方程式中，我生成的角度步长为

其中 theta_i 和 r_i 给出每个点相对于中心的角度和半径，U(min, max) 从均匀分布中拉取随机数，N(mu, sigma) 从高斯分布中拉取随机数, 和 clip(x, min, max) 将一个值限制在一个范围内。这为我们提供了两个非常好的参数来控制多边形的狂野程度 - 我称之为 不规则性 的 epsilon 控制点是否均匀地围绕圆角分布，以及我称之为 sigma spikeyness 控制点可以从半径 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.