python - 迭代 'spiral' 中的列表

Question

我有一个看起来像这样的图像:

我已将其转换为二维列表。以“螺旋”方式迭代此列表的最佳方法是什么，从左上角开始到中心结束。目标是读取所有非黑色像素。

Answer 1

这是我的代码，它从左上角开始按顺时针方向螺旋式前进。它很幼稚(没有利用我们知道存在螺旋)，只是打印出坐标，但我希望您可以将其修改为您需要的内容。

我检查了几种边缘情况，因为您需要确保 (0,1,2,3 mod 4) x (0,1,2,3 mod 4) 全部有效。并且需要考虑宽螺旋和方形螺旋。

def do_stuff_with(my_array, x, y):
    print("Do stuff with", x, ",", y) #obviously, you will want to return or manipulate something. But this code is just about traversing the spiral.

def spiral(my_array, width, height):
    x_left = 0
    x_right = width
    y_top = 0
    y_bottom = height
    x_c = y_c = 0
    print("Bounding box {0},{1} -> {2},{3}".format(x_left, y_top, x_right, y_bottom))
    if x_left >= x_right or y_top >= y_bottom:
        print("Invalid spiral range.")
        return
    while x_left < x_right and y_top < y_bottom:
        #print("Going right")
        for i in range(x_left, x_right):
            do_stuff_with(my_array, i, y_top)
        #print("Going down")
        for i in range(y_top + 1, y_bottom):
            do_stuff_with(my_array, x_right - 1, i)
        if y_bottom - y_top > 1: # this just prevents us from revisiting a square in, say, a 5x7 spiral
            #print("Going left")
            for i in range(x_right - 2, x_left, -1):
                do_stuff_with(my_array, i, y_bottom - 1)
        if x_right - x_left > 1: # this just prevents us from revisiting a square in, say, a 7x5 spiral
            #print("Going up")
            for i in range(y_bottom - 1, y_top + 1, -1):
                do_stuff_with(my_array, x_left, i)
        # we need to fill in the square that links an outer spiral with an inner spiral.
        if x_right - x_left > 2 and y_bottom - y_top > 4:
            do_stuff_with(my_array, x_left + 1, y_top + 2)
        x_left += 2
        x_right -= 2
        y_top += 2
        y_bottom -= 2
        print("Top/bottom overlap", y_top >= y_bottom)
        print("Left/right overlap", x_left >= x_right)

def test_spirals(xi, yi, xf, yf):
    '''an exhaustive test to make sure different rectangles/spirals work'''
    for x in range(xi, xf):
        for y in range(yi, yf):
            print(x, y, "spiral test")
            my_array = []
            for z in range(0, y):
                my_array.append([0] * x)
            spiral(my_array, x, y)

# squarish tests: it seems like the main cases are (0/1/2/3 mod 4, 0/1/2/3 mod 4) so these 16 should knock everything out
test_spirals(4, 4, 8, 8)
# rectangular tests--yes, this overlaps the above case with 5x(6/7) but we want to try all possibilities mod 4 without having too much data to read.
#test_spirals(2, 6, 6, 10)

如果您需要或想要澄清，请告诉我。

预计到达时间:如果您知道自己正在螺旋式阅读，这里有一些伪代码，但我认为这是一个很大的假设。此外，该伪代码未经测试。但想法是:向右走，直到碰到墙壁或黑色方 block ，然后向下，然后向左，然后向上。然后重复。另外，检查是否有不必要的引用引用，这些引用可能会导致您在接近末尾的最内行处循环。

def traverse_known_spiral(myary, width, length):
    do_stuff(0, 0)
    x_c = 0
    y_c = 0
    while True:
        x_c_i = x_c
        y_c_i = y_c
        while x_c < width - 1 and myary[x_c+1][y_c] == WHITE:
            do_stuff(x_c+1, y_c)
            x_c += 1
        while y_c < height - 1 and myary[x_c][y_c+1] == WHITE:
            do_stuff(x_c, y_c+1)
            y_c += 1
        if x_c_i == x_c and y_c_i == y_c: break # if we did not move right or down, then there is nothing more to do
        x_c_i = x_c
        y_c_i = y_c
        if y_c_i != y_c: # if we didn't go down, then we'd be going backwards here
            while x_c > 0 and myary[x_c-1][y_c] == WHITE:
                do_stuff(x_c-1, y_c)
                x_c -= 1
        if x_c_i != x_c: # if we didn't go right, then we'd be going backwards here
            while y_c > 0 and myary[x_c-1][y_c-1] == WHITE:
                do_stuff(x_c, y_c-1)
                y_c -= 1
        if x_c_i == x_c and y_c_i == y_c: break # if we did not move left or up, then there is nothing more to do