代码之家 › 专栏 › 技术社区 › Justin L.

从原点迭代离散二维网格上向外螺旋的算法

iteration recursion language-agnostic algorithm

Justin L. · 技术社区 · 16 年前

例如,这里是预期螺旋的形状(以及迭代的每个步骤)

          y
          |
          |
   16 15 14 13 12
   17  4  3  2 11
-- 18  5  0  1 10 --- x
   19  6  7  8  9
   20 21 22 23 24
          |
          |

其中直线是x和y轴。

[0,0],
[1,0], [1,1], [0,1], [-1,1], [-1,0], [-1,-1], [0,-1], [1,-1],
[2,-1], [2,0], [2,1], [2,2], [1,2], [0,2], [-1,2], [-2,2], [-2,1], [-2,0]..

等。

我甚至不知道从哪里开始,除了一些杂乱的、不雅的和特别的东西,比如为每一层创建/编码一个新的螺旋。

另外,有没有一种方法可以很容易地在顺时针和逆时针(方向)之间切换,以及从哪个方向“开始”螺旋?(旋转)

我的申请

我有一个充满数据点的稀疏网格,我想向网格中添加一个新的数据点,并使它“尽可能接近”给定的其他点。

grid.find_closest_available_point_to(point) ,它将在上面给出的螺旋上迭代,并返回第一个空且可用的位置。

point+[0,0] (为了完整起见)。然后它会检查的 point+[1,0] . 然后它会检查的 point+[1,1] . 那么 point+[0,1] ,并返回网格中位置为空(或尚未被数据点占用)的第一个位置。

网格大小没有上限。

11 回复 | 直到 16 年前

Nikita Rybak 16 年前

直接、“临时”解决方案没有错。它也可以足够干净。

编辑

   ... 11 10
7 7 7 7 6 10
8 3 3 2 6 10
8 4 . 1 6 10
8 4 5 5 5 10
8 9 9 9 9  9

    // (di, dj) is a vector - direction in which we move right now
    int di = 1;
    int dj = 0;
    // length of current segment
    int segment_length = 1;

    // current position (i, j) and how much of current segment we passed
    int i = 0;
    int j = 0;
    int segment_passed = 0;
    for (int k = 0; k < NUMBER_OF_POINTS; ++k) {
        // make a step, add 'direction' vector (di, dj) to current position (i, j)
        i += di;
        j += dj;
        ++segment_passed;
        System.out.println(i + " " + j);

        if (segment_passed == segment_length) {
            // done with current segment
            segment_passed = 0;

            // 'rotate' directions
            int buffer = di;
            di = -dj;
            dj = buffer;

            // increase segment length if necessary
            if (dj == 0) {
                ++segment_length;
            }
        }
    }

若要更改原始方向,请查看的原始值 di dj . 若要将旋转切换为顺时针方向,请参见如何修改这些值。

mako 11 年前

这里是C++中的一个STATION,一个状态迭代器。

class SpiralOut{
protected:
    unsigned layer;
    unsigned leg;
public:
    int x, y; //read these as output from next, do not modify.
    SpiralOut():layer(1),leg(0),x(0),y(0){}
    void goNext(){
        switch(leg){
        case 0: ++x; if(x  == layer)  ++leg;                break;
        case 1: ++y; if(y  == layer)  ++leg;                break;
        case 2: --x; if(-x == layer)  ++leg;                break;
        case 3: --y; if(-y == layer){ leg = 0; ++layer; }   break;
        }
    }
};

应该是最有效率的。

Community Mohan Dere 9 年前

这是基于上的答案的javascript解决方案 Looping in a spiral

var x = 0,
    y = 0,
    delta = [0, -1],
    // spiral width
    width = 6,
    // spiral height
    height = 6;


for (i = Math.pow(Math.max(width, height), 2); i>0; i--) {
    if ((-width/2 < x && x <= width/2) 
            && (-height/2 < y && y <= height/2)) {
        console.debug('POINT', x, y);
    }

    if (x === y 
            || (x < 0 && x === -y) 
            || (x > 0 && x === 1-y)){
        // change direction
        delta = [-delta[1], delta[0]]            
    }

    x += delta[0];
    y += delta[1];        
}

http://jsfiddle.net/N9gEC/18/

Agnius Vasiliauskas 16 年前

 x,y   |  dx,dy  | k-th corner | N | Sign |
