2
$\begingroup$

I have a problem as follows:

  • We have a set of circles (we know the radius r and the center point c in Rd 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(N2). My question is whether there is any better solution. example

$\endgroup$
  • $\begingroup$ If you want to find circles that overlap each other wouldn't you have four lists? $\endgroup$ – nicoguaro Dec 19 '17 at 13:29
  • $\begingroup$ I mean finding regions that do not overlap. Four circles (organ, yellow, magenta, red) create a region A. Two circles (green, blue) create another region B. The region A and B do not overlap each other. $\endgroup$ – khanhndk Dec 20 '17 at 10:57
  • $\begingroup$ What if the circles overlap in a tree-like manner with branches? $\endgroup$ – André Dec 20 '17 at 12:00
  • $\begingroup$ It somehow looks like the finding connected components in a graph (Wikipedia). A circle is a vertice. If two circles overlap each other, we have an edge connected between two corresponding vertices. But if we cast the problem to finding connected components, we need to check overlap for all pairs of circles to build a graph before doing the algorithm for finding connected components. $\endgroup$ – khanhndk Dec 21 '17 at 1:28
5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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: enter image description here

The connected components, $\mathbf{CC}$, looks like: enter image description here

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 
$\endgroup$
  • $\begingroup$ It works only on 2D, doesn't it? My problem requires dealing with high dimensional space. $\endgroup$ – khanhndk Dec 25 '17 at 5:44
  • $\begingroup$ Well, you mention 'circles' which are always 2D - any circle can always be mapped to a 2D plane. However, if you speak of objects in more dimensions the question should be phrased differently. In 3D one could render spheres on a grid, which would still work up to the discretization. Higher dimensions might require more care. $\endgroup$ – Tolga Birdal Dec 30 '17 at 19:41

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.