Алгоритм итерации по внешней спирали на дискретной двумерной сетке от начала координат

Ответ 1

Нет ничего плохого в прямом, "ad-hoc" решении. Это тоже может быть достаточно чистым.
Просто заметите, что спираль построена из сегментов. И вы можете получить следующий сегмент от текущего, вращая его на 90 градусов. И каждые два оборота длина сегмента увеличивается на 1.

редактировать Иллюстрация, эти сегменты пронумерованы

   ... 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. Чтобы переключить вращение по часовой стрелке, посмотрите, как эти значения изменены.

Ответ 2

Вот удар по нему в С++, итераторе с сохранением состояния.

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;
        }
    }
};

Должен быть примерно такой же эффективный, как и он.

Ответ 3

Это решение javascript, основанное на ответе на Цикл в спирали

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/

Ответ 4

Эта проблема лучше всего понять, анализируя, как изменяются координаты спиральных углов. Рассмотрим эту таблицу первых 8 спиральных углов (исключая начало):

 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 |  -

При взгляде на эту таблицу мы можем вычислить X, Y k-го угла, заданного X, Y угла (k-1):

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 спирального угла, вы можете получить все точки данных между k и k + 1, просто добавив 1 или -1 к x или y последней точки. Вот оно.

удачи.

Ответ 5

Я бы решил это, используя некоторую математику. Вот код 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)}

Edit

Сначала постарайтесь подойти к проблеме функционально. Что вам нужно знать на каждом шагу, чтобы перейти к следующему шагу?

Фокусировка на первой диагонали плоскости x = y. k сообщает вам, сколько шагов вы должны предпринять, прежде чем прикасаться к нему: отрицательные значения означают, что вы должны перемещать шаги abs(k) по вертикали, в то время как положительное означает, что вы должны перемещать горизонтальные шаги k.

Теперь сосредоточьтесь на длине сегмента, в котором вы находитесь (спиральные вершины - при изменении наклона сегментов - считаются частью "следующего" сегмента). Он 0 первый раз, затем 1 для следующих двух сегментов (= 2 точки), затем 2 для следующих двух сегментов (= 4 балла) и т.д. Он меняет каждые два сегмента и каждый раз, когда число точек части этих сегментов. Для чего используется j.

Случайно, это может быть использовано для получения еще одного бита информации: (-1)**j является просто сокращением до "1, если вы уменьшаете некоторую координату, чтобы перейти к этому шагу; -1, если вы увеличиваете" (Обратите внимание, что на каждом шаге изменяется только одна координата). То же самое верно для j%2, просто замените 1 на 0 и -1 на 1 в этом случае. Это означает, что они меняются между двумя значениями: один для сегментов "заголовок" вверх или вправо, а один для тех, кто идет вниз или слева.

Это привычная аргументация, если вы привыкли к функциональному программированию: остальное - всего лишь немного простая математика.

Ответ 6

Попробуйте найти либо параметрические, либо полярные уравнения. Оба подходят для построения спиральных вещей. Здесь страница, в которой есть много примеров, с картинками (и уравнениями). Он должен дать вам еще несколько идей о том, что искать.

Ответ 7

Я сделал почти то же самое, что и тренировочное упражнение, с некоторыми различиями в выходе и спиральной ориентации, и с дополнительным требованием, чтобы пространственная сложность функций была O (1).

Подумав какое-то время, я пришел к мысли, что, зная, где начинается спираль, и о позиции, которую я вычислял, я мог бы упростить задачу, вычитав все "кружки" спирали, а затем просто вычислите более простое значение.

Вот моя реализация этого алгоритма в ruby:

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

Это не совсем то, о чем вы просили, но я считаю, что это поможет вам подумать о своей проблеме.

Ответ 8

У меня была аналогичная проблема, но я не хотел каждый цикл перебирать всю спираль, чтобы найти следующую новую координату. Требование состоит в том, что вы знаете свою последнюю координату.

Вот что я придумал с большим количеством чтения на других решениях:

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. Некоторым ограничениям потребуется некоторая модификация для изменения спирального направления, не учитывает неквадратичные спирали и не может вращаться вокруг фиксированной координаты.

Ответ 9

Вот алгоритм. Он вращается по часовой стрелке, но может легко вращаться против часовой стрелки, с небольшими изменениями. Я сделал это через час.

// 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), но фактическая логика звучит на любом языке программирования.

В однолинейном алгоритме имеется только 2 переменные (sx и sy) для входов x и y. Я в основном расширил скобки, много. Это облегчает вам вставлять его в блокнот и изменять "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);`

Я знаю, что ответ ужасно опаздывает: D, но я надеюсь, что это поможет будущим посетителям.

Ответ 10

У меня есть алгоритм в 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;
}