随机生成一个指定边数多边形

随机生成一个指定边数多边形

  算法背景：我们想完成一个可以随机生成指定边数多边形的算法。在生成过程中，需要避免随机点连接过程中交叉的问题。
算法步骤
  1、为了随机生成一个n边形，我们先随机生成n个点。例如下图，我们随机生成5个点。然后对这五个点按照x坐标的大小排序。序号按照x从小到大依次增加。

  2、首先连接最左边的1、2、 3点，形成一个三角形。

  3、在添加下一个点的时候，根据通视原则删除与新增点不通视的边。

  4、逐次连接形成多边形。

def randpolygon(num):
    '''
    :param num: 边数为num
    :return:返回多边形的顶点
    '''
    np.random.seed(30)
    points = np.random.randint(50, 400, size=(num, 2))  # 随机num个坐标点
    points = points[np.lexsort(points[:, ::-1].T)]  # 对坐标x进行排序
    edges = [[0, 1], [2, 1], [2, 0]]
    u = 2  # 记录当前新增顶点
    v1 = 0
    v2 = 1  # 保存最新顶点的两个边
    for i in range(3, num):  # 遍历剩下的点
        mid1_x = (points[u, 0] + points[v1, 0]) / 2
        mid1_y = (points[u, 1] + points[v1, 1]) / 2
        mid2_x = (points[u, 0] + points[v2, 0]) / 2
        mid2_y = (points[u, 1] + points[v2, 1]) / 2
        cross_count1 = 0  # 记录交点个数
        cross_count2 = 0
        l1 = [points[i, 0], points[i, 1], mid1_x, mid1_y]
        l2 = [points[i, 0], points[i, 1], mid2_x, mid2_y]
        for edge in edges:  # 所有已经存在的边
            l = [points[edge[0], 0], points[edge[0], 1], points[edge[1], 0], points[edge[1], 1]]
            cross_count1 += len(cross(l1, l, True))
            cross_count2 += len(cross(l2, l, True))
        edges.append([i, u])
        if cross_count1 <= 1:
            edges.remove([u, v1])
            edges.append([i, v1])
            v2 = u
            u += 1

        elif cross_count2 <= 1:
            edges.remove([u, v2])
            edges.append([i, v2])
            v1 = u
            u += 1
    pts = points.copy()
    edge1 = 0
    edge2 = 1
    i = 2
    while edge2 != 0:
        for edge in edges:
            if edge[1] == edge2 and edge[0] != edge1:

                edge1 = edge2
                edge2 = edge[0]
                if edge2 == 0:
                    break
                pts[i, :] = points[edge[0], :]
                i += 1
            elif edge[0] == edge2 and edge[1] != edge1:

                edge1 = edge2
                edge2 = edge[1]
                if edge2 == 0:
                    break
                pts[i, :] = points[edge[1], :]
                i += 1
    return pts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

生成多边形结果：