algorithm - 对多边形的点进行排序以进行绘制

Question

我有一个矩阵(0 表示无，1 表示地形)代表我游戏中的一个关卡。矩阵对应于我的屏幕被分解成的网格，并指示我的地形走向。

我的地形实际上由网格内每个 block 的角上的 4 个点组成。当您有多个连接的 block 时，我使用合并单元格算法来删除重复点和任何内部点。结果是我得到了一个仅表示多边形外边缘的点列表。

要绘制此多边形，我需要将这些点按某种顺序(顺时针或逆时针)排列，以便每个点后面都有它的相邻点。显然第一个和最后一个点需要是邻居。因为这一切都在一个网格中，所以我知道相邻点之间的确切距离。

问题是我无法想出一种算法，该算法允许我在按顺序排列点的同时绕着多边形的边缘“走动”。我相信应该有一种方法可以利用我有表示几何图形的矩阵这一事实，这意味着只有一种可能的方法来绘制多边形(即使它是凹面的)。

我已经尝试了几种使用贪婪算法的方法，但似乎无法找到一种方法来知道在每种情况下我想朝哪个方向行进。鉴于任何特定点最多可以有 3 个邻居(第四个不包括在内，因为它是“起点”，这意味着我已经对它进行了排序)我需要一种方法来了解要移动的方向。

更新

我一直在尝试的另一种方法是按 X(使用 Y 的决胜局)对点进行排序，这给了我最上面/最左边的边缘。它还保证我从外边缘开始。然而，我仍在努力寻找一种算法来保证我留在外面而不穿越。

这是一个示例矩阵:

0 0 0 0 0 0 0 0 0 0

0 0 0 1 1 1 0 0 0 0

0 0 0 0 0 1 0 0 0 0

0 0 0 0 0 1 1 1 0 0

对应于此(黑点代表我的观点):

Answer 1

首先请考虑对于一般矩阵，输出可以由多个闭环组成；例如矩阵的边界

形成三个不同的循环，其中一个放在另一个循环中。

要提取这些循环，第一步是构建所有“墙”的 map :每当一个单元格的内容与同一行的下一个单元格的内容不同时，您就有一面垂直墙；当内容与下一行中的同一单元格不同时，您就会看到一堵水平墙。

data = [[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
        [ 0, 1, 1, 1, 1, 0, 0, 0, 0, 0 ],
        [ 0, 1, 0, 0, 1, 0, 1, 1, 0, 0 ],
        [ 0, 1, 0, 0, 1, 0, 1, 1, 1, 0 ],
        [ 0, 1, 1, 1, 1, 0, 0, 1, 1, 0 ],
        [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]]

rows = len(data)
cols = len(data[0])

walls = [[2*(data[r][c] != data[r][c+1]) + (data[r][c] != data[r+1][c])
          for c in range(cols-1)]
         for r in range(rows-1)]

在上面的示例中，我使用了两个位:0x01 标记水平墙，0x02 标记垂直墙。对于给定的 (r, c) 单元格，壁是单元格的右壁和底壁。

为简单起见，我还假设感兴趣的区域没有触及矩阵的极限；这可以通过添加额外的零行和列或将矩阵访问包装在一个函数中来解决，该函数为矩阵外的虚拟元素返回 0。

要构建边界列表，您需要简单地从墙上的任意点开始并沿着墙壁移动，在处理它们时从 map 上移除墙壁。当你不能再移动时，一个循环已经完成(你保证完成循环，因为在以这种方式从内部/外部标志矩阵构建的图形中，保证所有顶点的度数相同)。

使用奇偶填充规则同时填充所有这些循环也可以保证重现原始矩阵。

在下面的代码中，我使用 r 和 c 作为行/列索引以及 i 和 j 而不是表示边界上的点...例如对于单元格 (r=3, c=2) 架构是:

其中红墙对应位 0x02，绿墙对应位 0x01。 walls 矩阵比原始数据矩阵少了一行和一列，因为它假设最后一行或最后一列没有墙。

result = []
for r in range(rows-1):
    for c in range(cols-1):
        if walls[r][c] & 1:
            i, j = r+1, c
            cycle = [(i, j)]
            while True:
                if i < rows-1 and walls[i][j-1] & 2:
                    ii, jj = i+1, j
                    walls[i][j-1] -= 2
                elif i > 0 and walls[i-1][j-1] & 2:
                    ii, jj = i-1, j
                    walls[i-1][j-1] -= 2
                elif j < cols-1 and walls[i-1][j] & 1:
                    ii, jj = i, j+1
                    walls[i-1][j] -= 1
                elif j > 0 and walls[i-1][j-1] & 1:
                    ii, jj = i, j-1
                    walls[i-1][j-1] -= 1
                else:
                    break
                i, j = ii, jj
                cycle.append((ii, jj))
            result.append(cycle)

基本上，代码从边界上的一个点开始，并检查它是否可以在墙上向上、向下、向左或向右移动。当它不能再移动时，一个循环就完成了，可以添加到最终结果中。

该算法的复杂度为 O(rows*cols)，即它与输入大小成正比，并且是最优的(在大 O 意义上)，因为至少不读取输入就无法计算结果。这很容易看出，因为 while 主体的输入次数不能超过 map 中墙的总数(每次迭代都会移除一堵墙)。

编辑

可以修改该算法以仅生成简单循环作为输出(即，每个顶点仅被访问一次的路径)。

result = []
index = [[-1] * cols for x in range(rows)]
for r in range(rows-1):
    for c in range(cols-1):
        if walls[r][c] & 1:
            i, j = r+1, c
            cycle = [(i, j)]
            index[i][j] = 0
            while True:
                if i > 0 and walls[i-1][j-1] & 2:
                    ii, jj = i-1, j
                    walls[i-1][j-1] -= 2
                elif j > 0 and walls[i-1][j-1] & 1:
                    ii, jj = i, j-1
                    walls[i-1][j-1] -= 1
                elif i < rows-1 and walls[i][j-1] & 2:
                    ii, jj = i+1, j
                    walls[i][j-1] -= 2
                elif j < cols-1 and walls[i-1][j] & 1:
                    ii, jj = i, j+1
                    walls[i-1][j] -= 1
                else:
                    break
                i, j = ii, jj
                cycle.append((ii, jj))
                ix = index[i][j]
                if ix >= 0:
                    # closed a loop
                    result.append(cycle[ix:])
                    for i_, j_ in cycle[ix:]:
                        index[i_][j_] = -1
                    cycle = cycle[:ix+1]
                index[i][j] = len(cycle)-1

这是通过在处理过程中遇到两次相同的顶点后向输出添加一个单独的循环来实现的(index 表存储给定的 i,j 点当前正在构建的周期中从 0 开始的索引)。