Find nearest neighbor with morton code

Question

I have implemented a decode/encode method for transforming 2d points into their respective morton code.

What am i looking for is to find the nearest neighbor (under a min_distance) So for example something like this:

points=[(200,300),(500,150),(100,50)]
mortonCodes = {}
for p in points:
    mortonCodes[encode(p)] = p

nearest = findNearestNeighbor(mortonCodes, (201,305))
print(nearest) # ---> should return (200,300)

Is this possible?

Answer 1

You can do the following using min_distance, for example 120: Use your query point qp=(201,305) and create the minimal and maximal points by substracting/adding the distance: min=(81, 185) and max=(321,425). Now, you create the morton codes for these two points.

All points that are within a distance of 120 of (210,305) will have a morton code mcWithin120 with mortonCode(min) <= mcWithin120 <= mortonCode(max). If you have a list of points ordered by morton code, this should narrow down the search area quite a bit.

Note that the range will contain false positives! Not all points with morton code between min and max are in the given distance 120, so you have to check all points in the range whether they 'actually' are within the right distance.

If you are interested in spatial search, have a look at the PH-Tree it is a spatial index, similar to quadtree, that uses morton order to optimize tree structure and searches.