# Use of Morton Key to reduce number of grid points

I asked a question on Stack Overflow Performance Issue with VP Trees and Nearest Neighborsand I was not satisfied with the answer and so I thought I would reword my question for this site and post this question as a computational science question.

I am using the VPTree to store the coordinates of my sparse array as data is on a sphere/ellipsoid and I want to use great circle distances or geodesics to do nearest neighbor searches as asked in a related question - Fast nearest neighbor search with latitude and longitude . The creation of the VPTree is itself not a problem as that happens very fast( I have 7000 points approximately). I create a regular grid in the following way and the minLat,maxLat,minLon,maxLon are obtained from the coarse data grid that contains the sparse matrix of observations.

latGrid = np.arange(minLat,maxLat,0.05)
lonGrid = np.arange(minLo,maxLo,0.05)


So the total number of points in latGrid is 1800 and the total number of points in lonGrid is 7200. So the total number of grid points is 1800 * 7200 = 12960000

I am trying to do a Fixed radius nearest neighbor search and that is where I have my problem currently -

for grid_point in (grid_points):
indices = tree.get_all_in_range(grid_point,r=4)
args.append(indices)


When I run this query against 12960000 grid points it takes 12 minutes and I have to run this 175 times.

I build the VPTree using the 7000 points of the coarse grid and I query it with 12960000 points of the regular grid.

I believe the number of grid points that is sent to the query

get_all_in_range


can be reduced substantially as many of the grid points are not in the range of the sparse matrix coordinates. The question is how does one do an "intersection" of the grid points and the coarse matrix coordinates using a mathematical approach ? I have seen the answer to this question - Using Morton keys or Geohashes but I am not sure whether this would be applicable to my problem. At least I do not understand how to apply it to my problem. Similarly can a geodesic convex hull be used to determine the intersection ?

• Have you verified that your units are all correct? vptree's stated purpose is to perform these operations efficiently, and 12 minutes per lookup on a 7000 point dataset is hardly that. let's rule out user error before abandoning this approach – smh Aug 28 '18 at 17:50
• @smh Will clarify your comment in the question – gansub Aug 28 '18 at 17:51