用莫顿代码找到最近的邻居

Question

我已经实现了一个 decode/encode 方法来将 2d 点转换成它们各自的 morton code。

我要找的是最近的邻居（在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) 并通过 substracting/adding 距离创建最小点和最大点：min=(81, 185) 和 max=(321,425)。现在，您为这两点创建莫顿代码。

(210,305) 的 120 距离内的所有点都将具有莫顿代码 mcWithin120 和 mortonCode(min) <= mcWithin120 <= mortonCode(max)。如果你有一个按莫顿代码排序的点列表，这应该会大大缩小搜索范围。

请注意，该范围将包含误报！并非所有 morton 代码在 min 和 max 之间的点都在给定的距离 120 内，因此您必须检查范围内的所有点是否 'actually' 在正确的距离内。

如果您对空间搜索感兴趣，请查看 PH-Tree 它是一个空间索引，类似于四叉树，使用莫顿顺序优化树结构和搜索。

用莫顿代码找到最近的邻居

Find nearest neighbor with morton code

python

nearest-neighbor

z-order-curve