python - Python - 根据距离关联两个点列表
问题描述
我有两组 n 点,作为 Numpy 数组,以随机顺序排列。我必须根据距离(L2)将两个列表之间的点关联起来,以便 list1 中的每个点都有一个且唯一的对应点,即距离 list2 最接近的点。
我的问题:就计算时间而言,最快的方法是什么?
现在,我计算对称交叉范数矩阵(使用scipy.spatial.distance_matrix)并通过循环从那里对点进行排序,以找到整个矩阵中的最低范数。然后删除相应的行和列并迭代直到矩阵为空。我想知道是否有一种已知的更快的方法来做到这一点。
[编辑]:这是我得到的代码和示例
import numpy as np
import numpy.ma as ma
import matplotlib.pyplot as plt
from scipy.spatial import distance_matrix
rng = np.random.default_rng()
lst1 = rng.random((10, 2))
lst2 = lst1 + 0.1 * rng.standard_normal(lst1.shape) # rng.random((10, 2))
mask = np.zeros((len(lst1), len(lst2)), dtype=bool)
dst = ma.array(distance_matrix(lst1, lst2), mask=mask)
ord_lst1 = []
ord_lst2 = []
for i in range(min(len(lst1), len(lst2))):
index = np.unravel_index(np.argmin(dst), shape=dst.shape)
ord_lst1.append(lst1[index[0], :])
ord_lst2.append(lst2[index[1], :])
dst[index[0], :] = ma.masked
dst[:, index[1]] = ma.masked
fig = plt.figure()
plt.grid(True)
plt.scatter(x=lst1[:, 0], y=lst1[:, 1], label="list1")
plt.scatter(x=lst2[:, 0], y=lst2[:, 1], label="list2")
for p1, p2 in zip(ord_lst1, ord_lst2):
plt.plot((p1[0], p2[0]), (p1[1], p2[1]), "--", color="black")
plt.legend()
正如你所看到的,两个非常间隔的点之间的巨大关联可能会令人不安。但是,list1 在 (0.4, 0.6) 中的点与右上角的 list2 最接近,因此建立了关联并排除了这两个点的进一步关联。
谢谢 :)
解决方案
查看 scipy.spatial.KDTree https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.KDTree.html
从列表 2 构建 kdTree,并在列表 1 中的每个点查询它
以下代码段未经测试,因此可能需要调试。这应该是您自己设计的开始
#L1 is numpy array with shape (N,2)
#L2 is numpy array with shape (N,2)
import scipy.spatial
tree=scipy.spatial.KDTree(L2)
assoc=[]
for I1,point in enumerate(L1):
_,I2 = tree.query(point,k=1)
assoc.append((I1,I2))
该assoc
变量包含作为索引元组列表的最终关联
编辑:为了帮助解决非唯一关联问题,第一步可能是运行 KDtree 算法两次,一次使用“主列表”L1,一次使用“主列表”L2,然后仅保留两者之间共有的关联。然后,您可以将剩余点作为特殊情况处理。
推荐阅读
- r - 如何使用 Latex 在 rmarkdown 中为页脚制作背景颜色?
- php - 此集合实例上不存在属性 [列]
- python - ModuleNotFoundError:没有名为“firebase”的模块 - 即使我安装了 firebase
- flutter - Flutter RenderObject 断言失败
- python-3.x - 如何更正时间序列数据上的不匹配映射
- paypal - Paypal 计划:每月(OK)、每年(OK)和终身(这甚至可能吗?)
- java - 如何在 Java 中遍历按钮并禁用它们?
- reactjs - 如何从 next.js 中的自定义 App 组件中读取文件
- python - 是否可以使用 EinsumDense 而不是多个并行的 Dense 层?
- elasticsearch - 无法将仪表板加载到 kibana