从一个点的矩阵上的螺旋环

Question

我有一个2D网格,并希望从X,Y开始,并保存窗口的角(W)和(OP)的重叠.我已经尝试过这些代码,但不适用于我的目的.

如图所示,我想从一个随机点(黑色单元格)开始,并在螺旋循环中保存每个新窗口的角落位置(由黑色圆圈表示).该算法应该用于任何网格尺寸(不一定是方形)和任何起点位置.

Matlab也有一个类似于我想要的功能(螺旋),但它不需要网格,窗口大小和重叠(OP).

我希望这个数字有以下输出:(8,12)(11,12)(11,9)(8,9)(4,9)(4,12)(4,15)......

我使用以下代码从角落开始并使用定义的W,OP和Matrix大小逐步填充矩阵:

W = [10 12];
OP = [4 3];

M = zeros(100,110);

for i=[1:W(1)-OP(1):size(M,1)-W(1), size(M,1)-W(1)+1]
  for j=[1:W(2)-OP(2):size(M,2)-W(2), size(M,2)-W(2)+1]
      block = rand(W(1),W(2));
      M(i:i+W(1)-1, j:j+W(2)-1) = block;
      imagesc(M); axis equal tight xy
      pause(.1)
  end;
end;

因此,以更清晰的方式,我应该如何更改"上方"代码以便从位置(x,y)开始并根据W,OP和大小(M)螺旋地填充整个矩阵.

谢谢!

Answer 1

基本问题

将数据定义为:

step = 3;  %// step size
x0 = 8;    %// x coordinate of origin
y0 = 12;   %// y coordinate of origin
N = 32;    %// number of steps

然后螺旋的坐标可以作为复平面中的值获得如下^†:

z = x0+1j*y0 + step*cumsum([0 -1j.^(-floor(sqrt(4*(0:N)+1))-1)]);

当然,然后是x和y坐标

x = real(z);
y = imag(z);

使用上面给出的示例值,plot(z,'o-')(或plot(x,y,'o-'))生成图形

^{†关键是要生成1,2,3,3,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,8...我感谢OEIS 解决该部分的序列.序列结果是4n + 1平方根的整数部分,n = 1,2,3,...}

如何包含重叠和窗口大小

考虑到重叠,遵循丹尼尔的建议,从中减去它的价值step.

要考虑窗口大小,N应该足够大,以便螺旋到达窗口边界以外的某个点; 然后只保留前面的几点.

由于很难预先计算出N应该有多大,因此一种可能的方法是 在循环中指数增加N,直到它足够大.指数增加确保循环迭代的数量将很小.下面的代码使用2的幂N.

%// Data
step = 3;     %// step size
overlap = 1;  %// overlap
x0 = 20;      %// x coordinate of origin
y0 = 15;      %// y coordinate of origin
xmin = 0;     %// window boundary: min x
xmax = 40;    %// window boundary: max x
ymax = 30;    %// window boundary: min y
ymin = 0;     %// window boundary: max y

%// Computations
stepov = step-overlap;
N = 8; %// Initial value. Will be increased as needed
done = false;
while ~done
    z = x0+1j*y0 + stepov*cumsum([0 -1j.^(-floor(sqrt(4*(0:N)+1))-1)]);
        %// compute coordinates of N points
    ind = find(real(z)<xmin | real(z)>xmax | imag(z)<ymin | imag(z)>ymax, 1);
        %// find index of first z out of boundary, if any
    done = ~isempty(ind); %// exit if we have reached outside window boundary
    N = N*2; %// increase number of steps for next try
end
z = z(1:ind-1); %// only keep values that are within the boundary
x = real(z);
y = imag(z);

利用代码中指示的数据,获得的图如下.请注意,最后一点是(38,0).下一个点是(38,-2),它位于窗口边界之外.

Answer 2

这是一段产生预期输出的代码。只需对spiral_generic进行少量更改即可满足您的要求：

function demo()
spiral_generic([10,11],[3,4])
W = [10 12];
OP = [4 3];
%make sure your start point is really on the grid of r and c, this is not checked!
start = [19,28];
M = zeros(100,110);
r=[1:W(1)-OP(1):size(M,1)-W(1), size(M,1)-W(1)+1];
c=[1:W(2)-OP(2):size(M,2)-W(2), size(M,2)-W(2)+1];
startindex=[find(r==start(1),1,'first'),find(c==start(2),1,'first')];
A=spiral_generic([numel(r),numel(c)],startindex);
[~,idx]=sort(A(:));
[ridx,cidx]=ind2sub(size(A),idx);
%blocks contains the lower left corners in order of processing.
blocks=[r(ridx);c(cidx)];
for blockindex=blocks
       block = rand(W(1),W(2));
       M(blockindex(1):blockindex(1)+W(1)-1, blockindex(2):blockindex(2)+W(2)-1) = block;
       imagesc(M);
       pause(.1)
end

end
function A = spiral_generic(n, P)
% Makes NxN matrix filled up spirally starting with point P
  r = max([P - 1, n - P]);              % Radius of the bigger matrix
  M = spiral(2 * r + 1);                % Bigger matrix itself
  M = permute(M,[2,1]);                 % changing start direction of the spiral
  M = M(:,end:-1:1);                    % chaning spin orientation
  C = r + 1 - (P - 1);                  % Top-left corner of A in M
  A = M(C(1):C(1)+n(1)-1, C(2):C(2)+n(2)-1);  % Get the submatrix
  [~, order] = sort(A(:));              % Get elements' order
  A(order) = 1:(n(1)*n(2));                     % Fill with continous values
end