Check Overlap Between Circles

Hi,

I have the diameters and distances of n circles from one another. Each pair of circles which sum of diameters is grater than half the distance between them (0.5*dij<di+dj) should be overlaped by a circle tangent to both of them(Dij=dij+0.5*(di+dj)). If multiple circles are overlaped by this manner, they should all be overlaped by a circle tangent to the two most distant original circles (even if those two are not directly overlaped by the manner above).

How can I find the overlap for multiple circles? Is there an efficient to do this?

Thank you

[Walter Roberson]

You do not need to calculate the overlap between circles. You only need to calculate the distance between them to find out whether they satisfy the condition. You would also internally mark which circles are overlapping, and work out a transitive closure to find the set of overlapped circles. (sets can help with that; there are also graph-theory approaches.)

[Daniel Liberman]

How can I use sets to find the total overlap for multiple circles in the manner above?

and lets say that insted of distances between the circles I have the exact x and y coordinates for each circle

[Walter Roberson]

Create a cell array of sets (a set in matlab is represented by a numeric vector). Start it out as num2cell(1:number_of_circles) -- so each circle is in its own set.

When you determine that two circles are overlapping in the appropriate way, then for each of the two circle indices, find the index in the cell array of the set that the circle index belongs to. If the two are the same, then they are already both entered in the same set and you do not need to do anything. Otherwise, merge the contents of the higher numbered one into the lower numbered one, removing the higher numbered one.

Afterwards, prune out the sets that only have a single entry -- they do not have any overlap.

Now each set is a list of circle indices that mutually overlap. You can use the coordinates to find the two most distant circles in the set, and you can create the appropriate tangent circle.

and lets say that insted of distances between the circles I have the exact x and y coordinates for each circle

Coordinates of pixels? Or coordinates of the center? I think I noticed in another Question that you are working with identifying circles in an image, so you might be talking about pixel coordinates ??