27

给定一个nby nmatrix M，在 rowi和 column 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的那个点开始的半径。fTrue

如果有更有效的计算方式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")： FJ的circle_around

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

我将 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")： 镁的circle_around

如您所见，满足我正在寻找的界面的结果都没有产生一个圆形螺旋，该螺旋覆盖了 0、0 附近的所有索引。FJ 是最接近的，尽管 WolframH 的命中点正确，只是不是螺旋命令。

4

7 回答 7

13

由于提到点的顺序无关紧要，我只是按照它们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（对不起色盲）：

在此处输入图像描述

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

在此处输入图像描述

于 2012-03-06T21:04:29.867 回答
10

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

下面是该算法的（简单）实现。请注意，使用平方欧几里得距离，并且包括中心点。最重要的是，只考虑带有 x in 的点 (x, y) 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

于 2012-02-12T23:59:44.087 回答
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")

螺旋指数

从上图中可以看出，这正是所要求的。

于 2013-11-17T01:00:53.720 回答
2

这是一个基于循环的实现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)
于 2012-01-23T22:35:47.907 回答
0

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

问题：

  • 未优化以跳过数组外的点
  • 仍然使用方形迭代器，但它确实找到了最近的点
  • 我没有使用过 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
于 2012-02-12T13:07:03.513 回答
0

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

r(theta) = a + b*theta

然后将极坐标 (r,theta) 转换为 (x,y)，使用

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

cos并且sin在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
于 2012-02-13T03:52:41.900 回答
0

尽管我不完全确定您要做什么，但我会这样开始：

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

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

R，曼哈顿的距离度量是多少？欧几里得？别的东西？

于 2012-02-12T16:10:03.567 回答