Are there any known algorithms for identifying the coordinates of the nearest neighbours of a 2D square lattice?

I'm looking for a code that takes these inputs: (i) 2D lattice in x,y coordinates (ii) coordinate of interest (iii) integer n, and outputs the coordinates of the n-th nearest neighbours.

For example:

• Input (i) some arbitrary lattice (ii) (0,0) as coordinate of interest (iii) 2 - for next nearest neighbours.
• Output (-1,0), (0,1), (1,0), (0,-1) for nearest neighbours, (-1,1), (1,1), (1,-1), (-1,-1) for next nearest neighbours.

If there is no code around, I will write one up.

Thanks a bunch!

Answer 1

[Guillaume]

Assuming the lattice is not too huge, can't you just calculate the distance from your point to every lattice point, sort the distances and pick the nth first points (watching out for equality)? E.g.:

lattice = [];
[lattice(:, :, 1), lattice(:, :, 2)] = ndgrid(-10:10);  
lattice = reshape(lattice, [], 2) %demo lattice as Nx2 matrix, each row is a lattice point
querypoint = [0 0]
neighbours = 2 

distances = hypot(querypoint(:, 1) - lattice(:, 1), querypoint(:, 2) - lattice(:, 2));
[d, ~, order] = unique(distances);  %sort the distance and get unique id for each distance
rows = (1:numel(order)).';
if d(1) == 0
   %point on lattice coincide with query point, remove from result
   order = order - 1;
   rows(order == 0) = [];
   order(order == 0) = [];
end
result = accumarray(order(order <= neighbours), rows(order <= neighbours), [],@(v) {lattice(v, :)});
celldisp(result)

[Matt]

Sweet! Thank you very much!

Answer 2

[KSSV]

Read about knnsearch and rangesearch.

[Matt]

Hey!

Thanks for your input!

I did think about knnsearch or rangesearch but I'm not too sure how to apply it to my case.

Maybe I will elaborate.

M = [1 2 3 4; 5 6 7 8; 9 10 11 12; 13 14 15 16];
% Let M = 6 be the target.
% How do I obtain the coordinates for the first and second nearest neighbours to M = 6?
% First nearest neighbours are where M = 2, 5, 7, 10
% Second nearest neighbours are where M = 1, 3, 9, 11

It's something like nearest neighbours and next-nearest neighbours in a square lattice of a 2D Ising model.

Am I making sense? :\

Thanks a lot!