如何用原生Python查找两组二维坐标点中的最近点对

问题背景 #

我有两组[x, y]格式的二维坐标列表（示例已精简），需要找出两组点之间距离最近的一对点，类似寻找两座岛屿海岸线上距离最近的两座灯塔。给定坐标列表如下：

coords1 = [[0.5896793603897095, 2.4871931076049805], [0.6417439579963684, 2.4339494705200195], [0.6417439579963684, 2.4871931076049805], [0.6157116293907166, 2.407327651977539], [0.6677762269973755, 2.4605712890625], [0.6157116889953613, 2.4871931076049805], [0.5896793603897095, 2.407327651977539], [0.6417439579963684, 2.407327651977539], [0.6547601222991943, 2.4738821983337402], [0.6547601222991943, 2.4472603797912598], [0.6026955246925354, 2.4871931076049805]]

coords2 = [[0.7719054222106934, 2.4605712890625], [0.7198407649993896, 2.407327651977539], [0.7979376912117004, 2.4605712890625], [0.7458730936050415, 2.4605712890625], [0.7198408246040344, 2.4339494705200195], [0.7198408246040344, 2.3807055950164795], [0.7328569293022156, 2.4472603797912598], [0.7849215269088745, 2.4605712890625], [0.7588892579078674, 2.4605712890625], [0.7458730936050415, 2.4472603797912598], [0.7198407649993896, 2.4472603797912598], [0.7198407649993896, 2.394016742706299], [0.7198407649993896, 2.4206385612487793]]

closestCoord1 = [] 
closestCoord2 = []

之前尝试通过排序X、Y极值对比的思路未成功，需要用原生Python实现，不能依赖第三方库。

解决方案思路 #

• 采用欧几里得距离计算两点间距，为提升效率，直接比较距离的平方（无需开平方运算，不影响大小排序结果）
• 遍历第一组所有点，与第二组每个点计算距离平方，全程记录当前最小距离值及对应的点对
• 初始将最小距离设为无穷大，遍历过程中不断更新最小距离和对应点对

代码实现 #

coords1 = [[0.5896793603897095, 2.4871931076049805], [0.6417439579963684, 2.4339494705200195], [0.6417439579963684, 2.4871931076049805], [0.6157116293907166, 2.407327651977539], [0.6677762269973755, 2.4605712890625], [0.6157116889953613, 2.4871931076049805], [0.5896793603897095, 2.407327651977539], [0.6417439579963684, 2.407327651977539], [0.6547601222991943, 2.4738821983337402], [0.6547601222991943, 2.4472603797912598], [0.6026955246925354, 2.4871931076049805]]

coords2 = [[0.7719054222106934, 2.4605712890625], [0.7198407649993896, 2.407327651977539], [0.7979376912117004, 2.4605712890625], [0.7458730936050415, 2.4605712890625], [0.7198408246040344, 2.4339494705200195], [0.7198408246040344, 2.3807055950164795], [0.7328569293022156, 2.4472603797912598], [0.7849215269088745, 2.4605712890625], [0.7588892579078674, 2.4605712890625], [0.7458730936050415, 2.4472603797912598], [0.7198407649993896, 2.4472603797912598], [0.7198407649993896, 2.394016742706299], [0.7198407649993896, 2.4206385612487793]]

closestCoord1 = []
closestCoord2 = []

def find_closest_pair(list1, list2):
    min_dist_sq = float('inf')
    closest1 = None
    closest2 = None
    for p1 in list1:
        x1, y1 = p1
        for p2 in list2:
            x2, y2 = p2
            # 计算距离平方，避免开平方开销
            dist_sq = (x1 - x2)**2 + (y1 - y2)**2
            if dist_sq < min_dist_sq:
                min_dist_sq = dist_sq
                closest1 = p1
                closest2 = p2
    return closest1, closest2

# 执行计算并赋值
closestCoord1, closestCoord2 = find_closest_pair(coords1, coords2)

# 输出结果
print("找到的最近点对：")
print(f"coords1中的点：{closestCoord1}")
print(f"coords2中的点：{closestCoord2}")
print(f"两点间距离：{( (closestCoord1[0]-closestCoord2[0])**2 + (closestCoord1[1]-closestCoord2[1])**2 )**0.5}")

补充说明 #

这个暴力遍历方案适合小规模坐标集（比如你提供的几十点规模），运行效率完全足够。如果是超大规模坐标数据，可以考虑分治算法优化，但原生Python实现分治逻辑会复杂很多，你的场景用暴力法是最优选择。

内容的提问来源于stack exchange，提问作者John Gellar