Finding overlap between multiple circles

I have two matrices.

Each matrix is of dimension 3 * k and represents k circles with each column in the form of [x y r] where (x,y) is the center of the circle and r is it's radius.

So one matrix which has 3 circles is in the form of

x1 x2 x3 

y1 y2 y3

r1 r2 r3

I need to find what are the circles which overlap and the overlapped area between the two matrices. Clearly there may be multiple circles which overlap.The dimension k may be different for two matrices. I have 2 extra matrices of each matrix, one sorted by it's x coordinates and other sorted by y coordinates if that helps in computation.

Is there any proper algorithm for finding this?Is this the efficient way to start solving this i.e. is any other way to store data whic helps to compute this quickly.

Note: This is for finding the overlapped region between two SIFT interest points between two images where each image has multiple interest points and is of the form (x,y,sigma,theta)

Edit:

I'm not asking for every pair of circles overlapping area.

Suppose, consider a circle in first matrix. Now consider every other circle in second matrix. Now, I need to find out what circles in the second matrix overlap with the circle considered. I need to do this for every circle in the first matrix. Similarly for every circle in the second matrix with respect to first matrix.

So I need for each circle in the two matrices (There are k1+k2 of them), how much area is overlapping with the other matrix and what are the circles in the other matrix that are overlapping. The problem is that there are a lot of circles in the matrix and i'm looking for an efficient way to do it. Moreover I would like to extend this this more than two matrices and then an efficient code would greatly improve the execution time.

A preview of the two images (whose corresponding matrices of circles i have with me) is given in the below link https://www.dropbox.com/s/om5has5uw91dj6p/overlap.jpg

[Roger Stafford]

You need to define more carefully the question "what are the circles which overlap and the overlapped area between the two matrices." This can be interpreted in more than one way. Are you asking for the area common to all circles of both matrices? Are you asking for the common area for each possible pair of circles, one from the first matrix and the other from the second matrix, so that two matrices with k1 and k2 columns respectively would have k1*k2 pairings to test?

The second interpretation is relatively easy to do while the first one would in my opinion be extremely difficult to carry out, so the distinction here is of considerable importance.

[N/A]

Pardon me for not being clear. No, I'm not asking for every pair of circles overlapping area.

Suppose, consider a circle in first matrix. Now consider every other circle in second matrix. Now, I need to find out what circles in the second matrix overlap with the circle considered. I need to do this for every circle in the first matrix. Similarly for every circle in the second matrix with respect to first matrix.

So I need for each circle in the two matrices (There are k1+k2 of them), how much area is overlapping with the other matrix and what are the circles in the other matrix that are overlapping. The problem is that there are a lot of circles in the matrix and i'm looking for an efficient way to do it. Moreover I would like to extend this this more than two matrices and then an efficient code would greatly improve the execution time.

A preview of the two images (whose corresponding matrices of circles i have with me) is given in the below link https://www.dropbox.com/s/om5has5uw91dj6p/overlap.jpg

[Image Analyst]

dropbox is banned by my company - I'll have to look at that after I get home.

[Roger Stafford]

Priyatham, your question is still not clear to me. You say "for each circle in the two matrices (There are k1+k2 of them), how much area is overlapping with the other matrix and what are the circles in the other matrix that are overlapping." The aspect that is not clear is what you mean by "overlap" when more than two circles are involved. Suppose for the sake of discussion that one of these matrices holds just one circle, call it circle A, and the other matrix has two circles, call them circles B and C. It is quite possible for A to overlap B, for A to overlap C, and for B to overlap C, and yet there be no region of points which lie within all three circles simultaneously. Can you envision that? The question I pose to you is this. Do you consider what you call the "overlapping area" to be an area of zero since there is no common area to all three circles, or do you consider there to be separate nonzero areas for each overlapping pair of circles?

The differences between these two notions is extremely important as regards reaching an analytic solution. The solution I have provided you elsewhere here is just for a pair of circles. The problem of determining the common area occupied by even as few as three circles is much more difficult from an analytic point of view since the common overlap area can be involve many possibilities. It can be an region bounded by one, two, three, or four arcs for the three circles. With more than three circles, as in the link you provided, the possibilities expand to astronomical magnitudes.

