在扩展的圆形螺旋中迭代2d阵列

Question

给定一个n由n矩阵M,在行i和列j,我想遍历所有的相邻值以圆形螺旋.

这样做的目的是测试一些函数,f它取决于M,找到远离(i, j)其f返回的半径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")

以下是结果 plot(circle_around(0, 0), "F.J"):

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), "magnesium"):

正如你所看到的,满足我正在寻找的界面的结果都没有产生一个圆形螺旋,覆盖了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(抱歉为色盲):

这明显接近圆并按照半径增加的顺序击中每个网格点.

Answer 2

使距离增加的点产生的一种方法是将其分解为易于部分,然后将部分的结果合并在一起.itertools.merge应该进行合并是相当明显的.在简单的部分是列,因为固定X点(X,Y)可以通过看的只有y中的值进行排序.

下面是该算法的(简单)实现.注意,使用平方欧几里德距离,并且包括中心点.最重要的是,只有点(X,Y),在X range(x_end)被认为是,但我认为这是对你的使用情况确定(这里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替换.range(end_x)range(-end_x, end_x)cirlce_around

Answer 3

这是基于循环的实现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)