在Python中查找两个列表中点之间的最短距离

Question

我有两个坐标列表：

s1 = [(0,0), (0,1), (1,0), (1,1)]
s2 = [(3,2), (1,9)]

我想计算s1中每个点到s2中任一点的最小距离。例如，结果应该如下所示。

result = [3.60, 3.16, 2.82, 2.23]

问题：如何在执行时间最优的情况下，实现这个结果？

到目前为止，我尝试了这种方法，但执行时间不太理想：

import math
def nearestDistance(boundary, p):
    minDistList = map(lambda b: (b[0] - p[0])**2 + (b[1] - p[1])**2, boundary)
    minDist2 = min(minDistList)
    return math.sqrt(float(minDist2))

d = []
for p in s1:
    d.append(nearestDistance(s2, p))

我应该改变s1和s2的结构吗（例如使用2D数组而不是点）？

- orak

---

s1和s2在实际中会有多大？ - Thierry Lathuille

s1是一张图片的坐标，大约为800 x 600，而s2是s1中某些点的子集。 - orak

@orak 这将会显著改变游戏规则.. 如果s2是s1的子集，那么它们之间会有一些相等性（即s2中的某些元素也在s1中，因此最小距离将为0）。首先搜索这些相等性将显著加快速度。复杂度为 **O((n-k)^2)**，其中 k 是公共元素的数量。 - Ma0

哦，我可能错误地使用了“子集”这个词，因为我也忽略了s1中的一些元素，否则最小距离总是为0。 - orak

可能会感兴趣：https://erikbern.com/2018/02/15/new-benchmarks-for-approximate-nearest-neighbors.html - Dan

Answer 1

最简单的方法可能是使用scipy.spatial.distance.cdist函数：

import numpy as np
from scipy.spatial import distance

s1 = np.array([(0,0), (0,1), (1,0), (1,1)])
s2 = np.array([(3,2), (1,9)])
print(distance.cdist(s1,s2).min(axis=1))
# array([3.60555128, 3.16227766, 2.82842712, 2.23606798])

通过直接输出 0 来处理在 s1 与 s2 中都存在的任何点，可能会获得更多的速度。

- Graipher

Answer 2

你尝试过使用cdist吗？

import numpy as np
from scipy.spatial.distance import cdist

np.min(cdist(s1,s2))

返回值

array([ 3.60555128,  3.16227766,  2.82842712,  2.23606798])

你可能会通过将s1和s2替换为np.array来获得性能提升，尽管scipy可能在内部执行此操作，但我不确定。

如果这还不够优化，我认为你可以通过找到s2中点的Voronoi图，然后循环遍历s1以查看该点属于哪个区域，并匹配s2中最接近的点，从而实现O(n_s2*log(n_s2) + n_s1)。

- Dan

---

真是太牛了，比我快了7秒钟 :D - Graipher

Answer 3

为了计算N个距离，没有比暴力枚举所有可能性更好的方法。如果你想要更高级的东西，比如最大或最小距离，你可以根据一些外部知识减少计算次数，但是在你的设置下，你能得到的最好结果是O(n^2)的性能。

编辑：鉴于你的评论，有一些方法涉及到一般的“分而治之”的方法。维基百科有一个很好的概述，我会在这里复制一个相关的片段。

问题可以使用递归分治方法在O(n log n)时间内解决，例如如下方式：

1. 按照x坐标对点进行排序。
2. 通过垂直线x=x_mid将点集分成两个大小相等的子集。
3. 在左侧和右侧子集中递归解决问题。这将得到左侧和右侧的最小距离d_Lmin和d_Rmin。
4. 在左侧分割垂直线和右侧之间找到一组点对中的最小距离d_LRmin。
5. 最终答案是d_Lmin、d_Rmin和d_LRmin中的最小值。

- hunteke

---

O(n log n)算法不仅适用于一组点的最近对问题，如何将其应用于在列表（s2）中查找与固定点最近的点的问题，并将其重复应用于s1的所有点？ - Dan

Answer 4

暴力破解是主要的方法。由于您的数据维度较低，可能可以使用KDTree来提高性能。请参考scipy.spatial.KDTree。

kdtree = scipy.spatial.KDTree(s2)
neighbours = kdtree.query(s1)

- eltonlaw

---

https://en.wikipedia.org/wiki/Nearest_neighbor_search#Exact_methods 讨论了使用KD树解决这个问题。 - Dan

Answer 5

你可以使用sklearn的pairwise_distances_argmin_min实现，给定两个点集A和B，返回B中最接近A中每个点pA的点pB以及从pA到pB的距离。

然后，在O(n*log n)时间内选择所有点对中距离最小的一对点：

from sklearn.metrics import pairwise_distances_argmin_min
import numpy as np

def get_closest_pair_of_points(point_list_1: List[Tuple[float]],
                           point_list_2: List[Tuple[float]]) -> Tuple[Tuple, Tuple, float]:
    """
    Determine the two points from two disjoint lists of points that are closest to 
    each other and the distance between them.

    Args:
        point_list_1: First list of points.
        point_list_2: Second list of points.

    Returns:
        Two points that make the closest distance and the distance between them.
    """
    indeces_of_closest_point_in_list_2, distances = pairwise_distances_argmin_min(point_list_1, point_list_2)

    # Get index of a point pair that makes the smallest distance.
    min_distance_pair_index = np.argmin(distances)

    # Get the two points that make this smallest distance.
    min_distance_pair_point_1 = point_list_1[min_distance_pair_index]
    min_distance_pair_point_2 = point_list_2[indeces_of_closest_point_in_list_2[min_distance_pair_index]]

    min_distance = distances[min_distance_pair_index]

    return min_distance_pair_point_1, min_distance_pair_point_2, min_distance

在我测试过的所有实现中，这是最快的。它也没有任何点分布上的限制（例如，两个点集可以被平面分隔等）。

- Leo Kolezhuk