以扩展的圆形螺旋迭代二维数组

Question

给定一个 n by n 矩阵 M，位于行 i 和列 j，我想迭代圆形螺旋中的所有相邻值。

这样做的目的是测试某个函数 f（它取决于 M），以找到远离 (i, j) 的半径，其中 f< /code> 返回 True。因此，f 看起来像这样：

def f(x, y):
    """do stuff with x and y, and return a bool"""

并且会这样调用：

R = numpy.zeros(M.shape, dtype=numpy.int)
# for (i, j) in M
for (radius, (cx, cy)) in circle_around(i, j):
    if not f(M[i][j], M[cx][cy]):
       R[cx][cy] = radius - 1
       break

其中，circle_around 是返回圆形螺旋中索引（迭代器）的函数。因此，对于 M 中的每个点，此代码都会计算并存储从该点开始的半径，其中 f 返回 True。

如果有更有效的计算 R 的方法，我也愿意这样做。

---

更新：

感谢所有提交答案的人。我编写了一个简短的函数来绘制 circle_around 迭代器的输出，以显示它们的作用。如果您更新答案或发布新答案，则可以使用此代码来验证您的解决方案。

from matplotlib import pyplot as plt
def plot(g, name):
    plt.axis([-10, 10, -10, 10])
    ax = plt.gca()
    ax.yaxis.grid(color='gray')
    ax.xaxis.grid(color='gray')

    X, Y = [], []
    for i in xrange(100):
        (r, (x, y)) = g.next()
        X.append(x)
        Y.append(y)
        print "%d: radius %d" % (i, r)

    plt.plot(X, Y, 'r-', linewidth=2.0)
    plt.title(name)
    plt.savefig(name + ".png")

结果如下： 绘图（circle_around（0, 0），“FJ”）：

plot(circle_around(0, 0, 10), "WolframH")：

我已将 Magnesium 的建议编码如下：

def circle_around_magnesium(x, y):
    import math
    theta = 0
    dtheta = math.pi / 32.0
    a, b = (0, 1) # are there better params to use here?
    spiral = lambda theta : a + b*theta
    lastX, lastY = (x, y)
    while True:
        r = spiral(theta)
        X = r * math.cos(theta)
        Y = r * math.sin(theta)
        if round(X) != lastX or round(Y) != lastY:
            lastX, lastY = round(X), round(Y)
            yield (r, (lastX, lastY))
        theta += dtheta

