如何在两个最小距离的点列表中有效地找到点对？

Question

pointListA = [(13,45),(33,78),...,(360,240)]
pointListB = [(20,36),(47,32),...,(265,322)]

pointListA和pointListB的长度约为5000或更大更多。我的任务是为pointListA中的每个点找到pointListB中的点，使这两个点之间的距离最小。 我的问题是找到一个有效的方法来完成这项任务。我已经尝试过一些方法，比如遍历两个列表，但是太难了慢点。所以呢，有什么建议吗？你知道吗

编辑1： 我很抱歉刚才在标题中对我的描述现在。现在我将其修改为“如何有效地在两个具有最小距离的点列表中找到点对” 实际上，我想要这样的结果。你知道吗

minDistansceList = [((13,45),(a point in pointListB)),((33,78),(a point in pointListB)).....((360,240),(a point in pointListB))]

Answer 1

我不确定，但是您可以通过从使用scipy.spatial.distance.cdist 'euclidean'结果得到的矩阵中获取diagonal来有效地做到这一点：

#!/bin/python
import numpy as np
from scip.spatial.distance import cdist

pointListB = [(20,36),(47,32),(265,322)]
pointListA = [(13,45),(33,78),(360,240)]
A = np.array(pointListA)
B = np.array(pointListB)
distances = np.diagonal(cdist(A, B, 'euclidean'))
# Minimum distance:
min_dist = np.min(distances)

我们采用对角线的原因是cdist返回从a中的每个点到B中的每个点的距离矩阵。我担心的是，这将生成AxB中间结果来提取len（a）结果的向量。但它将在NumPy的低级（编译的二进制）代码中进行矢量化操作，并可能利用CPU自己的矢量指令集扩展（例如x86上的SSE）。你知道吗

我怀疑有某种方法可以消除额外的计算，但我知道的NumPy不够。你知道吗

Answer 2

作为优化，如果在距离0处找到一个点，则可以利用已找到最近点的事实，并利用使距离平方最小的点使距离最小的事实：

def sdist(p,q):
    return (p[0]-q[0])**2 + (p[1]-q[1])**2

def closestPoint(p,points):
    candidate = points[0]
    currentMin = sdist(p,candidate)
    for q in points[1:]:
        d = sdist(p,q)
        if d == 0: return q
        if d < currentMin:
            currentMin = d
            candidate = q
    return candidate

def closestPoints(pointsA,pointsB):
    return [(p,closestPoint(p,pointsB)) for p in pointsA]

要测试它：

from random import randint

ListA = [(randint(0,1000),randint(0,1000)) for i in range(5000)]
ListB = [(randint(0,1000),randint(0,1000)) for i in range(5000)]

那么

pairs = closestPoints(ListA,ListB)

在我2岁的笔记本电脑上大约需要18秒

Answer 3

假设您想从具有相同索引的每个列表中获取两个点，那么您可以zip两个列表。如果是指从A和B中选择的任意点之间的最小距离，则应使用itertools.product取这两个列表的笛卡尔积：

>>> from itertools import starmap, product
>>> from math import sqrt, pow

>>> def distance(p1, p2):
...     return sqrt(pow(p2[1] - p1[1], 2) + pow(p2[0] - p1[0], 2))

>>> pointListA = [(13,45), (33,78), (360,240)]
>>> pointListB = [(20,36), (47,32), (265,322)]

>>> min(starmap(distance, product(pointListA, pointListB)))
11.40175425099138

更新后：

>>> sorted(product(pointListA, pointListB), key=lambda t: distance(t[0], t[1]))
>>> [((13, 45), (20, 36)), ((13, 45), (47, 32)), ((33, 78), (20, 36)), ...]