Вот ответ Джулии: мой подход заключается в назначении точек в концентрических квадратах («спиралях») вокруг начала координат (0,0), где каждый квадрат имеет длину стороны m = 2n + 1, для создания упорядоченного словаря с номерами местоположений ( начиная с 1 для начала координат) в качестве ключей и соответствующей координаты в качестве значения.
Поскольку максимальное положение на спираль составляет (n,-n), остальные точки можно найти, просто работая в обратном направлении от этой точки, то есть от нижнего правого угла на m-1 единиц, а затем повторяя для перпендикулярных 3 сегментов m-1 единиц.
Этот процесс записан в обратном порядке ниже, в соответствии с тем, как протекает спираль, а не с процессом обратного счета, то есть сегмент ra [вправо по возрастанию] уменьшается на 3(m+1), затем la [слева по возрастанию] 2(m+1) и т. д. - надеюсь, это само за себя.
import DataStructures: OrderedDict, merge
function spiral(loc::Int)
s = sqrt(loc-1) |> floor |> Int
if s % 2 == 0
s -= 1
end
s = (s+1)/2 |> Int
return s
end
function perimeter(n::Int)
n > 0 || return OrderedDict([1,[0,0]])
m = 2n + 1 # width/height of the spiral [square] indexed by n
# loc_max = m^2
# loc_min = (2n-1)^2 + 1
ra = [[m^2-(y+3m-3), [n,n-y]] for y in (m-2):-1:0]
la = [[m^2-(y+2m-2), [y-n,n]] for y in (m-2):-1:0]
ld = [[m^2-(y+m-1), [-n,y-n]] for y in (m-2):-1:0]
rd = [[m^2-y, [n-y,-n]] for y in (m-2):-1:0]
return OrderedDict(vcat(ra,la,ld,rd))
end
function walk(n)
cds = OrderedDict(1 => [0,0])
n > 0 || return cds
for i in 1:n
cds = merge(cds, perimeter(i))
end
return cds
end
Итак, для вашего первого примера, добавление m = 3 в уравнение для поиска n дает n = (5-1)/2 = 2, а walk(2) дает упорядоченный словарь местоположений для координат, который вы можете превратить в просто массив координат, открыв поле vals словаря:
walk(2)
DataStructures.OrderedDict{Any,Any} with 25 entries:
1 => [0,0]
2 => [1,0]
3 => [1,1]
4 => [0,1]
⋮ => ⋮
[(co[1],co[2]) for co in walk(2).vals]
25-element Array{Tuple{Int64,Int64},1}:
(0,0)
(1,0)
⋮
(1,-2)
(2,-2)
Обратите внимание, что для некоторых функций [например, norm] может быть предпочтительнее оставить координаты в массивах, а не Tuple{Int,Int}, но здесь я изменяю их на кортежи - (x,y) - по запросу, используя понимание списка.
Контекст для «поддержки» неквадратной матрицы не указан (обратите внимание, что это решение по-прежнему рассчитывает значения вне сетки), но если вы хотите отфильтровать только диапазон x по y ( здесь для x=5, y=3) после расчета полной спирали, затем intersect эта матрица против значений из walk.
grid = [[x,y] for x in -2:2, y in -1:1]
5×3 Array{Array{Int64,1},2}:
[-2,-1] [-2,0] [-2,1]
⋮ ⋮ ⋮
[2,-1] [2,0] [2,1]
[(co[1],co[2]) for co in intersect(walk(2).vals, grid)]
15-element Array{Tuple{Int64,Int64},1}:
(0,0)
(1,0)
⋮
(-2,0)
(-2,-1)