为绘图排序多边形的点

Question

我有一个矩阵(0表示什么都没有,1表示地形)代表我游戏中的一个级别.矩阵对应于我的屏幕被分解成的网格,并指示我的地形去向何处.

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

为了绘制这个多边形,我需要点以某种顺序(顺时针或逆时针),使得每个点后面跟着它的相邻点.显然,第一点和最后一点必须是邻居.由于这都在网格中,我知道相邻点之间的确切距离.

问题是我在提出一种算法时遇到麻烦,这种算法允许我在多边形的边缘"行走",同时按顺序排列点.我相信应该有一种方法来利用我有矩阵表示几何的事实,这意味着只有一种可能的方法来绘制多边形(即使它是凹的).

我已经尝试了几种使用贪婪算法的方法,但似乎找不到一种方法可以知道,在每种情况下,我想要进入哪个方向.鉴于任何特定点可以有多达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

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

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

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

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 的函数中来解决。

要构建边界列表，您只需从墙上的任何点开始并移动后面的墙，在处理它们时从地图上删除这些墙。当您无法再移动时，循环已完成（保证您完成循环，因为在以这种方式从内部/外部标志矩阵构建的图中，保证所有顶点的度数都是偶数）。

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

在下面的代码中，我使用randc作为行/列索引，并且i使用 andj来表示边界上的点...例如，对于单元格，(r=3, c=2)架构是：

其中红墙对应 bit 0x02，绿墙对应 bit 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 的主体输入的次数不能多于地图中墙的总数（在每次迭代时都会删除一堵墙）。

编辑

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

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 的索引）。