用莫顿码寻找最近邻居

Question

用莫顿码寻找最近邻居

4

我已经实现了一个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)

可以吗？

- greedsin

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- TilmannZ · Accepted Answer

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

所有距离（210，305）距离在120以内的点都将具有莫顿编码mcWithin120，其中mortonCode（min）<= mcWithin120 <= mortonCode（max）。如果您有按莫顿代码排序的点列表，则应该能够缩小搜索区域。

请注意，范围将包含错误结果！并非所有莫顿代码在min和max之间的点都处于给定距离120内，因此必须检查在范围内的所有点是否“实际”位于正确距离内。

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