Find closest point in matlab grid

10
votes

G'day

I'm trying to program a smart way to find the closest grid points to the points along a contour.

The grid is a 2-dimensional grid, stored in x and y (which contain the x and y kilometre positions of the grid cells).

The contour is a line, made up of x and y locations, not necessarily regularly spaced.

This is shown below - the red dots are the grid, and the blue dots are the points on the contour. How do I find the indices of the red dot closest to each blue dot?

interpolate red dots closest to each blue dot

Edit - I should mention that the grid is a latitude/longitude grid, of an area fairly close to the south pole. So, the points (the red dots) are the position in metres from the south pole (using a polar stereographic representation). Since the grid is a geographic grid there is unequal grid spacing - with slightly different shaped cells (where the red dots define the vertices of the cells) due to the distortion at high latitudes. The result is that I can't just find which row/column of the x and y matrix corresponds closest to the input point coordinates - unlike a regular grid from meshgrid, the values in the rows and columns vary...

Cheers Dave

4
matlabnearest-neighbor
Your grid is very regular, but not aligned to the rectangular xy axes. Could you perhaps give us a mathematical definition of the grid points? I suspect the best way is to find the answer algebraically rather than algorithmically - since the grid is well-defined, you can determine the closest point by geometry rather than by testing pairs of points. – Brian L
@BrianL Good idea! If the points have a rotation transform you can axially align them then search based on an expanding box method! – Fantastic Mr Fox
@BrianL and Ben - in my edit, I have tried to elaborate on the nature of the grid. It is not aligned to the xy axis, and while it looks regular, it isn't - it is geographic (latitude/longitude), and due to the high latitude location (near the south pole), the southernmost cells are slightly smaller than the northernmost. Also, for orientation - North is to the bottom right in the plot above, as it is a polar stereographic representation. – David_G
Yeah, sorry. Old staff website hosting died! I'll see what I can do. – David_G
@naught101 Wow, I'm very surprised I was able to find them tucked away in a 5 year old backup! – David_G

4 Answers

10
votes

The usual method is to go:

for every blue point {
    for every red point {
        is this the closest so far
    }
}

But a better way is to put the red data into a kd tree. This is a tree that splits the data along its mean, then splits the two data sets along their means etc until you have them separated into a tree structure.

enter image description here

This will change your searching effeciancy from O(n*m) to O(log(n)*m)

Here is a library:

http://www.mathworks.com.au/matlabcentral/fileexchange/4586-k-d-tree

This library will provide you the means to easily make a kd tree out of the data and to search for the closest point in it.

Alternatively you can use a quadtree, not as simple but the same idea. (you may have to write your own library for that)

Make sure the largest data set (in this case your red points) go into the tree as this will provide the greatest time reduction.

2
votes

I think I've found a way to do it using the nearest flag of griddata.

I make a matrix that is the same size as the grid x and y matrices, but is filled with the linear indices of the corresponding matrix element. This is formed by reshaping a vector (which is 1:size(x,1)*size(x,2)) to the same dimensions as x.

I then use griddata and the nearest flag to find the linear index of the point closest to each point on my contour (blue dots). Then, simply converting back to subscript notation with ind2sub leaves me with a 2 row vectors describing the matrix subscripts for the points closest to each point on the blue-dotted contour.

This plot below shows the contour (blue dots), the grid (red dots) and the closest grid points (green dots).

result of gridding

This is the code snippet I used:

index_matrix1 = 1:size(x,1)*size(x,2); 
index_matrix1 = reshape(index_matrix1,size(x));
lin_ind = griddata(x,y,index_matrix1,CX,CY,'nearest'); % where CX and CY are the coords of the contour
[sub_ind(1,:),sub_ind(2,:)] = ind2sub(size(x),lin_ind);
1
votes

I suppose that in the stereographic representation, your points form a neat grid in r-theta coordinates. (I'm not too familiar with this, so correct me if I'm wrong. My suggestion may still apply).

For plotting you convert from the stereographic to latitude-longitude, which distorts the grid. However, for finding the nearest point, consider converting the latitude-longitude of the blue contour points into stereographic coordinates, where it is easy to determine the cell for each point using its r and theta values.

If you can index the cell in the stereographic representation, the index will be the same when you transform to another representation.

The main requirement is that under some transformation, the grid points are defined by two vectors, X and Y, so that for any x in X and y in Y, (x, y) is a grid point. Next transform both the grid and the contour points by that transformation. Then given an arbitrary point (x1, y1), we can find the appropriate grid cell by finding the closest x to x1 and the closest y to y1. Transform back to get the points in the desired coordinate system.

1
votes

dsearchn: N-D nearest point search.

[k, d] = dsearchn(A,B) : returns the distances, d, to the closest points. d is a column vector of length p.

http://au.mathworks.com/help/matlab/ref/dsearchn.html?s_tid=gn_loc_drop