2

我有两个清单。第一个列表是坐标对列表

[[x1, y1]
 [x2, y2]
 ...
 [xn, yn]]

第二个列表是坐标对列表以及与每对关联的值

[[x1',y1',v1']
 [x2',y2',v2']
 ...
 [xn',yn',vn']]

我想为第一个列表中的每对（x，y）在第二个列表中找到最接近的（x'，y'），然后将值 v' 映射到（x，y）。

我目前的解决方案是遍历两个列表并计算每个可能的坐标对之间的欧几里得距离并映射到最小距离。但是原来的第二个列表有300万个条目！有没有更有效的方法来实现这一目标？谢谢。

4

2 回答 2

1

您可以创建一个空间地图，将“区域”映射到该区域中的第二个列表中的点，例如，您可以将 x-min、x-max、y-min、y-max 的 4 元组映射到点，像这样：

{(0, 10, 0, 10): [(2, 4, 5), (5, 1, 12), ...], (0, 10, 10, 20): [(4, 14, -1), ...] }

现在您可以从第一个列表中为您的点选择相应的区域，例如，如果该点是(24, 13)，则选择与 area 对应的列表(20, 30, 10, 20)。当然，这些区域的大小可能会根据点的分布而有所不同。

如果该区域有任何点，则选择与原点距离最小的点；否则，请查看该区域周围八个区域的下一个“层”，依此类推。一旦你找到了一个点，你应该再扩展一层，因为在这些层中仍然可能有一个点更接近原始点。（见图）

在此处输入图像描述

这里，红点是第一个列表中的点，蓝点是第二个列表中的点。这些框对应于地图中的区域。虽然该区域有两个点直接对应原始点，但下一个“层”中有更接近的点，但您不必再往外搜索。

于 2013-10-09T08:34:43.797 回答
1

尝试对第二个列表中的坐标进行四舍五入。如果坐标，这会给你很多小集群。使用圆角坐标作为字典中的键，坐标+值列表作为值。

for x,y in first_list:
    x_,y_ = round(x,y)
    l = d[(x_,y_)]
    ... find closest point in l...

使用此算法，您只需要检查几个点。

如果列表为空，您可以使用更松散的舍入重试。

于 2013-10-09T08:30:42.463 回答