用matlab写出分治法求最小点对距离的过程演示图

由于分治法求最小点对距离的过程比较复杂，无法用一张图简单地呈现，这里我们用文字和伪代码来描述其过程。

1. 将点按照 x 坐标排序

2. 递归地将点集分为左右两个子集，直到每个子集只有一个点

3. 对于每个子集，分别求出其最小点对距离

4. 找出左右两个子集的最小点对距离 d_min

5. 在距离线 d = x-d_min 和 d = x+d_min 之间搜索可能的最小点对距离

6. 在这个距离范围内，对于每个点，只需要考虑与其 y 坐标相差不超过 d_min 的点的距离，因为超过 d_min 的点不可能成为最小点对距离

7. 将这些点按照 y 坐标排序，然后依次计算它们与后面 7 个点的距离，找出其中最小的距离 d_mid

8. 返回左右两个子集和距离 d_mid 中的最小值

伪代码如下：

function d = closest_pair(points) points = sort_points_by_x(points) d = closest_pair_recursive(points)

function d = closest_pair_recursive(points) n = length(points) if n <= 1 d = inf else mid = floor(n/2) left_points = points(1:mid) right_points = points(mid+1:end) d_left = closest_pair_recursive(left_points) d_right = closest_pair_recursive(right_points) d_min = min(d_left, d_right) d_mid = closest_pair_between_splits(points, d_min) d = min(d_min, d_mid)

function d = closest_pair_between_splits(points, d_min) n = length(points) mid_x = points(floor(n/2)).x left_idx = find([points.x] >= mid_x-d_min) right_idx = find([points.x] <= mid_x+d_min) split_idx = intersect(left_idx, right_idx) split_points = points(split_idx) split_points = sort_points_by_y(split_points) m = length(split_points) d = d_min for i = 1:m for j = i+1:min(i+7, m) dist = distance(split_points(i), split_points(j)) if dist < d d = dist end end end

function points = sort_points_by_x(points) [~, idx] = sort([points.x]) points = points(idx)

function points = sort_points_by_y(points) [~, idx] = sort([points.y]) points = points(idx)

function dist = distance(p1, p2) dist = sqrt((p1.x-p2.x)^2 + (p1.y-p2.y)^2)