高效求解平面最近点对（Rust最近点对算法详解）

暴力解法 vs 分治解法

- 暴力法：遍历所有点对，计算欧几里得距离，记录最小值。时间复杂度 O(n²)。
- 分治法：将点集按 x 坐标排序后递归分割，合并时只检查“中间带”内的候选点。时间复杂度 O(n log n)。

对于大规模数据，分治法优势明显。这也是为什么我们要学习 Rust分治算法 的原因。

Rust 实现步骤详解

我们将按照以下步骤实现：

1. 定义点结构体（Point）
2. 实现距离计算函数
3. 按 x 坐标排序点集
4. 递归分治函数
5. 合并阶段：检查中间 strip 区域

1. 定义点和辅助函数

#[derive(Debug, Clone, Copy)]struct Point {    x: f64,    y: f64,}fn distance(p1: &Point, p2: &Point) -> f64 {    let dx = p1.x - p2.x;    let dy = p1.y - p2.y;    (dx * dx + dy * dy).sqrt()}

2. 主算法函数

我们先对点按 x 排序，然后调用递归函数：

use std::cmp::Ordering;fn closest_pair(points: &mut [Point]) -> Option<(Point, Point, f64)> {    if points.len() < 2 {        return None;    }    // 按 x 坐标排序    points.sort_by(|a, b| a.x.partial_cmp(&b.x).unwrap_or(Ordering::Equal));    // 创建 y 排序副本用于 strip 检查    let mut points_y: Vec = points.to_vec();    points_y.sort_by(|a, b| a.y.partial_cmp(&b.y).unwrap_or(Ordering::Equal));    closest_pair_rec(points, &points_y)}

3. 递归分治核心逻辑

fn closest_pair_rec(px: &[Point], py: &[Point]) -> Option<(Point, Point, f64)> {    let n = px.len();    // 基础情况：点数 ≤ 3，直接暴力计算    if n <= 3 {        return brute_force(px);    }    let mid = n / 2;    let midpoint = px[mid];    // 分割 py 为左右两部分（保持 y 有序）    let (left_y, right_y): (Vec<_>, Vec<_>) = py        .iter()        .partition(|&p| p.x <= midpoint.x);    // 递归求解左右子问题    let left_res = closest_pair_rec(&px[..mid], &left_y);    let right_res = closest_pair_rec(&px[mid..], &right_y);    // 取左右最小距离    let (min_pair, min_dist) = match (left_res, right_res) {        (Some((p1, p2, d1)), Some((p3, p4, d2))) => {            if d1 <= d2 { (Some((p1, p2)), d1) } else { (Some((p3, p4)), d2) }        }        (Some(res), None) => (Some(res), res.2),        (None, Some(res)) => (Some(res), res.2),        (None, None) => return None,    };    // 构建 strip：x 在 [midpoint.x - min_dist, midpoint.x + min_dist] 范围内    let strip: Vec = py        .iter()        .filter(|&&p| (p.x - midpoint.x).abs() < min_dist)        .copied()        .collect();    // 检查 strip 中的点（最多检查每个点后7个点）    let mut best_dist = min_dist;    let mut best_pair = min_pair;    for i in 0..strip.len() {        for j in (i + 1)..strip.len() {            if (strip[j].y - strip[i].y) >= best_dist {                break; // y 差已超，后续更远            }            let d = distance(&strip[i], &strip[j]);            if d < best_dist {                best_dist = d;                best_pair = Some((strip[i], strip[j]));            }        }    }    best_pair.map(|(p1, p2)| (p1, p2, best_dist))}

4. 暴力法辅助函数（用于小规模数据）

fn brute_force(points: &[Point]) -> Option<(Point, Point, f64)> {    let mut min_dist = f64::INFINITY;    let mut pair = None;    for i in 0..points.len() {        for j in (i + 1)..points.len() {            let d = distance(&points[i], &points[j]);            if d < min_dist {                min_dist = d;                pair = Some((points[i], points[j]));            }        }    }    pair.map(|(p1, p2)| (p1, p2, min_dist))}

完整测试示例

fn main() {    let mut points = vec![        Point { x: 2.0, y: 3.0 },        Point { x: 12.0, y: 30.0 },        Point { x: 40.0, y: 50.0 },        Point { x: 5.0, y: 1.0 },        Point { x: 12.0, y: 10.0 },        Point { x: 3.0, y: 4.0 },    ];    match closest_pair(&mut points) {        Some((p1, p2, dist)) => {            println!("最近点对: ({}, {}) 和 ({}, {})", p1.x, p1.y, p2.x, p2.y);            println!("距离: {:.4}", dist);        }        None => println!("点数不足，无法计算最近点对"),    }}

为什么这个算法高效？

关键在于合并阶段的优化：数学上可以证明，在 strip 区域中，每个点只需与它之后最多 7 个点比较（因为 y 有序且距离限制）。这使得合并操作是线性的，整体复杂度为 O(n log n)。

总结

通过本教程，你已经掌握了如何用 Rust语言 实现高效的Rust最近点对算法。这不仅是一个经典的Rust计算几何问题，也是理解Rust分治算法思想的绝佳案例。

建议你动手运行代码，修改点集，观察结果。实践是掌握 Rust编程教程 内容的最佳方式！

提示：实际项目中可考虑使用 f32 提升性能，或添加误差处理以应对 NaN/Inf 等边界情况。