找到最近的邻居莫顿·科德

Question

我实现了一个decode/encode方法，用于将2d点转换成它们各自的morton code。在

我要找的是找到最近的邻居（在a min_distance下） 比如这样：

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)

这可能吗？在

Answer 1

可以使用min_distance执行以下操作，例如120： 使用您的查询点qp=(201,305)，并通过减去/添加距离：min=(81, 185)和{}来创建最小和最大点。 现在，为这两点创建莫顿代码。在

距离（210305）120范围内的所有点都将有一个莫顿代码mcWithin120，其中mortonCode(min) <= mcWithin120 <= mortonCode(max)。 如果您有一个按morton代码排序的点列表，那么这应该会缩小搜索范围。在

请注意，该范围将包含误报！并非所有莫顿代码在最小值和最大值之间的点都在给定的距离120内，因此您必须检查范围内的所有点是否“实际上”在正确的距离内。在

如果您对空间搜索感兴趣，请看一下PH-Tree这是一个空间索引，类似于quadtree，它使用morton order优化树结构和搜索。在