___________________________________________
1,0    |  1,0    | 1           | 1 |  +
1,1    |  0,1    | 2           | 1 |  +
-1,1   |  -2,0   | 3           | 2 |  -
-1,-1  |  0,-2   | 4           | 2 |  -
2,-1   |  3,0    | 5           | 3 |  +
2,2    |  0,3    | 6           | 3 |  +
-2,2   |  -4,0   | 7           | 4 |  -
-2,-2  |  0,-4   | 8           | 4 |  -

N = INT((1+k)/2)
Sign = | +1 when N is Odd
       | -1 when N is Even
[dx,dy] = | [N*Sign,0]  when k is Odd
          | [0,N*Sign]  when k is Even
[X(k),Y(k)] = [X(k-1)+dx,Y(k-1)+dy]

现在,当你知道了k和k+1螺旋角的坐标后,你可以通过简单地在最后一个点的x或y上加1或-1得到k和k+1之间的所有数据点。就这样。

祝你好运。

Alberto Santini 16 年前

我会用数学来解决它。下面是Ruby代码(带有输入和输出):

(0..($*.pop.to_i)).each do |i|
    j = Math.sqrt(i).round
    k = (j ** 2 - i).abs - j
    p = [k, -k].map {|l| (l + j ** 2 - i - (j % 2)) * 0.5 * (-1) ** j}.map(&:to_i)
    puts "p => #{p[0]}, #{p[1]}"
end

$ ruby spiral.rb 10
p => 0, 0
p => 1, 0
p => 1, 1
p => 0, 1
p => -1, 1
p => -1, 0
p => -1, -1
p => 0, -1
p => 1, -1
p => 2, -1
p => 2, 0

和高尔夫版本:

p (0..$*.pop.to_i).map{|i|j=Math.sqrt(i).round;k=(j**2-i).abs-j;[k,-k].map{|l|(l+j**2-i-j%2)*0.5*(-1)**j}.map(&:to_i)}

编辑

注意飞机的第一条对角线 x = y . k 告诉您在触摸它之前必须走多少步:负值意味着您必须移动 abs(k) 垂直移动,而正向移动意味着你必须移动 k 水平移动。

现在关注当前所在线段的长度(当线段的倾斜度发生变化时,螺旋的顶点被视为“下一个”线段的一部分)。它是 0 那么,第一次 1 对于接下来的两段(=2点),则 2 对于接下来的两段(=4点)等,它每两段改变一次,每次该段的点数部分增加。那是什么 j 用于。

(-1)**j 只是“的简写” 1 -1 如果您正在增加“(请注意,每一步仅更改一个坐标)。同样适用于 j%2 ,只需替换 1 0 -1 1

这是一个熟悉的推理,如果你习惯了函数式编程:剩下的只是一点点简单的数学。

Asad Saeeduddin 7 年前

可以使用递归以一种相当简单的方式完成。我们只需要一些基本的2D向量数学和工具来生成和映射(可能无限)序列:

// 2D vectors
const add = ([x0, y0]) => ([x1, y1]) => [x0 + x1, y0 + y1];
const rotate = Î¸ => ([x, y]) => [
  Math.round(x * Math.cos(Î¸) - y * Math.sin(Î¸)),
  Math.round(x * Math.sin(Î¸) + y * Math.cos(Î¸))
];
// Iterables
const fromGen = g => ({ [Symbol.iterator]: g });
const range = n => [...Array(n).keys()];
const map = f => it =>
  fromGen(function*() {
    for (const v of it) {
      yield f(v);
    }
  });

现在我们可以通过生成一条平线,再加上一个旋转的(平线,再加上一个旋转的(平线,再加上一个旋转的…)来递归地表示一个螺旋:

const spiralOut = i => {
  const n = Math.floor(i / 2) + 1;
  const leg = range(n).map(x => [x, 0]);
  const transform = p => add([n, 0])(rotate(Math.PI / 2)(p));

  return fromGen(function*() {
    yield* leg;
    yield* map(transform)(spiralOut(i + 1));
  });
};

const take = n => it =>
  fromGen(function*() {
    for (let v of it) {
      if (--n < 0) break;
      yield v;
    }
  });
const points = [...take(5)(spiralOut(0))];
console.log(points);
// => [[0,0],[1,0],[1,1],[0,1],[-1,1]]

也可以取消旋转角度以转到另一个方向,或者使用变换和腿部长度来获得更复杂的形状。

const empty = [];
const append = it1 => it2 =>
  fromGen(function*() {
    yield* it1;
    yield* it2;
  });
const spiralIn = ([w, h]) => {
  const leg = range(w).map(x => [x, 0]);
  const transform = p => add([w - 1, 1])(rotate(Math.PI / 2)(p));

  return w * h === 0
    ? empty
    : append(leg)(
        fromGen(function*() {
          yield* map(transform)(spiralIn([h - 1, w]));
        })
      );
};

take 一些任意数字):

