编辑“︁点集最近点对”︁

{{DISPLAYTITLE:点集最近点对}}  
{{Note|本文介绍计算几何中的经典问题「点集最近点对」，包含分治法实现、复杂度分析及实际应用案例。}}  

== 概述 ==  
'''最近点对问题'''（Closest Pair of Points Problem）是计算几何中的基础问题之一：给定平面上的<math>n</math>个点，找出其中欧几里得距离最小的两个点。该问题在碰撞检测、地理信息系统（GIS）和模式识别等领域有广泛应用。  

=== 问题定义 ===  
给定点集<math>P = \{p_1, p_2, \ldots, p_n\}</math>，其中每个点<math>p_i = (x_i, y_i)</math>，求解：  
<math>\min_{1 \leq i < j \leq n} \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}</math>  

== 暴力解法 ==  
最直接的方法是计算所有点对的距离并取最小值。  
=== 算法步骤 ===  
1. 遍历所有<math>\binom{n}{2}</math>个点对。  
2. 计算每对点的欧几里得距离。  
3. 记录最小距离及其对应的点对。  

=== 代码示例 ===  
<syntaxhighlight lang="python">  
import math  

def brute_force_closest_pair(points):  
    min_dist = float('inf')  
    pair = None  
    n = len(points)  
    for i in range(n):  
        for j in range(i + 1, n):  
            dist = math.sqrt((points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2)  
            if dist < min_dist:  
                min_dist = dist  
                pair = (points[i], points[j])  
    return pair, min_dist  

# 示例输入  
points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]  
print(brute_force_closest_pair(points))  
</syntaxhighlight>  
'''输出'''：  
<pre>(((2, 3), (3, 4)), 1.4142135623730951)</pre>  
'''复杂度分析'''：时间复杂度为<math>O(n^2)</math>，空间复杂度为<math>O(1)</math>。  

== 分治法优化 ==  
分治法可将时间复杂度优化至<math>O(n \log n)</math>，步骤如下：  
1. '''按x坐标排序'''点集并递归分割为左右两半。  
2. '''递归求解'''左右两半的最近点对。  
3. '''合并阶段'''：检查距离分割线小于当前最小距离的点，构成候选点对。  

=== 算法细节 ===  
* '''分割线'''：取点集的中位数x坐标。  
* '''候选区域'''：仅需检查距离分割线<math>d</math>（当前最小距离）以内的点。  
* '''纵坐标优化'''：在候选区域内按y坐标排序，只需检查后续7个点。  

=== 代码示例 ===  
<syntaxhighlight lang="python">  
def closest_pair(points):  
    points_sorted_x = sorted(points, key=lambda x: x[0])  
    return _closest_pair(points_sorted_x)  

def _closest_pair(points):  
    n = len(points)  
    if n <= 3:  
        return brute_force_closest_pair(points)  

    mid = n // 2  
    left_pair, left_dist = _closest_pair(points[:mid])  
    right_pair, right_dist = _closest_pair(points[mid:])  
    min_dist = min(left_dist, right_dist)  
    min_pair = left_pair if left_dist < right_dist else right_pair  

    # 合并阶段  
    mid_x = points[mid][0]  
    candidates = [p for p in points if abs(p[0] - mid_x) < min_dist]  
    candidates.sort(key=lambda x: x[1])  

    for i in range(len(candidates)):  
        for j in range(i + 1, min(i + 8, len(candidates))):  
            dist = math.sqrt((candidates[i][0] - candidates[j][0])**2 + (candidates[i][1] - candidates[j][1])**2)  
            if dist < min_dist:  
                min_dist = dist  
                min_pair = (candidates[i], candidates[j])  
    return min_pair, min_dist  
</syntaxhighlight>  

=== 复杂度分析 ===  
* 时间复杂度：<math>O(n \log n)</math>（排序占主导）。  
* 空间复杂度：<math>O(n)</math>（递归栈和临时数组）。  

== 实际应用 ==  
1. '''碰撞检测'''：游戏引擎中快速检测物体是否接触。  
2. '''天文数据分析'''：识别邻近恒星或星系。  
3. '''路径规划'''：无人机避障时计算最近障碍物。  

== 可视化示例 ==  
<mermaid>  
graph TD  
    A[输入点集] --> B[按x坐标排序]  
    B --> C[递归分割至子集≤3点]  
    C --> D[暴力求解子集最近点对]  
    D --> E[合并阶段: 检查候选区域]  
    E --> F[输出全局最近点对]  
</mermaid>  

== 扩展阅读 ==  
* 进一步优化：随机化算法或并行化处理。  
* 三维空间中的最近点对问题。  

{{Warning|分治法实现需注意边界条件和递归终止条件。}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:计算几何算法]]