MATLAB 分治法求最小点对距离动态演示

由于分治法求最小点对距离的算法不涉及动态更新，因此无法进行动态演示。以下是一个静态的演示图。

首先，随机生成一些点，并在图中画出它们的位置。

接着，将所有点按照横坐标排序，并在图中用红线标出分界线。

接下来，将点集递归地分成左右两个子集，并对每个子集分别求出最小点对距离。

最后，在两个子集的最小点对距离中取最小值，即为整个点集的最小点对距离。在图中用绿色线标出。

完整的 MATLAB 代码如下：

function demo()
    % 随机生成点
    n = 16;
    X = rand(n, 1);
    Y = rand(n, 1);
    
    % 画出点的位置
    scatter(X, Y, 'filled');
    xlim([0, 1]);
    ylim([0, 1]);
    
    % 分治法求最小点对距离
    [d, ~, ~] = divide_conquer(X, Y);
    
    % 画出分界线和最小点对距离
    hold on;
    plot([0, 1], [0.5, 0.5], 'r');
    plot([0, 1], [0.25, 0.25], 'r');
    plot([0, 1], [0.75, 0.75], 'r');
    plot([X(1), X(end)], [Y(1), Y(1)], 'g');
    text(X(1), Y(1), sprintf('%.2f', d), 'VerticalAlignment', 'top');
    hold off;
end

function [d, x, y] = divide_conquer(X, Y)
    % 递归终止条件
    n = length(X);
    if n <= 1
        d = Inf;
        x = [];
        y = [];
        return;
    elseif n == 2
        d = norm([X(1), Y(1)] - [X(2), Y(2)]);
        x = [X(1), X(2)];
        y = [Y(1), Y(2)];
        return;
    end
    
    % 将点集分成左右两个子集
    mid = ceil(n / 2);
    [d1, x1, y1] = divide_conquer(X(1:mid), Y(1:mid));
    [d2, x2, y2] = divide_conquer(X(mid+1:end), Y(mid+1:end));
    if d1 < d2
        d = d1;
        x = x1;
        y = y1;
    else
        d = d2;
        x = x2;
        y = y2;
    end
    
    % 确定分界线
    xmid = X(mid);
    idx = (X >= xmid - d) & (X <= xmid + d);
    Ymid = Y(idx);
    nmid = length(Ymid);
    
    % 按照纵坐标排序
    [~, order] = sort(Ymid);
    Ymid = Ymid(order);
    
    % 计算最小点对距离
    for i = 1:nmid
        j = i + 1;
        while j <= nmid && Ymid(j) - Ymid(i) < d
            dij = norm([xmid, Ymid(i)] - [xmid, Ymid(j)]);
            if dij < d
                d = dij;
                x = [xmid, xmid];
                y = [Ymid(i), Ymid(j)];
            end
            j = j + 1;
        end
    end
end