const points = [...spiralIn([3, 3])];
console.log(points);
// => [[0,0],[1,0],[2,0],[2,1],[2,2],[1,2],[0,2],[0,1],[1,1]]

如果你想玩的话,可以把整件事作为一个活片段放在一起:

// 2D vectors
const add = ([x0, y0]) => ([x1, y1]) => [x0 + x1, y0 + y1];
const rotate = Î¸ => ([x, y]) => [
  Math.round(x * Math.cos(Î¸) - y * Math.sin(Î¸)),
  Math.round(x * Math.sin(Î¸) + y * Math.cos(Î¸))
];

// Iterables
const fromGen = g => ({ [Symbol.iterator]: g });
const range = n => [...Array(n).keys()];
const map = f => it =>
  fromGen(function*() {
    for (const v of it) {
      yield f(v);
    }
  });
const take = n => it =>
  fromGen(function*() {
    for (let v of it) {
      if (--n < 0) break;
      yield v;
    }
  });
const empty = [];
const append = it1 => it2 =>
  fromGen(function*() {
    yield* it1;
    yield* it2;
  });

// Outward spiral
const spiralOut = i => {
  const n = Math.floor(i / 2) + 1;
  const leg = range(n).map(x => [x, 0]);
  const transform = p => add([n, 0])(rotate(Math.PI / 2)(p));

  return fromGen(function*() {
    yield* leg;
    yield* map(transform)(spiralOut(i + 1));
  });
};

// Test
{
  const points = [...take(5)(spiralOut(0))];
  console.log(JSON.stringify(points));
}

// Inward spiral
const spiralIn = ([w, h]) => {
  const leg = range(w).map(x => [x, 0]);
  const transform = p => add([w - 1, 1])(rotate(Math.PI / 2)(p));

  return w * h === 0
    ? empty
    : append(leg)(
        fromGen(function*() {
          yield* map(transform)(spiralIn([h - 1, w]));
        })
      );
};

// Test
{
  const points = [...spiralIn([3, 3])];
  console.log(JSON.stringify(points));
}

Seth 16 年前

尝试搜索参数方程或极坐标方程。两者都适用于绘制螺旋形的东西。 Here's a page 有很多例子,有图片(和方程式)。它应该会给你更多的想法去寻找什么。

alcuadrado 16 年前

我做的和训练练习差不多,在输出和螺旋方向上有一些不同,还有一个额外的要求,函数的空间复杂度必须是O(1)。

经过一段时间的思考,我想到了这样一个想法:通过知道螺旋从哪里开始,以及我计算值的位置,我可以通过减去螺旋的所有完整“圆”来简化问题,然后只计算一个更简单的值。

def print_spiral(n)
  (0...n).each do |y|
    (0...n).each do |x|
      printf("%02d ", get_value(x, y, n))
    end
    print "\n"
  end
end


def distance_to_border(x, y, n)
  [x, y, n - 1 - x, n - 1 - y].min
end

def get_value(x, y, n)
  dist = distance_to_border(x, y, n)
  initial = n * n - 1

  (0...dist).each do |i|
    initial -= 2 * (n - 2 * i) + 2 * (n - 2 * i - 2)
  end        

  x -= dist
  y -= dist
  n -= dist * 2

  if y == 0 then
    initial - x # If we are in the upper row
  elsif y == n - 1 then
    initial - n - (n - 2) - ((n - 1) - x) # If we are in the lower row
  elsif x == n - 1 then
    initial - n - y + 1# If we are in the right column
  else
    initial - 2 * n - (n - 2) - ((n - 1) - y - 1) # If we are in the left column
  end
end

print_spiral 5

这不完全是你要求的,但我相信它会帮助你思考你的问题

br3nt 13 年前

我也有类似的问题,但我不想每次都在整个螺旋上循环寻找下一个新的坐标。要求你知道你最后的坐标。

以下是我在大量阅读其他解决方案后得出的结论:

function getNextCoord(coord) {

    // required info
    var x     = coord.x,
        y     = coord.y,
        level = Math.max(Math.abs(x), Math.abs(y));
        delta = {x:0, y:0};

    // calculate current direction (start up)
    if (-x === level)
        delta.y = 1;    // going up
    else if (y === level)
        delta.x = 1;    // going right
    else if (x === level)        
        delta.y = -1;    // going down
    else if (-y === level)
        delta.x = -1;    // going left

    // check if we need to turn down or left
    if (x > 0 && (x === y || x === -y)) {
        // change direction (clockwise)
        delta = {x: delta.y, 
                 y: -delta.x};
    }

    // move to next coordinate
    x += delta.x;
    y += delta.y;

    return {x: x,
            y: y};
}

