MATLAB 分治法求解最小点对距离算法详解

以下是使用分治法求解最小点对距离的 MATLAB 代码：

function [d, p1, p2] = minDist(points)
% 递归基：如果只剩下一个或两个点，直接计算距离并返回
n = size(points, 1);
if n == 1
    d = inf;
    p1 = 1;
    p2 = 1;
elseif n == 2
    d = norm(points(1,:) - points(2,:));
    p1 = 1;
    p2 = 2;
else
    % 分治：将点集分成左右两个子集
    mid = floor(n / 2);
    [d1, p1_l, p1_r] = minDist(points(1:mid,:));
    [d2, p2_l, p2_r] = minDist(points(mid+1:end,:));
    if d1 < d2
        d = d1;
        p1 = p1_l;
        p2 = p1_r;
    else
        d = d2;
        p1 = p2_l + mid;
        p2 = p2_r + mid;
    end
    
    % 计算跨越中线的最小距离
    x_mid = (points(mid,1) + points(mid+1,1)) / 2;
    idx = (points(:,1) >= x_mid - d) & (points(:,1) <= x_mid + d);
    strip = points(idx,:);
    strip = sortrows(strip, 2);
    m = size(strip, 1);
    for i = 1:m-1
        for j = i+1:min(i+7,m)
            dist = norm(strip(i,:) - strip(j,:));
            if dist < d
                d = dist;
                p1 = find(ismember(points, strip(i,:), 'rows'));
                p2 = find(ismember(points, strip(j,:), 'rows'));
            end
        end
    end
end

end

其中，points 是一个 n*2 的矩阵，每一行表示一个点的坐标；d 表示最小的点对距离；p1 和 p2 表示最小距离的两个点在 points 中的索引。

算法步骤：

递归基： 如果点集只有一个或两个点，直接计算距离并返回。
分治： 将点集分成左右两个子集。
递归求解： 递归地求解左右子集的最小点对距离。
合并： 取左右子集中较小的距离作为当前最小距离，并计算跨越中线的最小距离。
更新最小距离： 如果跨越中线的最小距离小于当前最小距离，则更新最小距离和两个点的索引。

关键代码解释：

mid = floor(n / 2)：计算点集的中间位置。
[d1, p1_l, p1_r] = minDist(points(1:mid,:)) 和 [d2, p2_l, p2_r] = minDist(points(mid+1:end,:))：递归地求解左右子集的最小点对距离。
x_mid = (points(mid,1) + points(mid+1,1)) / 2：计算中线的横坐标。
idx = (points(:,1) >= x_mid - d) & (points(:,1) <= x_mid + d)：筛选出可能存在最小距离的点。
strip = points(idx,:); strip = sortrows(strip, 2)：将筛选出的点按照纵坐标排序。
for i = 1:m-1 for j = i+1:min(i+7,m)：计算跨越中线的最小距离。

注意：

跨越中线的点对最多只有 7 个，因为它们必须在距离中线 d 以内的区域内。
该算法的时间复杂度为 O(n log n)，空间复杂度为 O(n)。