Spiral loop on a matrix from a point

Question

I have a 2D grid as follow and want to start from X, Y and save the corner of a window (W) and overlap of (OP). I have tried these codes, but non of them are fit to my purpose.

As it is demonstrated, I want to start from a random point (black cell) and save the corner locations (shown by black circles) of each new window in a spiral loop. The algorithm should be used for any grid sizes (not square necessarily) and any start point locations.

Matlab also has a function (spiral) that is similar to what I want, but it does not take a grid, window size and overlap (OP).

I expect to have the following output for this figure: (8,12) (11,12) (11,9) (8,9) (4,9) (4,12) (4,15) ...

I am using the following codes which starts from a corner and fill the matrix step-by-step using the defined W, OP and Matrix size:

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;

So, in a more clear way, how should I change the "above" code in order to start from a location(x,y) and spirally fill the whole matrix according to W, OP and size(M).

Thanks!

Answer 1

The basic problem

Let the data be defined as:

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

Then the coordinates of the spiral can be obtained as values in the complex plane as follows^†:

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

Of course, the x and y coordinates are then

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

With the example values given above, plot(z,'o-') (or plot(x,y,'o-')) produces the graph

^{† The key was to generate the sequence 1,2,3,3,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,8... I'm indebted to OEIS for solving that part. The sequence turns out to be the integer part of the square root of 4n+1, for n=1,2,3,...}

How to include overlap and window size

To take into account overlap, following Daniel's suggestion, subtract its value from step.

To consider window size, N should be large enough so that the spiral reaches some point out of the window boundary; and then only the preceding points would be kept.

Since it's difficult to compute in advance how large N should be, one possible approach is to exponentially increase N in a loop until it is large enough. The exponential increase assures that the number of loop iterations will be small. The code below uses powers of 2 for 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);

With the data indicated in the code, the obtained graph is as follows. Note that the last point is (38,0). The next point would be (38,-2), which is outside the window boundary.

Answer 2

Here is a piece of code which produces the expected output. There where only minor changes to the spiral_generic necessary to match your requirements:

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