最近点对算法详解（使用Python实现分治法解决计算几何问题）

Python 实现步骤

下面我们将一步步用 Python 编写这个算法。

1. 计算两点间欧氏距离

import mathdef distance(p1, p2):    """计算两点之间的欧氏距离"""    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

2. 暴力法（用于小规模点集）

当点的数量 ≤ 3 时，直接暴力比较更高效。

def brute_force(points):    """暴力法求最近点对"""    min_dist = float('inf')    pair = None    n = len(points)    for i in range(n):        for j in range(i + 1, n):            d = distance(points[i], points[j])            if d < min_dist:                min_dist = d                pair = (points[i], points[j])    return min_dist, pair

3. 合并阶段：检查中线附近的点

我们只关心那些 x 坐标与中线距离小于 d 的点，并且对这些点按 y 排序后，只需检查每个点之后最多 6 个点（这是几何性质决定的）。

def closest_split_pair(px, py, delta, best_pair):    """    px: 按x排序的点列表    py: 按y排序的点列表    delta: 当前最小距离    best_pair: 当前最佳点对    """    mid_x = px[len(px) // 2][0]    # 筛选出中线附近 delta 范围内的点    sy = [p for p in py if abs(p[0] - mid_x) <= delta]        best = delta    for i in range(len(sy)):        j = i + 1        # 只需检查最多6个点（理论上最多7个，但通常6个足够）        while j < len(sy) and (sy[j][1] - sy[i][1]) < best:            d = distance(sy[i], sy[j])            if d < best:                best = d                best_pair = (sy[i], sy[j])            j += 1    return best, best_pair

4. 主函数：递归实现分治

def closest_pair_rec(px, py):    """递归求解最近点对"""    if len(px) <= 3:        return brute_force(px)        mid = len(px) // 2    qx = px[:mid]    rx = px[mid:]        # 根据qx和rx构建对应的按y排序的子列表    midpoint = px[mid][0]    qy = [p for p in py if p[0] <= midpoint]    ry = [p for p in py if p[0] > midpoint]        (d1, pair1) = closest_pair_rec(qx, qy)    (d2, pair2) = closest_pair_rec(rx, ry)        if d1 <= d2:        delta = d1        best_pair = pair1    else:        delta = d2        best_pair = pair2        (d3, pair3) = closest_split_pair(px, py, delta, best_pair)        if d3 < delta:        return (d3, pair3)    else:        return (delta, best_pair)

5. 封装入口函数

def closest_pair(points):    """用户调用的主函数"""    px = sorted(points, key=lambda p: p[0])  # 按x排序    py = sorted(points, key=lambda p: p[1])  # 按y排序    return closest_pair_rec(px, py)

测试一下！

# 示例点集points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]min_dist, pair = closest_pair(points)print(f"最近距离: {min_dist:.2f}")print(f"最近点对: {pair}")

总结

通过本文，你学会了如何用Python最近点对算法高效解决计算几何中的经典问题。该算法利用分治算法思想，将时间复杂度从 O(n²) 降低到 O(n log n)，非常适合处理大规模点集。掌握这一技巧，不仅能提升编程能力，还能为学习更复杂的计算几何算法打下坚实基础。

现在，你可以尝试自己生成随机点集进行测试，或者将此算法应用到实际项目中（如地理信息系统、游戏开发等）。编程的世界，因算法而精彩！