plot(circle_around(0, 0, 10) ，“镁”）：

如您所见，满足我正在寻找的界面的结果都没有产生圆形螺旋它涵盖了 0, 0 周围的所有索引。FJ 是最接近的，尽管 WolframH 命中了正确的点，只是不是按螺旋顺序排列。

Answer 1

由于提到点的顺序并不重要，因此我只是按照它们在给定半径处出现的角度 (arctan2) 对它们进行排序。更改 N 以获得更多积分。

from numpy import *
N = 8

# Find the unique distances
X,Y = meshgrid(arange(N),arange(N))
G = sqrt(X**2+Y**2)
U = unique(G)

# Identify these coordinates
blocks = [[pair for pair in zip(*where(G==idx))] for idx in U if idx<N/2]

# Permute along the different orthogonal directions
directions = array([[1,1],[-1,1],[1,-1],[-1,-1]])

all_R = []
for b in blocks:
    R = set()
    for item in b:
        for x in item*directions:
            R.add(tuple(x))

    R = array(list(R))

    # Sort by angle
    T = array([arctan2(*x) for x in R])
    R = R[argsort(T)]
    all_R.append(R)

# Display the output
from pylab import *
colors = ['r','k','b','y','g']*10
for c,R in zip(colors,all_R):
    X,Y = map(list,zip(*R))

    # Connect last point
    X = X + [X[0],]
    Y = Y + [Y[0],]
    scatter(X,Y,c=c,s=150)
    plot(X,Y,color=c)

axis('equal')
show()

为 N=8 提供：

更多积分 N=16< /code> （抱歉色盲）：

这明显接近一个圆并按顺序击中每个网格点半径不断增加。

Answer 2

随着距离的增加而产生点的一种方法是将其分解为简单的部分，然后将各部分的结果合并在一起。很明显，itertools.merge 应该进行合并。 简单的部分是列，因为对于固定的x，点(x, y)可以通过仅查看y的值来排序。

下面是该算法的（简单的）实现。请注意，使用平方欧几里德距离，并且包括中心点。最重要的是，仅考虑 x 在 range(x_end) 中的点 (x, y)，但我认为这适合您的用例（其中 x_end 将是 n 在上面的符号中）。

from heapq import merge
from itertools import count

def distance_column(x0, x, y0):
    dist_x = (x - x0) ** 2
    yield dist_x, (x, y0)
    for dy in count(1):
        dist = dist_x + dy ** 2
        yield dist, (x, y0 + dy)
        yield dist, (x, y0 - dy)

def circle_around(x0, y0, end_x):
    for dist_point in merge(*(distance_column(x0, x, y0) for x in range(end_x))):
        yield dist_point

编辑：测试代码：

def show(circle):
    d = dict((p, i) for i, (dist, p) in enumerate(circle))
    max_x = max(p[0] for p in d) + 1
    max_y = max(p[1] for p in d) + 1
    return "\n".join(" ".join("%3d" % d[x, y] if (x, y) in d else "   " for x in range(max_x + 1)) for y in range(max_y + 1))

import itertools
print(show(itertools.islice(circle_around(5, 5, 11), 101)))

测试结果（点按照circle_around产生的顺序编号）：

             92  84  75  86  94                
     98  73  64  52  47  54  66  77 100        
     71  58  40  32  27  34  42  60  79        
 90  62  38  22  16  11  18  24  44  68  96    
 82  50  30  14   6   3   8  20  36  56  88    
 69  45  25   9   1   0   4  12  28  48  80    
 81  49  29  13   5   2   7  19  35  55  87    
 89  61  37  21  15  10  17  23  43  67  95    
     70  57  39  31  26  33  41  59  78        
     97  72  63  51  46  53  65  76  99        
             91  83  74  85  93                

编辑2：如果你真的这样做需要 i 为负值，请将 cirlce_around 中的 range(end_x) 替换为 range(-end_x, end_x)功能。

Answer 3

如果您遵循 x 和 y 螺旋索引，您会发现它们都可以以递归方式定义。因此，很容易想出一个递归生成正确索引的函数：

def helicalIndices(n):
    num = 0
    curr_x, dir_x, lim_x, curr_num_lim_x = 0, 1, 1, 2
    curr_y, dir_y, lim_y, curr_num_lim_y = -1, 1, 1, 3
    curr_rep_at_lim_x, up_x = 0, 1
    curr_rep_at_lim_y, up_y = 0, 1

    while num < n:
        if curr_x != lim_x:
            curr_x +=  dir_x
        else:
            curr_rep_at_lim_x += 1
            if curr_rep_at_lim_x == curr_num_lim_x - 1:
                if lim_x < 0:
                    lim_x = (-lim_x) + 1
                else:
                    lim_x = -lim_x
                curr_rep_at_lim_x = 0
                curr_num_lim_x += 1
                dir_x = -dir_x
        if curr_y != lim_y:
            curr_y = curr_y + dir_y
        else:
            curr_rep_at_lim_y += 1
            if curr_rep_at_lim_y == curr_num_lim_y - 1:
                if lim_y < 0:
                    lim_y = (-lim_y) + 1
                else:
                    lim_y = -lim_y
                curr_rep_at_lim_y = 0
                curr_num_lim_y += 1
                dir_y = -dir_y
        r = math.sqrt(curr_x*curr_x + curr_y*curr_y)        
        yield (r, (curr_x, curr_y))
        num += 1

    hi = helicalIndices(101)
    plot(hi, "helicalIndices")

正如您可以从上图，这正是所要求的。

Answer 4

以下是 circle_around() 的基于循环的实现：

def circle_around(x, y):
    r = 1
    i, j = x-1, y-1
    while True:
        while i < x+r:
            i += 1
            yield r, (i, j)
        while j < y+r:
            j += 1
            yield r, (i, j)
        while i > x-r:
            i -= 1
            yield r, (i, j)
        while j > y-r:
            j -= 1
            yield r, (i, j)
        r += 1
        j -= 1
        yield r, (i, j)

Answer 5

虽然我不完全确定你想做什么，但我会这样开始：

def xxx():
    for row in M[i-R:i+R+1]:
        for val in row[j-R:j+r+1]:
            yield val

我不确定你想要的螺旋有多少顺序，这重要吗？它必须是递增的 R 顺序吗？或者也许从特定的方位角开始顺时针？

R 曼哈顿的距离是多少？欧几里得？还有别的东西吗？

Answer 6

我要做的是使用阿基米德螺旋方程：

r(theta) = a + b*theta

然后使用

x = r*cos(theta)
y = r*sin(theta)

cos 和 sin 将极坐标 (r,theta) 转换为 (x,y)位于math 库中。然后将所得的 x 和 y 舍入为整数。您可以随后将 x 和 y 偏移起始索引，以获得数组的最终索引。

但是，如果您只是想找到 f 返回 true 的第一个半径，我认为执行以下伪代码会更有益：

for (i,j) in matrix:
    radius = sqrt( (i-i0)^2 + (j-j0)^2) // (i0,j0) is the "center" of your spiral
    radiuslist.append([radius, (i,j)])
sort(radiuslist) // sort by the first entry in each element, which is the radius
// This will give you a list of each element of the array, sorted by the
// "distance" from it to (i0,j0)
for (rad,indices) in enumerate(radiuslist):
    if f(matrix[indices]):
        // you found the first one, do whatever you want

Answer 7

好吧，我很尴尬，这是我迄今为止想到的最好的。但也许它会对你有帮助。由于它实际上不是循环迭代器，因此我必须接受您的测试函数作为参数。

问题：

• 未针对跳过数组外部的点进行优化
• 最近点
• ，仍使用方形迭代器，但它确实找到了我未使用 numpy 的 ，因此它是为列表列表而设计的。您需要更改的两点已被注释，
• 我将方形迭代器保留为长形式，以便更容易阅读。它可能会更干燥

这是代码。您问题的关键解决方案是顶层“spiral_search”函数，它在方形螺旋迭代器的顶部添加了一些额外的逻辑，以确保找到最近的点。

from math import sqrt

#constants
X = 0
Y = 1

def spiral_search(array, focus, test):
    """
    Search for the closest point to focus that satisfies test.
    test interface: test(point, focus, array)
    points structure: [x,y] (list, not tuple)
    returns tuple of best point [x,y] and the euclidean distance from focus
    """
    #stop if focus not in array
    if not _point_is_in_array(focus, array): raise IndexError("Focus must be within the array.")
    #starting closest radius and best point
    stop_radius = None
    best_point = None 
    for point in _square_spiral(array, focus):
        #cheap stop condition: when current point is outside the stop radius
        #(don't calculate outside axis where more expensive)
        if (stop_radius) and (point[Y] == 0) and (abs(point[X] - focus[X]) >= stop_radius):
            break #current best point is already as good or better so done
        #otherwise continue testing for closer solutions
        if test(point, focus, array):
            distance = _distance(focus, point)
            if (stop_radius == None) or (distance < stop_radius):
                stop_radius = distance
                best_point = point
    return best_point, stop_radius

def _square_spiral(array, focus):
    yield focus
    size = len(array) * len(array[0]) #doesn't work for numpy
    count = 1
    r_square = 0
    offset = [0,0]
    rotation = 'clockwise'
    while count < size:
        r_square += 1
        #left
        dimension = X
        direction = -1
        for point in _travel_dimension(array, focus, offset, dimension, direction, r_square):
            yield point
            count += 1
        #up
        dimension = Y
        direction = 1
        for point in _travel_dimension(array, focus, offset, dimension, direction, r_square):
            yield point
            count += 1
        #right
        dimension = X
        direction = 1
        for point in _travel_dimension(array, focus, offset, dimension, direction, r_square):
            yield point
            count += 1
        #down
        dimension = Y
        direction = -1
        for point in _travel_dimension(array, focus, offset, dimension, direction, r_square):
            yield point
            count += 1

def _travel_dimension(array, focus, offset, dimension, direction, r_square):
    for value in range(offset[dimension] + direction, direction*(1+r_square), direction):
        offset[dimension] = value
        point = _offset_to_point(offset, focus)
        if _point_is_in_array(point, array):
            yield point

def _distance(focus, point):
    x2 = (point[X] - focus[X])**2
    y2 = (point[Y] - focus[Y])**2
    return sqrt(x2 + y2)

def _offset_to_point(offset, focus):
    return [offset[X] + focus[X], offset[Y] + focus[Y]]

def _point_is_in_array(point, array):
    if (0 <= point[X] < len(array)) and (0 <= point[Y] < len(array[0])): #doesn't work for numpy
        return True
    else:
        return False