Алгоритм итерации по внешней спирали на дискретной двумерной сетке от начала координат
Например, вот форма предполагаемой спирали (и каждый шаг итерации)
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]и т. д. И вернуть первый, для которого позиция в сетке пуста (или уже не занята точкой данных).
Нет верхней границы для размера сетки.
13 ответов
Нет ничего плохого в прямом, "специальном" решении. Это может быть достаточно чистым тоже.
Просто обратите внимание, что спираль построена из сегментов. И вы можете получить следующий сегмент из текущего, повернув его на 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, Чтобы переключить вращение по часовой стрелке, посмотрите, как эти значения изменяются.
Вот удар в C++, итератор с сохранением состояния.
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;
}
}
};
Должно быть настолько эффективным, насколько это возможно.
Это решение 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/
Я бы решил это с помощью математики. Вот код 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 в этом случае. Это означает, что они меняются между двумя значениями: одно для сегментов, "движущихся" вверх или вправо, и одно для тех, которые идут вниз или влево.
Это привычное рассуждение, если вы привыкли к функциональному программированию: все остальное - просто небольшая математика.
Эту проблему лучше всего понять, анализируя, как меняются координаты спиральных углов. Рассмотрите эту таблицу первых 8 спиральных углов (исключая происхождение):
х, у | DX, DY | k-й угол | N | Вход | ___________________________________________ 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)
Знак = | +1, когда N нечетно
| -1 когда N четное
[dx,dy] = | [N*Sign,0], когда k нечетно
| [0,N* Знак], когда k является четным
[X(k),Y(k)] = [X(k-1)+dx,Y(k-1)+dy]Теперь, когда вы знаете координаты спирального угла k и k + 1, вы можете получить все точки данных между k и k + 1, просто добавив 1 или -1 к x или y последней точки. Это оно.
удачи.
Это может быть сделано довольно простым способом с использованием рекурсии. Нам просто нужны базовые двухмерные векторные математические вычисления и инструменты для генерации и отображения последовательностей (возможно, бесконечных):
// 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));
}Вот реализация Python, основанная на ответе @mako.
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)
Урожайность:
0 0
1 0
1 1
0 1
-1 1
-1 0
-1 -1
0 -1
1 -1
2 -1
2 0
У меня есть алгоритм в 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;
}
У меня была похожая проблема, но я не хотел каждый раз перебирать всю спираль, чтобы найти следующую новую координату. Требуется, чтобы вы знали свою последнюю координату.
Вот что я придумал, читая много других решений:
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. Некоторым ограничениям потребуется некоторая модификация для изменения направления спирали, она не учитывает неквадратные спирали и не может вращаться вокруг фиксированной координаты.
Я сделал почти то же самое, что и тренировочное упражнение, с некоторыми отличиями в выходной и спиральной ориентации, и с дополнительным требованием, чтобы пространственная сложность функций была 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
Это не совсем то, о чем вы просили, но я верю, что это поможет вам подумать о вашей проблеме
Вот алгоритм. Он вращается по часовой стрелке, но может легко вращаться против часовой стрелки, с некоторыми изменениями. Я сделал это всего за час.
// 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);`
Он будет обрабатывать любые значения х / у (бесконечно).
Он написан на 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, но я надеюсь, что он поможет будущим посетителям.
Вот очень простой ответ на Javascript:
let v = [0, 0]
let r = 1
let axis = 0
let delta = 1
let count = 4 * (radius + 1) * radius + 1
for (let i = 0; i < count; i++) {
console.log(v[0], v[1])
v[axis] += delta
if (Math.abs(v[axis]) == r) {
axis = axis ? 0 : 1
if (axis) delta = delta < 0 ? 1 : -1;
else if (0 < delta) r++
}
}
Обратите внимание на общее количество квадратов, вычисленное с помощьюcountвыше, учитывая так называемый радиус.
Полный пример кода
Попробуйте поискать либо параметрические, либо полярные уравнения. Оба подходят для построения спиральных вещей. Вот страница с множеством примеров с картинками (и уравнениями). Это должно дать вам больше идей о том, что искать.