Find connected circles

Question

I have a problem as follows:

• We have a set of circles (we know the radius r and the center point c in R^d of each circle)
• We need to find lists. Each list contains circles that overlap and connect each other.
• For example, we have 6 circles in 2D as bellows. We need to find two lists. The first list contains red, yellow, orange, and magenta circles. The second list contains blue and green circles.

An obvious solution is to check overlap of each pair, then find connected components. However, the complexity is O(N²). My question is whether there is any better solution.

Answer 1

You don't need to check each pair of circles, so you can apply one of the neighour search algorithms. They restrict the distance calculations to the circles in the vicinity of each other by generating a list of potential neighbours based on a certain division of space.

I would suggest to use the kd-tree method, which is efficient for circles with variable radii and has linear complexity. However, if you have only a few circles, brute-force method is more efficient.

Answer 2

Allow me to introduce a linear time, $C\cdot O(N) + O(W\cdot H)$ algorithm where $C$ denotes the number of circles, plus some small coefficient, and $O(W\cdot H)$ is always constant. In this one, you will not need KD-trees, which make it $O(N\cdot log(N))$ anyways. This of course, comes at the expense of some additional space consumption - though KD-trees also do, and a very acceptable approximation in certain cases.

What one could do is to render the circles on a fixed spatial domain, such as an image, and find the connected components on that image. It is then possible to directly find the equivalences, from the components in the image. Here is a pseudo-code of the idea:

   $\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}$

If one likes to consider the nested circles as connected, then the rendering (e.g. using Bresenham or midpoint algorithm) should be made filled, otherwise, boundary drawing is sufficient and makes the algorithm far more efficient (image is never fully traversed).

Let's take the following configuration:

The connected components, $\mathbf{CC}$, looks like:

and the mapping array contains values such as: $[2 ,3, 1, 2, 1, 4]$.

Below, I provide a very dirty, but hopefully working solution in MATLAB. It can be implemented much more efficiently, but this one in general, demonstrates the concept.

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