每个像素的距离图（Python实现）

Question

每个像素的距离图（Python实现）

3

我需要在Python中实现一个距离地图，关于二进制的迷宫（1表示墙壁，0表示空旷区域），我想要从迷宫中的某个点开始实现一个距离地图。距离地图不应穿过墙壁。

我有一个numpy格式的迷宫，如下图所示，希望距离地图可以从蓝色区域向外扩展。 The binary map that I have 我认为距离地图应该从蓝色区域向外递进，并给迷宫中的每个体素赋一个代表最短距离的值。让您有一个想法，我认为距离地图应该按照这种方式演化有人知道如何实现这个或者有代码示例吗？

感谢您的帮助！

我通过以下WeTransfer链接上传了numpy数组：https://wetransfer.com/downloads/63800d0f06667fa7644a4a5d1a68fc5a20200121121741/744d2c 我使用的起点是（56，104）

- VincentWin

2个回答

0

你可以使用以下算法来完成这个任务：

将所有距离设置为一个大数字，例如9e99，除了起始点（显然距离为0）。
循环遍历所有单元格，每个单元格的值为相邻单元格（除墙外）中 i+1 的最小值。
重复步骤2，直到没有数值改变为止。

一种稍微复杂但更快的方法是做同样的事情，但只循环遍历在前一次迭代中更新过的相邻单元格。

例如，我的迷宫：

0, 0, 0
0, 1, 0
0, 1, 0

这里的1代表墙壁，0代表非墙壁。左上角是我的起点。距离如下：

 0, 9e9, 9e9
9e9, 9e9, 9e9
9e9, 9e9, 9e9

迭代：

 0,   1, 9e9
 1, 9e9, 9e9
9e9, 9e9, 9e9

 0,   1, 2
 1, 9e9, 9e9
 2, 9e9, 9e9

 0,   1, 2
 1, 9e9, 3
 2, 9e9, 9e9

 0,   1, 2
 1, 9e9, 3
 2, 9e9, 4

 0,   1, 2
 1, 9e9, 3
 2, 9e9, 4

停止

- Nathan

代码的时间复杂度为 O(n^2*m)，其中 n 表示迷宫的大小，m 表示步数。另外，你可以使用 float('inf') 代替任意大的数字。 - BlueSheepToken

@BlueSheepToken 我会将其写成O(n^1.5)（n为像素总数）。如果您实现稍微复杂一些的版本，它将变成O(n)。 - Nathan

听起来不错！但是我该如何实现停止条件？而且，如何实现对角线距离的长度值为sqrt(2)？ - VincentWin

@Nathan 为什么步数是 n^0.5？顺便说一下，感谢添加了一个图表！ - BlueSheepToken

1

这是一个正方形，因此从一个角到另一个角的距离为2 * n^0.5（如果没有循环），向左n^0.5并向下n^0.5（如果是正方形），显然有最坏情况，但这将相当准确。 - Nathan

显示剩余3条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- BlueSheepToken · Accepted Answer

您可以使用像propaging这样的前端：

import matplotlib.pyplot as plt


def cond(x, y, max_x, max_y, maze):
    return 0 <= x < max_x and 0 <= y < max_y and maze[y][x] == 0

def neighbours(point, maze):
    max_x = len(maze[0])
    max_y = len(maze)
    x = point[0]
    y = point[1]

    list_neighbours = [(i, y) for i in (x - 1, x + 1) if cond(i, y, max_x, max_y, maze)] \
                      + [(x, j) for j in (y - 1, y + 1) if cond(x, j, max_x, max_y, maze)]

    return list_neighbours


maze = [
    [0, 0, 1, 1],
    [0, 1, 1, 0],
    [0, 0, 0, 0],
    [0, 0, 1, 0]
]

start = (0, 0)
maze_copy = [[-1] * len(maze[0]) for _ in range(len(maze))]

front = [(0, 0)]
step = 0
while front:
    new_front = []
    for point in front:
        new_front += [p for p in neighbours(point, maze) if maze_copy[p[1]][p[0]] == -1]
        maze_copy[point[1]][point[0]] = step

    step += 1
    front = list(set(new_front))

print(maze_copy)
plt.imshow(maze_copy, cmap='hot', interpolation='nearest')
plt.show()

在代码中，1 表示墙壁，0 表示可以通过的部分。我复制了迷宫，以跟踪已经访问过的像素。

这个想法是有一个前沿区域，将会传播并填充 maze_copy。

这将导致以下填充结果：

[0, -1, -1, -1]
[-1, -1, -1, -1]
[-1, -1, -1, -1]
[-1, -1, -1, -1]

[0, 1, -1, -1]
[1, -1, -1, -1]
[-1, -1, -1, -1]
[-1, -1, -1, -1]

[0, 1, -1, -1]
[1, -1, -1, -1]
[2, -1, -1, -1]
[-1, -1, -1, -1]

[0, 1, -1, -1]
[1, -1, -1, -1]
[2, 3, -1, -1]
[3, -1, -1, -1]

[0, 1, -1, -1]
[1, -1, -1, -1]
[2, 3, 4, -1]
[3, 4, -1, -1]

[0, 1, -1, -1]
[1, -1, -1, -1]
[2, 3, 4, 5]
[3, 4, -1, -1]

[0, 1, -1, -1]
[1, -1, -1, 6]
[2, 3, 4, 5]
[3, 4, -1, 6]