[Image Analyst]

OK, I'm home now so I can see the image. I could be wrong, but that looks like a "salient points" image, like you'd see here and on similar web pages. The circles enclose interesting "salient" regions in the image. Because Priyatham has two sets I'd guess one set was from one frame of a video and another set was from the next frame in the video and he's trying to see which circle in one frame corresponds to which circle in the other frame and he's assuming that the two circles that overlap the most represent the same region of the image. For example he wants to do vehicle tracking and one circle might represent the license plate and it has moved from one frame to the next so the circle around it has different coordinates. So in that case, he's interested in comparing exactly two circles at a time and the area would go from 0 (no overlap) to as much as the area of the smaller circle (the circle for a given salient point such as the license plate might not be the same size or location in each image.). Note though in the example web site I linked to, that you can have multiple circles inside a much larger circle, so it's not quite as simple as getting overlap areas. You also have to consider that the two candidate circles have the same center and same radius, or close to it. Actually I don't know the details of how they get the salient point correspondences, but they do, so you might look up details in papers discussing algorithms like SIFT and SURF.

Answer 1

[Image Analyst]

Don't you just see if sqrt(xj-xk)^2+(yj-yk)^2) < rj+rk? If it is, then they overlap. If it's > then they don't overlap. So just loop j and k over all possible values and note which overlap and which don't. It's such a very trivial algorithm that I'm sure you must have thought of, so I'm wondering if there's something you didn't tell us or I overlooked something. Or is really as simple as that and you just didn't think much about the problem? The area is probably some formula that is easily found on the web somewhere (you can Google just as well as I can to find sites like this)

[Roger Stafford]

The test isn't quite that easy. Calling rij = sqrt(xj-xk)^2+(yj-yk)^2), you must have

 rij <= ri + rj
 ri <= rj + rij
 rj <= ri + rij

all be true in order to have an "overlap". That is, there must exist a valid triangle with the three sides ri, rj, and rij.

[Roger Stafford]

I should correct that statement to be the following. The first inequality must be true for there to exist an overlap. If either of the second two inequalities is false, then the overlap is simply one of the whole circles since it lies entirely inside the other circle. All three inequalities are tests that need to be made to derive a correct area.

[Image Analyst]

Good point. I guess you could use an if statement to determine if you have the case of regular/normal, partial overlap or if it's one of the two cases of one circle lying completely inside the other.

[N/A]

Pardon me for not being clear. I have updated the question.

[Image Analyst]

See my comment on salient points above and then go here for algorithms and papers: https://www.google.com/search?hl=En&as_sitesearch=www.visionbib.com%2F&bthG=Google%2BSearch&q=salient+points

Answer 2

[Roger Stafford]

If ImageAnalyst's assumption is correct that you only want to find the area of overlap between pairs of circles, one from each matrix, then the following method can be applied to each possible pair using two nested for-loops. Let a pair have centers at (x1,y1) and (x2,y2), and let their respective radii be r1 and r2. Then do the following:

 d2 = (x2-x1)^2+(y2-y1)^2;
 d = sqrt(d2);
 t = ((r1+r2)^2-d2)*(d2-(r2-r1)^2);
 if t >= 0 % The circles overlap
   A = r1^2*acos((r1^2-r2^2+d2)/(2*d*r1)) ...
      +r2^2*acos((r2^2-r1^2+d2)/(2*d*r2)) ...
      -1/2*sqrt(t);
 elseif d > r1+r2  % The circles are disjoint
   A = 0;
 else  % One circle is contained entirely within the other
   A = pi*min(r1,r2)^2;
 end

A will be the area of overlap of the pair in all cases.

It would be rather messy trying to vectorize this and it might not execute any faster. I would suggest being content to use for-loops.

[Nazrin Afiq Abdul Rahman]

hello,

The code u give is it the formula to calculate the overlap area between two circles? If it is the calculation for overlap area for circle i will edit it and use it directly becos i want to use it too to calculate the overlap area between two circles and plus i have multiple circle which all were overlap.