coord = {x: 0, y: 0}
for (i = 0; i < 40; i++) {
    console.log('['+ coord.x +', ' + coord.y + ']');
    coord = getNextCoord(coord);  

}

仍然不确定这是否是最优雅的解决方案。也许一些优雅的数学可以去掉一些if语句。有些限制是需要修改以更改螺旋方向,不考虑非方形螺旋,并且不能围绕固定坐标螺旋。

Ely Golden 11 年前

我在java中有一个算法,它可以输出与您类似的输出,只是它先对右边的数字进行优先级排序,然后对左边的数字进行优先级排序。

  public static String[] rationals(int amount){
   String[] numberList=new String[amount];
   int currentNumberLeft=0;
   int newNumberLeft=0;
   int currentNumberRight=0;
   int newNumberRight=0;
   int state=1;
   numberList[0]="("+newNumberLeft+","+newNumberRight+")";
   boolean direction=false;
 for(int count=1;count<amount;count++){
   if(direction==true&&newNumberLeft==state){direction=false;state=(state<=0?(-state)+1:-state);}
   else if(direction==false&&newNumberRight==state){direction=true;}
   if(direction){newNumberLeft=currentNumberLeft+sign(state);}else{newNumberRight=currentNumberRight+sign(state);}
   currentNumberLeft=newNumberLeft;
   currentNumberRight=newNumberRight;
   numberList[count]="("+newNumberLeft+","+newNumberRight+")";
 }
 return numberList;
}

Adi Shavit 10 年前

这是算法。它顺时针旋转,但可以很容易地逆时针旋转,有一些改变。我只用了不到一个小时。

// spiral_get_value(x,y);
sx = argument0;
sy = argument1;
a = max(sqrt(sqr(sx)),sqrt(sqr(sy)));
c = -b;
d = (b*2)+1;
us = (sy==c and sx !=c);
rs = (sx==b and sy !=c);
bs = (sy==b and sx !=b);
ls = (sx==c and sy !=b);
ra = rs*((b)*2);
ba = bs*((b)*4);
la = ls*((b)*6);
ax = (us*sx)+(bs*-sx);
ay = (rs*sy)+(ls*-sy);
add = ra+ba+la+ax+ay;
value = add+sqr(d-2)+b;
return(value);`

它将处理任何x/y值(无限)。

它是用GML(Game Maker Language)编写的,但是实际的逻辑在任何编程语言中都是合理的。

对于x和y输入,单线算法只有2个变量(sx和sy)。我基本上扩大了括号,很多。它使您更容易将其粘贴到记事本中,并将“sx”更改为x参数/变量名,“sy”更改为y参数/变量名。

`// spiral_get_value(x,y);

sx = argument0;  
sy = argument1;

value = ((((sx==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sy !=(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy))))))*((max(sqrt(sqr(sx)),sqrt(sqr(sy))))*2))+(((sy==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sx !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*((max(sqrt(sqr(sx)),sqrt(sqr(sy))))*4))+(((sx==(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy)))) and sy !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*((max(sqrt(sqr(sx)),sqrt(sqr(sy))))*6))+((((sy==(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy)))) and sx !=(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy))))))*sx)+(((sy==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sx !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*-sx))+(((sx==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sy !=(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy))))))*sy)+(((sx==(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy)))) and sy !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*-sy))+sqr(((max(sqrt(sqr(sx)),sqrt(sqr(sy)))*2)+1)-2)+max(sqrt(sqr(sx)),sqrt(sqr(sy)));

return(value);`

我知道答复太晚了,但我希望它能帮助将来的来访者。

chris 5 年前

下面是一个基于@mako的答案的Python实现。

def spiral_iterator(iteration_limit=999):
    x = 0
    y = 0
    layer = 1
    leg = 0
    iteration = 0

    yield 0, 0

    while iteration < iteration_limit:
        iteration += 1

        if leg == 0:
            x += 1
            if (x == layer):
                leg += 1
        elif leg == 1:
            y += 1
            if (y == layer):
                leg += 1
        elif leg == 2:
            x -= 1
            if -x == layer:
                leg += 1
        elif leg == 3:
            y -= 1
            if -y == layer:
                leg = 0
                layer += 1

        yield x, y

运行此代码:

for x, y in spiral_iterator(10):
       print(x, y)

产量: