您不需要检查每一对圆圈，因此您可以应用其中一种邻居搜索算法。它们通过基于一定的空间划分生成潜在邻居列表，将距离计算限制在彼此附近的圆圈内。

我建议使用kd-tree方法，该方法对于具有可变半径且具有线性复杂性的圆非常有效。但是，如果你只有几个圈子，蛮力方法更有效。

请允许我介绍一个线性时间，$C\cdot O(N) + O(W\cdot H)$算法在哪里$C$表示圆的数量，加上一些小系数，并且$O(W\cdot H)$总是不变的。在这一个中，您将不需要 KD-trees，这使得它$O(N\cdot log(N))$无论如何。当然，这是以一些额外的空间消耗为代价的——尽管 KD-trees 也会这样做，并且在某些情况下是一个非常可接受的近似值。

可以做的是在固定空间域（例如图像）上渲染圆圈，并在该图像上找到连接的组件。然后可以直接从图像中的组件中找到等价物。这是这个想法的伪代码：

   $\mathbf{I}$ $\leftarrow$ $\text{empty image}$

   $\text{for all} (circle \in \mathbf{C}$)$\{$

      $\mathbf{I} \gets \text{render_circle}(\mathbf{I}$,$circle$)

   $\}$

   $\mathbf{CC} \gets \text{conn_comp}(\mathbf{I})$

   $\text{look-up the label of each } circle \in \mathbf{C} \text{ from }\mathbf{CC}$

如果人们喜欢将嵌套的圆视为连接的，则应该填充渲染（例如使用 Bresenham 或中点算法），否则，边界绘制就足够了，并且使算法更加高效（图像永远不会完全遍历）。

让我们采取以下配置：

连接的组件，$\mathbf{CC}$， 好像：

并且映射数组包含以下值：$[2 ,3, 1, 2, 1, 4]$.

下面，我提供了一个非常肮脏但希望在 MATLAB 中有效的解决方案。它可以更有效地实现，但一般来说，这一个展示了这个概念。

close all;

% some experimental parameters 
n = 6; % # circles
width = 256;
height = 256;
maxRadius = 60;

% generate some random data 
cx = rand(n, 1)*width;
cy = rand(n, 1)*height;
r = 4+rand(n, 1)*maxRadius;

circIds = cell(width*height, 1); % image, where each pixel is a an array

% now render the circles to integer coordinates
figure, hold on;
for i=1:n
    h = viscircles([cx(i), cy(i)], r(i), 'Color', colors(i,:));

    list = double(midPointCircle(r(i), cx(i), cy(i)));
    li = double(list(:,2));
    lj = double(list(:,1));
    invalid = (li<=0 | li>height | lj<=0 | lj>width);
    li(invalid)=[];
    lj(invalid)=[];
    ind = sub2ind(([height, width]), li, lj);
    for j=1:length(circIds(ind))
        circIds(ind(j)) = {[cell2mat(circIds(ind(j))) i]};
    end
end
drawnow; hold off;

% compute the label image 
I = zeros(height, width);
Ilogical = (false(height, width));
for i=1:length(circIds)
    C = circIds{i};
    for j=1:length(C)
        [row, col] = ind2sub(([height, width]), i);
        I(row, col) = C(j);
        Ilogical(row, col) = 1;
    end
end
figure, imagesc(I);

% find the connected components on the image
Ccomp = bwlabel(Ilogical,8); % O(WH)
figure, imagesc(Ccomp);

mapping = zeros(n, 1);
% now collect the equivalences
for i=1:length(circIds)
    C = circIds{i};
    for j=1:length(C)
        [row, col] = ind2sub(([height, width]), i);
        mapping(C(j)) = Ccomp(row, col);
        if (all(mapping))
            break;
        end
    end
    if (all(mapping))
        break;
    end
end

% the final connected components
mapping