以菱形图案从中心向外遍历(2n + 1)(2n + 1)阵列? [英] Traverse (2n+1)(2n+1) Array from centre out in diamond pattern?

问题描述

1我如何从中心向外遍历一个数组，只访问每个单元一次?

1How would I traverse an array from the centre outwards, visiting each cell only once?

我可以通过找到未访问的邻居来进行广度优先遍历，但是如何进行某种编辑距离遍历呢?我一直试图在纸上弄清楚，但不能把我的头缠在它上面.

I can do it with a breadthfirst traversal by finding unvisited neighbours, but how could I do it with some kind of edit-distance traversal? I've been trying to figure it out on paper, but can't wrap my head around it.

例如，在数组中

[
[5 6 8 9 0]
[1 2 4 5 6]
[5 4 0 2 1]
[1 2 3 4 5]
[1 2 3 4 5]]

从中心的零开始，我们将访问[1][2]处的4，然后访问[2][3]处的2，然后访问[3][2]处的3，然后访问[2][1]处的4，然后访问[0][2]处的8 [1][3]等处的

starting from the zero in the centre, we would visit the 4 at [1][2] then the 2 at [2][3] then the 3 at [3][2] then the 4 at [2][1] then the 8 at [0][2]and then the 5 at the [1][3] etc etc

我已经尝试过了，但是已经很接近了，但是错过了一些.

I've tried this, which gets close, but misses some.

def traversalOrder(n): #n is size of array (always square)

    n = n/2
    t = []
    for k in range(1,n+1):
        t += [(i,j) for i in range(n-k,n+k+1) for j in range(n-k,n+k+1) if (i,j) not in t and (i-j == k or j-i == k)  ]

推荐答案

我有一个开源库 pixelscan 在网格上进行这种空间模式遍历.该库提供了各种扫描功能和坐标转换.例如，

I have an open source library pixelscan that does this sort of spatial pattern traversal on a grid. The library provides various scan functions and coordinate transformations. For example,

x0, y0, r1, r2 = 0, 0, 0, 2
for x, y in ringscan(x0, y0, r1, r2, metric=manhattan):
    print x, y

其中

x0     = Circle x center
y0     = Circle y center
r1     = Initial radius
r2     = Final radius
metric = Distance metric

在钻石中产生以下几点:

produces the following points in a diamond:

(0,0) (0,1) (1,0) (0,-1) (-1,0) (0,2) (1,1) (2,0) (1,-1) (0,-2) (-1,-1) (-2,0) (-1,1)

您可以应用翻译，以从所需的任何中心点开始.

You can apply a translation to start at any center point you want.

这篇关于以菱形图案从中心向外遍历(2n + 1)(2n + 1)阵列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！